Access the full text.
Sign up today, get DeepDyve free for 14 days.
Loading next page...
/lp/association-for-computing-machinery/approximating-pathwidth-for-graphs-of-small-treewidth-E5FIilXkkC
References (42)
-
B. Monien, I. Sudborough (1988)
Min cut is NP-complete for edge weighted treesTheoretical Computer Science, 58
-
T. Kloks, H. Bodlaender, H. Müller, D. Kratsch (1993)
Computing Treewidth and Minimum Fill-In: All You Need are the Minimal Separators -
N. Robertson, P. Seymour (1986)
Graph minors. V. Excluding a planar graphJ. Comb. Theory, Ser. B, 41
-
By the induction hypothesis, β ∈ Sub(G − i>k M i ). The fact that v ∈ V (α) ∩ V (β) and Lemma 4.4 (2) yield α ∈ Sub(β) or β ∈ Sub(α) -
W. Horn (1972)
Three Results for Trees, Using Mathematical InductionJournal of Research of the National Bureau of Standards, Section B: Mathematical Sciences
-
(1989)
Die Baumweite von Graphen als ein Maß für die Kompliziertheit algorithmischer Probleme -
If q ∈ V ( T ) and every connected component of G − B q has pathwidth at most ‘ -
[ (1986)
Graph minorsV. Excluding a planar graph. Journal of Combinatorial Theory, 41
-
U. Feige, M. Hajiaghayi, James Lee (2005)
Improved approximation algorithms for minimum-weight vertex separatorsSIAM J. Comput., 38
-
H. Bodlaender (1993)
A linear time algorithm for finding tree-decompositions of small treewidthProceedings of the twenty-fifth annual ACM symposium on Theory of Computing
-
G. Petsko (2011)
DominoesGenome Biology, 12
-
Patrick Bellenbaum, R. Diestel (2002)
Two Short Proofs Concerning Tree-DecompositionsCombinatorics, Probability and Computing, 11
-
(2019)
Graph minors and tree decompositions. Bachelor’s thesis, School of Mathematics, Monash University, Melbourne, 2019 -
K. Kawarabayashi, Benjamin Rossman (2018)
A Polynomial Excluded-Minor Approximation of Treedepth -
C. Chekuri, Julia Chuzhoy (2016)
Polynomial Bounds for the Grid-Minor TheoremJournal of the ACM (JACM), 63
-
(2010)
Graph Theory, volume 173 of Graduate Texts in Mathematics -
[ (1996)
A linear-time algorithm for finding tree-decompositions of small treewidthSIAM J. Comput., 25
-
[ (1993)
Open problemsGraph Structure Theory: Proceedings of a Joint Summer Research Conference on Graph Minors
-
[ (2019)
Graph minors and tree decompositionsBachelor’s thesis. School of Mathematics
-
K. Cattell, M. Dinneen, M. Fellows
Information Processing Letters a Simple Linear-time Algorithm for Finding Path-decompositions of Small Width -
P. Fraigniaud, N. Nisse (2006)
Connected Treewidth and Connected Graph Searching -
M (β, b) = ∅, which is a contradiction. If β ∈ Sub(α), then Lemma 4.8 (1) yields level(β, b) level(α, a), which is again a contradiction -
J. Gustedt (1993)
On the Pathwidth of Chordal GraphsDiscret. Appl. Math., 45
-
S. Khuller (1997)
Open problemsACM SIGACT News, 28
-
A) We set h ( G, b ) = k -
Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk (2019)
Improved bounds for the excluded-minor approximation of treedepth -
(2010)
Graph Theory (4th ed.) -
Julia Chuzhoy, Zihan Tan (2019)
Towards Tight(er) Bounds for the Excluded Grid TheoremJ. Comb. Theory, Ser. B, 146
-
D. Bienstock, N. Robertson, P. Seymour, R. Thomas (1991)
Quickly excluding a forestJ. Comb. Theory, Ser. B, 52
-
[ (2013)
Personal communication(2013).
-
Hans Bodlaendery (1993)
Eecient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs -
For statement (2), let (α, a) be a subproblem with a k > level(α, a). If a = k -
[ (1996)
A simple linear-time algorithm for finding path-decompositions of small widthInformation Processing Letters, 57
-
F. Fomin, D. Thilikos (2004)
A 3-approximation for the pathwidth of Halin graphsJ. Discrete Algorithms, 4
-
H. Bodlaender (2012)
Fixed-Parameter Tractability of Treewidth and Pathwidth -
E. Marshall, D. Wood (2013)
Circumference and Pathwidth of Highly Connected GraphsJournal of Graph Theory, 79
-
F. Fomin, H. Bodlaender (2001)
Approximation of pathwidth of outerplanar graphs -
M. Habib, R. Möhring (1994)
Treewidth of cocomparability graphs and a new order-theoretic parameterOrder, 11
-
H. Bodlaender, T. Kloks (1993)
Efficient and Constructive Algorithms for the Pathwidth and Treewidth of GraphsJ. Algorithms, 21
-
P. Heggernes (2016)
Graph-Theoretic Concepts in Computer Science, 9941
-
S. Arnborg, D. Corneil, A. Proskurowski (1987)
Complexity of finding embeddings in a k -treeSiam Journal on Algebraic and Discrete Methods, 8
-
H. Bodlaender (1993)
A Tourist Guide through TreewidthActa Cybern., 11
- Publisher
- Association for Computing Machinery
- Copyright
- Copyright © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
- ISSN
- 1549-6325
- eISSN
- 1549-6333
- DOI
- 10.1145/3576044
- Publisher site
- See Article on Publisher Site
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\sqrt {\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.
Journal
ACM Transactions on Algorithms (TALG) – Association for Computing Machinery
Published: Mar 9, 2023
Keywords: Treewidth