World's most popular travel blog for travel bloggers.

[Solved]: Tree decomposition - Fastest algorithm in practise

, , No Comments
Problem Detail: 

I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph.

I found the paper "A linear time algorithm for finding tree-decompositions of small treewidth" [1] by Hans L. Bodlaender which return a tree-decompsiton with the optimized tree-width and as the name says, the algorithm runs in linear time but since there are no (translation: I have not found ) any implementations, I am not sure if it's being used in practice or not.

Is the paper by Hans L. used in practice or does the constant factor make the algorithm useless?

[1] http://dl.acm.org/citation.cfm?id=167161

[2] http://www.treewidth.com/docs/libtw.pdf

Edit: Linked http://math.stackexchange.com/questions/1246421/tree-decomposition-by-hand-for-understanding

Asked By : Niclas Jonsson

Answered By : Luke Mathieson

The first caveat is that deciding whether the treewidth of a graph is at most $t$ is NP-complete, but it is FPT (which is what Bodlaender's paper shows). So for small $t$, we can (in principle) solve the problem exactly (and actually spit out the decomposition as well), but for graphs with large treewidth, then things can get a bit slow.

Having said that, you're right, the hidden constants in Bodlaender's algorithm are prohibitive, but there are more practical ways of getting at least a good tree decomposition. A useful place to start is with another of Bodlaender's papers, "A tourist guide to treewidth", which is now a bit old, but still has some valuable information and references to algorithms for generating tree decompositions, particularly in various restricted graph classes (sometimes the algorithms work in general, you just don't get a nice upper bound on the running time outside of the restricted class). John Fouhy's master's thesis "Computational experiments on graph width metrics" includes a number of way of obtaining tree decompositions (you can find it here under the link "John's thesis").

Probably most useful though is if you can get a copy of Downey and Fellow's new book "Fundamentals of Parameterized Complexity" (Springer, 2013), in which they devote Chapter 11 to heuristics for finding tree decompositions. This is probably the most recent survey in covering this material. They also note that the handful of attempts at implementing Bodlaender's algorithm have not been successful because it was impractically slow, so your lack of success in finding implementations is no coincidence. Bodlaender's algorithm works via recursive application of an FPT algorithm, the problem being that the recursion depth depends on the treewidth, (checking Downey & Fellows, the recursive depth is $O(t^8)$) which just becomes too prohibitively slow too quickly.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41651

0 comments:

Post a Comment

Let us know your responses and feedback