I am specifically interested in optimization problems in graphs (minimum coloring, maximum clique, maximum matching etc.) and I need a resource (database) which contains complexity results on different graph classes. The best resource that I know is the following:


I think this web site is great because it covers all the graph classes, however the results presented (recognition, independent set, domination) in the site and my interests do not match.

I am looking for similar resources.


  • $\begingroup$ Maximum Clique for G is equivalent to Maximum Independent Set for the complement of G and therefore ISGCI contains necessary information. Maximum Matching is always polynomial-time solvable by Edmonds’s matching algorithm. $\endgroup$ – Tsuyoshi Ito Dec 12 '10 at 12:48
  • $\begingroup$ Maybe I am confusing but is it sufficient to have a maximum independent set algorithm for a specific graph class to solve maximum clique problem in the same graph class? I think in order to have this proporty the complement of the graph should also be in the same graph class. $\endgroup$ – Arman Dec 12 '10 at 12:59
  • $\begingroup$ On the other hand, you are complety right on the maximum matching issue. However there can be exist a more efficient matching algorithm for a specific graph class (e.g. trees, planar graphs, etc.). $\endgroup$ – Arman Dec 12 '10 at 13:02
  • 3
    $\begingroup$ Suppose you want to know the complexity of Max Clique for, say, interval graphs. Since this is equivalent to Max Independent Set for the complement of interval graphs, you can look it up in ISGCI. $\endgroup$ – Tsuyoshi Ito Dec 12 '10 at 20:23
  • 3
    $\begingroup$ For some of the special case of Maximum Matching, you can again use ISGCI because Maximum Matching in G is equivalent to Maximum Independent Set in the line graph of G, and sometimes it is shown as linear-time computable (instead of polynomial-time computable) in ISGCI. But to use this method, you have to know the class of the line graphs of certain graphs. $\endgroup$ – Tsuyoshi Ito Dec 12 '10 at 20:27

Get Spinrad's book on efficient graph representations: http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150

Also check out Li and Vitanyai's book on Kolmogorov Complexity: http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150

You will get an appriciation for each graph class by studying succinct data structures. When you understand why certain classes of graphs take less storage than others you gain a great understanding of how to tailor optimization problems on to them.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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