Approximating pathwidth for graphs of small treewidth
| Autor: | Groenland, Carla, Joret, Gwenaël, Nadara, Wojciech, Walczak, Bartosz |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | ACM Transactions on Algorithms, 19/2:1--19, 2023 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1145/3576044 |
| Popis: | We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$, approximates the pathwidth of $G$ to within a ratio of $O(t\sqrt{\log t})$. This is the first algorithm to achieve an $f(t)$-approximation for some function $f$. Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least $th+2$ has treewidth at least $t$ or contains a subdivision of a complete binary tree of height $h+1$. The bound $th+2$ is best possible up to a multiplicative constant. This result was motivated by, and implies (with $c=2$), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant $c$ such that every graph with pathwidth $\Omega(k^c)$ has treewidth at least $k$ or contains a subdivision of a complete binary tree of height $k$. Our main technical algorithm takes a graph $G$ and some (not necessarily optimal) tree decomposition of $G$ of width $t'$ in the input, and it computes in polynomial time an integer $h$, a certificate that $G$ has pathwidth at least $h$, and a path decomposition of $G$ of width at most $(t'+1)h+1$. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height $h$. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth. Comment: v4: small changes following further comments from a referee. v3: revised following referees' comments, corrects a serious error in the previous version |
| Databáze: | arXiv |
| Externí odkaz: |
|