Recognition of graph families. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T15:15:31Z http://mathoverflow.net/feeds/question/83255 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/83255/recognition-of-graph-families Recognition of graph families. Bogdan 2011-12-12T16:42:50Z 2011-12-13T10:51:39Z <p>Let F be a family of finite simple graphs, such as planar graphs, Cayley graphs, 4-colorable graphs, etc. The basic question is whether there exists a polynomial-time algorithm to decide whether a given graph G belongs to F. Do you know any summary (for example in the form of table) with state-of-the-art for this problem: for which families F there is a polynomial algorithm (and what is the fastest known algorithm), for which families the problem is NP complete, and for which families it is open.</p> http://mathoverflow.net/questions/83255/recognition-of-graph-families/83260#83260 Answer by Joseph O'Rourke for Recognition of graph families. Joseph O'Rourke 2011-12-12T17:19:27Z 2011-12-12T20:35:30Z <p>Permit me to direct you to the Wikipedia page on "<a href="http://en.wikipedia.org/wiki/Forbidden_graph_characterization" rel="nofollow">Forbidden graph characterization</a>," which contains a long table of graph classes that have a forbidden subgraph characterizations. For example, chordal graphs may be characterized as those with no cycles of length \$\ge 4\$. Then the "<a href="http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem" rel="nofollow">Robertson–Seymour theorem</a>" is relevant, for it implies that</p> <blockquote> <p>for every minor-closed family \$F\$, there is polynomial time algorithm for testing whether a graph belongs to \$F\$.</p> </blockquote> <p>And the R-S theorem itself says that every minor-closed family can be defined by a finite set of forbidden minors, e.g., \$K_5\$ and \$K_{3,3}\$ for planar graphs.</p> http://mathoverflow.net/questions/83255/recognition-of-graph-families/83291#83291 Answer by David Eppstein for Recognition of graph families. David Eppstein 2011-12-12T22:03:51Z 2011-12-12T22:03:51Z <p>It's too big to fit into one table, but I believe what you want is the <a href="http://www.graphclasses.org/" rel="nofollow">Information System on Graph Classes and their Inclusions</a>. In particular, for each of over 1200 graph classes listed on this site, it includes the known results on the complexity of several important computational problems on graphs in that class, including recognition.</p> http://mathoverflow.net/questions/83255/recognition-of-graph-families/83328#83328 Answer by Zsbán Ambrus for Recognition of graph families. Zsbán Ambrus 2011-12-13T10:51:39Z 2011-12-13T10:51:39Z <p>Garey, Michael R. – Johnson, David S., <em>Computers and intractability</em>, a guide to the theory of NP-completeness, 1979. It's a nice book which includes many problems about decision problems on graphs. It even gives a general sufficient condition that makes recognizing a class of graphs NP-complete. I don't remember the details, but I think it has to do with the class being monotonous.</p>