18
$\begingroup$

I would like to compute the treewidth of a graph. There are really good heuristics for other NP-hard graph problems such as VF2 for subgraph isomorphism, with code available in igraph for example. I have tried them on my graphs and I find they run very fast for my data.

Are there any fast algorithms for treewidth calculation in a similar vein?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ fyi recently treewidth has been connected to SAT hardness by Gaspers/Szeider in FOCS, hope to hear from others in that chat/discussion $\endgroup$ – vzn Jul 31 '13 at 16:45
19
$\begingroup$

As far as I know, the state of the art is what is reported in

Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos (2012), "On exact algorithms for treewidth", ACM Transactions on Algorithms 9 (1): A12, doi:10.1145/2390176.2390188.

The methods described there include an implemented $O^*(2^n)$ algorithm with some heuristic optimizations to make it faster in practice.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Thank you. References 2, 8 and 15 which give upper and lower bound heuristics might in practice be the most useful from that paper. $\endgroup$ – felix Jul 28 '13 at 8:23
10
$\begingroup$

I wrote a paper called A Fast Parallel Branch and Bound Algorithm for Treewidth, in ICTAI 2011. It can compute treewidth in multi-core. I used lots of heuristics and spent lots of time refining the program.

I was a random undergraduate student in China and didn't make it to a good conference. But based on my experiment results, I think my program is very fast. I solved many unsolved benchmarks in Treewidth lib, and my program was 40 times faster than a algorithm proposed by Zhou and Hansen in IJCAI 09..

I'm not working on this topic any more. But if my previous work is helpful, you can download my program (src and exe) from http://www.callowbird.com/undergraduate-stuff.html, and have a try. (still, it is very very slow on a slightly larger instance)

|cite|improve this answer
$\endgroup$
5
$\begingroup$

Here http://arxiv.org/abs/1304.6321 (accepted at FOCS this year) Bodlaender et al. give an $O^*(2^k)$ algorithm that gives a tree-decomposition of width at most 5k+4 if the graph has tree-width at most k. May be it can interest you.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ The algorithm runs in $2^{O(k)}$, or $O(c^k n)$ time. That $c$ is quite nasty, so this paper doesn't really give an implementable algorithm. $\endgroup$ – Pål GD Jul 30 '13 at 17:59
5
$\begingroup$

Here are two surveys on algorithms for calculating treewidth that may be helpful. The first one has empirical comparisons, and it has miscellaneous algorithms implemented as a Java library.

There are many algorithms to compute an upperbound, a lowerbound or the exact treewidth of a graph. We have implemented a lot of upperbound and lowerbound heuristics and two exact algorithms (a Dynamic Programming and a Branch and Bound algorithm). This report compares the different kind of algorithms and shows that some algorithms are preferred.

Treewidth is a graph parameter with several interesting theoretical and practical applications. This survey reviews algorithmic results on determining the treewidth of a given graph, and finding a tree decomposition of small width. Both theoretical results, establishing the asymptotic computational complexity of the problem, as experimental work on heuristics (both for upper bounds as for lower bounds), preprocessing, exact algorithms, and postprocessing are discussed.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

Sage doesn't know how to compute treewidth exactly but it can give you the pathwidth of small graphs.

http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/vertex_separation.html

I would be verrryyyyyyyy glad to learn that there is anything implemented and public to compute tree-decompositions, though :-)

Nathann

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Hey, there's an android app which has a treewidth tester. The code can be rewritten to have it give a decomposition, but currently it only tests whether the treewidth is at most some given $k$. (warning: I am one of the developers) $\endgroup$ – Pål GD Jul 30 '13 at 17:58

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.