Approximating pathwidth for graphs of small treewidth

Carla Groenland*, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

5 Citations (Scopus)

Abstract

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√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 t0 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 (t0 + 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.

Original languageEnglish
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery (ACM)
Pages1965-1976
Number of pages12
ISBN (Electronic)9781611976465
Publication statusPublished - 2021
Externally publishedYes
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: 10 Jan 202113 Jan 2021

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Country/TerritoryUnited States
CityAlexandria, Virtual
Period10/01/2113/01/21

Fingerprint

Dive into the research topics of 'Approximating pathwidth for graphs of small treewidth'. Together they form a unique fingerprint.

Cite this