5
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ This question is too vague. Any computational problem can be encoded as a family of graphs, so you are effectively asking for a listing of all known problems together with their computational complexity. $\endgroup$ Dec 12, 2011 at 17:14
  • 1
    $\begingroup$ Have you tried asking on cstheory.stackexchange.com ? $\endgroup$ Dec 13, 2011 at 10:59
  • 1
    $\begingroup$ Actually, not so vague: The question is about INTERESTING families, and the answer below from David Eppstein is exactly what I wanted. Ok, then, may I ask much more concrete question: can I efficiently test whether the given (uncolored) graph is the Cayley graph for some group G or not? $\endgroup$
    – Bogdan
    Dec 14, 2011 at 12:48

3 Answers 3

10
$\begingroup$

It's too big to fit into one table, but I believe what you want is the Information System on Graph Classes and their Inclusions. 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.

$\endgroup$
2
  • $\begingroup$ Thans! This is exactly what I have asked. But, surprisingly, this long list of 1200 classes does not include Cayley graphs. So, I still do not know can I efficiently test whether the given (uncolored) graph is the Cayley graph for some group G or not. $\endgroup$
    – Bogdan
    Dec 14, 2011 at 12:46
  • $\begingroup$ Ok, I see now that this is open. Thanks again. $\endgroup$
    – Bogdan
    Dec 14, 2011 at 13:45
3
$\begingroup$

Permit me to direct you to the Wikipedia page on "Forbidden graph characterization," 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 "Robertson–Seymour theorem" is relevant, for it implies that

for every minor-closed family $F$, there is polynomial time algorithm for testing whether a graph belongs to $F$.

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.

$\endgroup$
3
  • $\begingroup$ Cubic time, in fact, if I remember correctly. $\endgroup$
    – Will Sawin
    Dec 12, 2011 at 19:45
  • $\begingroup$ @Will: Yes, cubic in the size of the graph, but with a constant superpolynomial in the minor size. $\endgroup$ Dec 12, 2011 at 20:41
  • 4
    $\begingroup$ The original algorithm of Robertson and Seymour ran in cubic time, but it has since been improved to quadratic by Kawarabayashi, Kobayashi and Reed. See research.nii.ac.jp/~k_keniti/quaddp1.pdf $\endgroup$
    – Tony Huynh
    Dec 12, 2011 at 22:02
1
$\begingroup$

Garey, Michael R. – Johnson, David S., Computers and intractability, 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.