Approximating pathwidth for graphs of small treewidth

Speaker(s)

Wojciech Nadara

Date

Nov. 5, 2020, 12:15 p.m.

Information about the event

online

Seminar

Seminar Algorithms

---

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})$.

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.

---