Approximating pathwidth for graphs of small treewidth

Prelegent(ci)

Wojciech Nadara

Termin

5 listopada 2020 12:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium "Algorytmika"

---

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.

---