Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter 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]. Cited in 13 Documents 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 \textit{J. Kneis} et al., Lect. Notes Comput. Sci. 3787, 385--396 (2005; Zbl 1171.05428) Full Text: DOI