13
$\begingroup$

I am looking for an implementation of an algorithm to compute the pathwidth of a graph. It is well known that computing the pathwidth is equivalent to computing the node searching number, vertex separation number, or interval thickness of the graph. The algorithm does not have to be very fast; I want to run it on graphs of at most 20 vertices. I do require the algorithm to compute the pathwidth exactly, rather than giving an approximation.

I am aware that there are some implementations to compute the treewidth of a graph (a related concept) but have not been able to find any to compute the pathwidth. Any pointers are appreciated!

Improve this question
$\endgroup$
8
$\begingroup$

A simple DFS+DP implementation was added to SAGE 4.8 last year: sage.graphs.graph_decompositions.vertex_separation.path_decomposition

It's implemented in Cython (GNU GPL) here and here. Very simple and short if you ignore everything nonessential. $O(n\omega 2^n)$ time where $\omega = pw(G)$. It could be sped up with pruning rules, and particularly a heuristic.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Wouaaaaaaaaahhhh !! How did you learn that it was added to Sage ? Nice to see people actually look what Sage's new features are :-) $\endgroup$
    – Nathann Cohen
    May 30 '12 at 18:59
  • $\begingroup$ By the way the module's documentation is just there, and explains how it all works : sagemath.org/doc/reference/sage/graphs/graph_decompositions/… $\endgroup$
    – Nathann Cohen
    May 30 '12 at 19:01
  • $\begingroup$ Sorry to disappoint, but I'm not actually a SAGE user; Google found your patch contributing it. I would contribute to SAGE (I already use Cython), but I feel like it would be better to contribute to upstream projects (NetworkX?) where more people can make use of it. $\endgroup$
    – Ralph Versteegen
    May 31 '12 at 21:18
  • $\begingroup$ Well. NetworkX is not really "upstream" of Sage anymore, as it does not really use NetworkX much unless you ask for it. And being able to use other parts of maths, Cython and the interface with linear programming makes a difference too :-P $\endgroup$
    – Nathann Cohen
    Jul 29 '13 at 7:32
8
$\begingroup$

Don't know about "an implementation" but check out

Computing Pathwidth Faster Than 2^n Karol Suchan and Yngve Villanger Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009,Copenhagen, Denmark, Springer Verlag, Lecture Notes in Computer Science 5917, Pages 324-335.

Improve this answer
$\endgroup$
2
$\begingroup$

Hisao Tamaki recently devised an exact algorithm for directed pathwidth (WG 2011). There he refers to some successful practical application of his approach (ISCIT 2010), so I guess he also has an implementation of the algorithm.

Hisao Tamaki: A directed path-decomposition approach to exactly identifying attractors of boolean networks. International Symposium on Communications and Information Technologies (ISCIT 2010), pp. 844-849

Hisao Tamaki: A Polynomial Time Algorithm for Bounded Directed Pathwidth. In: 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), LNCS 6986, pp. 331-342.

Improve this answer
$\endgroup$

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.