Computational Complexity and Forbidden Graph Patterns

Wednesday, September 16, 2020 - 12:30pm - 1:15pm
Puck Rombach (University of Vermont)
Many graph problems are NP-hard in general, but may be in P for certain classes of graphs. Instead of classifying problems, we can therefore fix a problem and classify graphs into “hard” and “easy” classes. This is often done with respect to classes closed under the minor relation, which is facilitated by the fact that these are well-founded. However, classifying graphs based on forbidden subgraphs or induced subgraphs (such as bipartite graphs, graphs of bounded degree, etc) is more appropriate in many applications. In this case, the “hard” and “easy” classification is more complicated.