<p>I'd be surprised if there existed a graph library recognizing them all (there is <em>a lot</em> of them), but most of the algorithms you will find in the litterature are focused on a very small amount of classes... For example chordal graphs (easy to recognise), or treewidth-bounded graphs (much harder.. hopefully the algorithms given for these classes are almost useless in practice), planar graphs, ...</p>

<p>In Sage (http://www.sagemath.org/), we are trying to build a large graph library, with recognition algorithms and methods to solve NP-Hard problems. For instance, we have the following methods :</p>

<pre><code>g.is_bipartite
g.is_chordal
g.is_circular_planar
g.is_clique
g.is_drawn_free_of_edge_crossings
g.is_equitable
g.is_eulerian
g.is_even_hole_free
g.is_forest
g.is_gallai_tree
g.is_hamiltonian
g.is_interval
g.is_line_graph
g.is_odd_hole_free
g.is_overfull
g.is_perfect
g.is_planar
g.is_prime
g.is_regular
g.is_split
g.is_transitively_reduced
g.is_tree
g.is_triangle_free
g.is_vertex_transitive
</code></pre>

<p>The best is probably to read the (unfortunately) long list of methods related to graphs...</p>

<p><a href="http://www.sagemath.org/doc/reference/graphs.html">http://www.sagemath.org/doc/reference/graphs.html</a></p>

<p>(I wrote a short tutorial there : <a href="http://www-sop.inria.fr/members/Nathann.Cohen/tut/Graphs/">http://www-sop.inria.fr/members/Nathann.Cohen/tut/Graphs/</a> )</p>

<p>Nathann</p>

CC BY-SA 3.0
2011-04-21T13:17:07.823Z
2011-04-21T13:17:07.823Z
Nathann Cohen
<p>Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource on graph classes <a href="http://www.graphclasses.org" rel="nofollow">http://www.graphclasses.org</a>). 
How can I know if G belong to some of these classes? Do I need to read and code algorithms from each paper to check it? Or there exists already an implementation for most of these algorithms?</p>

<p>Thanks in advance.</p>

<p>Edit: Maybe it is too broad my question but in some sense I want to know if someone is trying to code all these theoretic algorithms.
As a reformulation of my question: Does exist some project with the goal of unify all this theoretical knowledge in practical application (real code implementation)?</p>

CC BY-SA 3.0
2011-04-20T21:30:23.713Z
If you were more specific about which problem you are trying to solve and which class of graphs you are interested in, maybe someone can provide you with an answer. As is, the question is far too broad.
Dave Clarke
CC BY-SA 3.0
2011-04-21T07:38:58.363Z
I saw the graphclasses.org and it is very comprehensive! (it would be great if the Java applet - in the problem/complexity table - had a button "Upload graph and solve" :-D. However you can look at wide math libraries projects such as: the graph-tool project (projects.skewed.de/graph-tool) or the collection of combinatorial/graph tools used in the SAGE math framework (sagemath.org/doc/reference/). SAGE is an open source alternative to Maple, Matlab ...
Marzio De Biasi
CC BY-SA 3.0
2011-04-21T11:42:13.330Z
I did not know that ISGCI moved to a new domain name.  I updated a relevant [FAQ entry](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/229#229) to reflect the change of the address.  So thanks for the information.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-21T14:51:25.267Z
Can you update the title of your question so that people do not have to read the text to know what “these algorithms” refer to?
Tsuyoshi Ito
<ds.algorithms><graph-algorithms><software><implementation>
Are there good implementations for easy subclasses of NP-hard graph problems 
user2582
# Are there good implementations for easy subclasses of NP-hard graph problems 

(Asked by: username_0 on 2011-04-20)

Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource on graph classes <http://www.graphclasses.org>).
How can I know if G belong to some of these classes? Do I need to read and code algorithms from each paper to check it? Or there exists already an implementation for most of these algorithms?

Thanks in advance.

Edit: Maybe it is too broad my question but in some sense I want to know if someone is trying to code all these theoretic algorithms.
As a reformulation of my question: Does exist some project with the goal of unify all this theoretical knowledge in practical application (real code implementation)?

**Tags:** ds.algorithms, graph-algorithms, software, implementation
> **Comments:**
> **username_1**: If you were more specific about which problem you are trying to solve and which class of graphs you are interested in, maybe someone can provide you with an answer. As is, the question is far too broad.  
> **username_2**: I saw the graphclasses.org and it is very comprehensive! (it would be great if the Java applet - in the problem/complexity table - had a button "Upload graph and solve" :-D. However you can look at wide math libraries projects such as: the graph-tool project (projects.skewed.de/graph-tool) or the collection of combinatorial/graph tools used in the SAGE math framework (sagemath.org/doc/reference/). SAGE is an open source alternative to Maple, Matlab ...  
> **username_3**: I did not know that ISGCI moved to a new domain name.  I updated a relevant [FAQ entry](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/229#229) to reflect the change of the address.  So thanks for the information.  
> **username_3**: Can you update the title of your question so that people do not have to read the text to know what “these algorithms” refer to?  

---

## 1 answers

### Answer by username_4 on 2011-04-21. Score: 13 | Accepted answer

I'd be surprised if there existed a graph library recognizing them all (there is a lot of them), but most of the algorithms you will find in the litterature are focused on a very small amount of classes... For example chordal graphs (easy to recognise), or treewidth-bounded graphs (much harder.. hopefully the algorithms given for these classes are almost useless in practice), planar graphs, ...
In Sage (http://www.sagemath.org/), we are trying to build a large graph library, with recognition algorithms and methods to solve NP-Hard problems. For instance, we have the following methods :
g.is_bipartite
g.is_chordal
g.is_circular_planar
g.is_clique
g.is_drawn_free_of_edge_crossings
g.is_equitable
g.is_eulerian
g.is_even_hole_free
g.is_forest
g.is_gallai_tree
g.is_hamiltonian
g.is_interval
g.is_line_graph
g.is_odd_hole_free
g.is_overfull
g.is_perfect
g.is_planar
g.is_prime
g.is_regular
g.is_split
g.is_transitively_reduced
g.is_tree
g.is_triangle_free
g.is_vertex_transitive

The best is probably to read the (unfortunately) long list of methods related to graphs...
http://www.sagemath.org/doc/reference/graphs.html
(I wrote a short tutorial there : http://www-sop.inria.fr/members/Nathann.Cohen/tut/Graphs/ )
Nathann


---

