3
$\begingroup$

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)?

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ 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. $\endgroup$
    – Dave Clarke
    Commented Apr 20, 2011 at 21:30
  • $\begingroup$ 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 ... $\endgroup$
    – Marzio De Biasi
    Commented Apr 21, 2011 at 7:38
  • 1
    $\begingroup$ I did not know that ISGCI moved to a new domain name. I updated a relevant FAQ entry to reflect the change of the address. So thanks for the information. $\endgroup$
    – Tsuyoshi Ito
    Commented Apr 21, 2011 at 11:42
  • $\begingroup$ 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? $\endgroup$
    – Tsuyoshi Ito
    Commented Apr 21, 2011 at 14:51

1 Answer 1

Reset to default
13
$\begingroup$

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

Improve this answer
$\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.