TY - JOUR
T1 - Approximating Pathwidth for Graphs of Small Treewidth
AU - Groenland, Carla
AU - Joret, Gwenaël
AU - Nadara, Wojciech
AU - Walczak, Bartosz
PY - 2023
Y1 - 2023
N2 - We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of (t√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 ω(kc) 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.
AB - We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of (t√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 ω(kc) 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.
KW - pathwidth
KW - Treewidth
UR - http://www.scopus.com/inward/record.url?scp=85159174361&partnerID=8YFLogxK
U2 - 10.1145/3576044
DO - 10.1145/3576044
M3 - Article
AN - SCOPUS:85159174361
SN - 1549-6325
VL - 19
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 2
M1 - 16
ER -