<p>Get Spinrad's book on efficient graph representations:
<a href="http://rads.stackoverflow.com/amzn/click/0821828150" rel="nofollow">http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150</a></p>

<p>Also check out Li and Vitanyai's book on Kolmogorov Complexity:
<a href="http://rads.stackoverflow.com/amzn/click/0821828150" rel="nofollow">http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150</a></p>

<p>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.</p>

CC BY-SA 3.0
2013-05-16T20:15:27.947Z
2013-05-16T20:15:27.947Z
Chad Brewbaker
<p>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:</p>

<p><a href="http://graphclasses.org/" rel="nofollow">http://graphclasses.org/</a></p>

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

<p>I am looking for similar resources.</p>

<p>Thanks.</p>

CC BY-SA 2.5
2010-12-12T12:48:31.863Z
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](http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm).
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-12T12:59:51.103Z
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.
Arman
CC BY-SA 2.5
2010-12-12T13:02:37.793Z
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.).
Arman
CC BY-SA 2.5
2010-12-12T20:23:46.287Z
Suppose you want to know the complexity of Max Clique for, say, [interval graphs](http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_234.html).  Since this is equivalent to Max Independent Set for the [complement of interval graphs](http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_157.html), you can look it up in ISGCI.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-12T20:27:26.127Z
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.
Tsuyoshi Ito
<ds.algorithms><graph-theory><reference-request>
Resources for complexity results for optimization problems in restricted graph classes
Arman
# Resources for complexity results for optimization problems in restricted graph classes

(Asked by: username_0 on 2010-12-12)

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:

<http://graphclasses.org/>

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.

Thanks.

**Tags:** ds.algorithms, graph-theory, reference-request
> **Comments:**
> **username_1**: 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](http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm).  
> **username_0**: 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.  
> **username_0**: 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.).  
> **username_1**: Suppose you want to know the complexity of Max Clique for, say, [interval graphs](http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_234.html).  Since this is equivalent to Max Independent Set for the [complement of interval graphs](http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_157.html), you can look it up in ISGCI.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-05-16. Score: 3

Get Spinrad's book on efficient graph representations:
[http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150](http://rads.stackoverflow.com/amzn/click/0821828150)

Also check out Li and Vitanyai's book on Kolmogorov Complexity:
[http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150](http://rads.stackoverflow.com/amzn/click/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.


---

