# zbMATH — the first resource for mathematics

A bound on the pathwidth of sparse graphs with applications to exact algorithms. (English) Zbl 1219.05187
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})$$.

##### 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
Full Text: