×

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

Software:

MAX-2-SAT
PDFBibTeX XMLCite
Full Text: DOI