zbMATH — the first resource for mathematics

Algorithms based on the treewidth of sparse graphs. (English) Zbl 1171.05428
Kratsch, Dieter (ed.), Graph-theoretic concepts in computer science. 31st international workshop, WG 2005, Metz, France, June 23–25, 2005. Revised selected papers. Berlin: Springer (ISBN 3-540-31000-2/pbk). Lecture Notes in Computer Science 3787, 385-396 (2005).
Summary: We prove that, given a graph, one can efficiently find a set of no more than $$m/5.217 + 1$$ nodes whose removal yields a partial two-tree. As an application, we immediately get simple algorithms for several problems, including Max-Cut, Max-2-SAT and Max-2-XSAT. All of these take a record-breaking time of $$O^*(2^{m/5.217})$$, where $$m$$ is the number of clauses or edges, while only using polynomial space. Moreover, the existence of the aforementioned node sets implies an upper bound of $$m/5.217 + 3$$ on the treewidth of a graph with $$m$$ edges. Letting go of polynomial space restrictions, this can be improved to a bound of $$m/5.769 + O(\log n)$$ on the pathwidth, leading to algorithms for the above problems that take $$O^*(2^{m /5.769})$$ time.
For the entire collection see [Zbl 1098.68004].

MSC:
 05C85 Graph algorithms (graph-theoretic aspects) 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science
MAX-2-SAT
Full Text: