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

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

<p>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 <a href="http://www.callowbird.com/undergraduate-stuff.html">http://www.callowbird.com/undergraduate-stuff.html</a>, and have a try. (still, it is very very slow on a slightly larger instance)</p>

CC BY-SA 3.0
2013-07-29T21:39:33.300Z
2013-07-29T21:39:33.300Z
Yang Yuan
<p>Here <a href="http://arxiv.org/abs/1304.6321">http://arxiv.org/abs/1304.6321</a> (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. </p>

CC BY-SA 3.0
2013-07-30T17:59:49.773Z
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.
John K.
CC BY-SA 3.0
2013-07-30T12:13:52.000Z
2013-07-30T12:13:52.000Z
M. kanté
<p>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.</p>

<ul>
<li><a href="http://www.treewidth.com/" rel="nofollow">treewidth.com</a> / <a href="http://www.treewidth.com/docs/LibTW.pdf" rel="nofollow">Computing treewidth with Libtw</a> Dijk, Heuvel, Slob</li>
</ul>

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

<ul>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.3586" rel="nofollow">Discovering Treewidth (2005)
by Hans L. Bodlaender</a></li>
</ul>

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

CC BY-SA 3.0
2013-07-30T02:56:50.483Z
2013-08-24T06:42:51.993Z
2013-08-24T06:42:51.993Z
vzn
<p>Sage doesn't know how to compute treewidth exactly but it can give you the pathwidth of small graphs.</p>

<p><a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/vertex_separation.html" rel="nofollow">http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/vertex_separation.html</a></p>

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

<p>Nathann</p>

CC BY-SA 3.0
2013-07-30T17:58:56.707Z
Hey, there's an android app which has a [treewidth](https://github.com/drange/Grapher/blob/master/src/no/uib/ii/algo/st8/algorithms/TreewidthInspector.java) 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)
John K.
CC BY-SA 3.0
2013-07-28T16:20:53.217Z
2013-07-28T16:20:53.217Z
Nathann Cohen
<p>As far as I know, the state of the art is what is reported in</p>

<p>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, <a href="http://dx.doi.org/10.1145/2390176.2390188">doi:10.1145/2390176.2390188</a>.</p>

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

CC BY-SA 3.0
2013-07-28T08:23:43.903Z
Thank you.  References 2, 8 and 15 which give upper and lower bound heuristics might in practice be the most useful from that paper.
Simd
CC BY-SA 3.0
2013-07-27T17:34:09.703Z
2013-07-27T17:34:09.703Z
David Eppstein
<p>I would like to compute the <a href="http://en.wikipedia.org/wiki/Treewidth" rel="nofollow noreferrer">treewidth</a> of a graph. There are really good heuristics for other NP-hard graph problems such as <a href="https://stackoverflow.com/questions/8176298/vf2-algorithm-steps-with-example">VF2</a> for subgraph isomorphism, with code available in <a href="http://igraph.sourceforge.net/" rel="nofollow noreferrer">igraph</a> for example.   I have tried them on my graphs and I find they run very fast for my data.</p>

<p>Are there any fast algorithms for treewidth calculation in a similar vein?  </p>

CC BY-SA 3.0
2013-07-31T16:45:19.033Z
fyi recently treewidth has been connected to [SAT hardness](http://chat.stackexchange.com/transcript/message/10189653#10189653) by Gaspers/Szeider in FOCS, hope to hear from others in that chat/discussion
vzn
<ds.algorithms><graph-algorithms><treewidth><heuristics>
Fast treewidth algorithms
Simd
# Fast treewidth algorithms

(Asked by: username_0 on 2013-07-27)

I would like to compute the [treewidth](http://en.wikipedia.org/wiki/Treewidth) of a graph. There are really good heuristics for other NP-hard graph problems such as [VF2](https://stackoverflow.com/questions/8176298/vf2-algorithm-steps-with-example) for subgraph isomorphism, with code available in [igraph](http://igraph.sourceforge.net/) 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?

**Tags:** ds.algorithms, graph-algorithms, treewidth, heuristics
> **Comments:**
> **username_1**: fyi recently treewidth has been connected to [SAT hardness](http://chat.stackexchange.com/transcript/message/10189653#10189653) by Gaspers/Szeider in FOCS, hope to hear from others in that chat/discussion  

---

## 5 answers

### Answer by username_6 on 2013-07-27. Score: 19 | Accepted answer

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](http://dx.doi.org/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.

> **Comments:**
> **username_0**: Thank you.  References 2, 8 and 15 which give upper and lower bound heuristics might in practice be the most useful from that paper.  

---

### Answer by username_2 on 2013-07-29. Score: 11

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)


---

### Answer by username_3 on 2013-07-30. Score: 5

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.

> **Comments:**
> **username_4**: 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.  

---

### Answer by username_1 on 2013-07-30. Score: 5

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.

* [treewidth.com](http://www.treewidth.com/) / [Computing treewidth with Libtw](http://www.treewidth.com/docs/LibTW.pdf) Dijk, Heuvel, Slob

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

* [Discovering Treewidth (2005)
  by Hans L. Bodlaender](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.3586)

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


---

### Answer by username_5 on 2013-07-28. Score: 3

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

> **Comments:**
> **username_4**: Hey, there's an android app which has a [treewidth](https://github.com/drange/Grapher/blob/master/src/no/uib/ii/algo/st8/algorithms/TreewidthInspector.java) 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)  

---

