A bound on the pathwidth of sparse graphs with applications to exact algorithms. (English) Zbl 1219.05187

Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter

SIAM J. Discrete Math. 23, No. 1, 407-427 (2009).

The authors resented a bound of \(m/5.769+O(\log n)\) on the pathwidth of graphs with \(m\) edges. Respective path decompositions can be computed in polynomial time. Using a well-known framework for algorithms that rely on tree decompositions, this directly leads to runtime bounds of \(O^*(2^{m/5.769})\) for Max-2SAT and Max-Cut. Both algorithms require exponential space due to dynamic programming. If we agree to accept a slightly larger bound of \(m/5.217+3\), we even obtain path decompositions with a rather simple structure: all bags share a large set of common nodes. Using branching based algorithms it may be possible to solve the same problems in polynomial space and time \(O^*(2^{m/5.217})\).

Reviewer: I. M. Erusalimskiy (Rostov-on-Don)

MSC:

05C85	Graph algorithms (graph-theoretic aspects)
68R10	Graph theory (including graph drawing) in computer science
68W01	General topics in the theory of algorithms

Keywords:

graph algorithms; graph theory; algorithm; pathwidth