Approximating Pathwidth for Graphs of Small Treewidth

DOI10.1145/3576044MaRDI QIDQ6075751zbMATH OpenOpenAlexFDO

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

Publication date 23 October 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.00779

zbMATH Keywords

treewidthpathwidth

Mathematics Subject Classification ID

Computer science (68-XX)

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(tsqrtlogt)$. 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^{\prime }$ 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^{\prime }+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.

Cites work

• scientific article; zbMATH DE number 475622 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1107735 (Why is no real title available?)
• scientific article; zbMATH DE number 4121438 (Why is no real title available?)
• scientific article; zbMATH DE number 1870231 (Why is no real title available?)
• A 3-approximation for the pathwidth of Halin graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A polynomial excluded-minor approximation of treedepth
• A simple linear-time algorithm for finding path-decompositions of small width
• Approximation of pathwidth of outerplanar graphs
• Circumference and pathwidth of highly connected graphs
• Complexity of Finding Embeddings in a k-Tree
• Connected Treewidth and Connected Graph Searching
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Fixed-parameter tractability of treewidth and pathwidth
• Graph minors. V. Excluding a planar graph
• Graph theory
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Improved bounds for the excluded-minor approximation of treedepth
• Min Cut is NP-complete for edge weighted trees
• On the pathwidth of chordal graphs
• Polynomial bounds for the grid-minor theorem
• Quickly excluding a forest
• Three results for trees, using mathematical induction
• Towards tight(er) bounds for the excluded grid theorem
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Treewidth of cocomparability graphs and a new order-theoretic parameter

Cited in

(8)

• Comparing width parameters on graph classes
• Approximating the treewidth of AT-free graphs.
• Approximation algorithms for treewidth, pathwidth, and treedepth -- a short survey
• Shortest path queries in digraphs of small treewidth
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• An approximation algorithm for zero forcing
• Induced subgraphs and tree decompositions. XVI: Complete bipartite induced minors
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms

This page was built for publication: Approximating Pathwidth for Graphs of Small Treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075751)