Approximating pathwidth for graphs of small treewidth

2023
journal article
article
10
dc.abstract.enWe 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 $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.pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.contributor.authorGroenland, Carlapl
dc.contributor.authorJoret, Gwenaëlpl
dc.contributor.authorNadara, Wojciechpl
dc.contributor.authorWalczak, Bartosz - 114113 pl
dc.date.accessioned2023-03-24T08:38:54Z
dc.date.available2023-03-24T08:38:54Z
dc.date.issued2023pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number2pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume19pl
dc.identifier.articleid16pl
dc.identifier.doi10.1145/3576044pl
dc.identifier.eissn1549-6333pl
dc.identifier.issn1549-6325pl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/309412
dc.languageengpl
dc.language.containerengpl
dc.rightsDodaję tylko opis bibliograficzny*
dc.rights.licenceInna otwarta licencja
dc.share.typeotwarte czasopismo
dc.source.integratorfalse
dc.subject.entreewidthpl
dc.subject.enpathwidthpl
dc.subtypeArticlepl
dc.titleApproximating pathwidth for graphs of small treewidthpl
dc.title.journalACM Transactions on Algorithmspl
dc.typeJournalArticlepl
dspace.entity.typePublication
dc.abstract.enpl
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 $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.
dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.contributor.authorpl
Groenland, Carla
dc.contributor.authorpl
Joret, Gwenaël
dc.contributor.authorpl
Nadara, Wojciech
dc.contributor.authorpl
Walczak, Bartosz - 114113
dc.date.accessioned
2023-03-24T08:38:54Z
dc.date.available
2023-03-24T08:38:54Z
dc.date.issuedpl
2023
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.numberpl
2
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
19
dc.identifier.articleidpl
16
dc.identifier.doipl
10.1145/3576044
dc.identifier.eissnpl
1549-6333
dc.identifier.issnpl
1549-6325
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/309412
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights*
Dodaję tylko opis bibliograficzny
dc.rights.licence
Inna otwarta licencja
dc.share.type
otwarte czasopismo
dc.source.integrator
false
dc.subject.enpl
treewidth
dc.subject.enpl
pathwidth
dc.subtypepl
Article
dc.titlepl
Approximating pathwidth for graphs of small treewidth
dc.title.journalpl
ACM Transactions on Algorithms
dc.typepl
JournalArticle
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
2
Views per month
Views per city
Warsaw
1
Wroclaw
1

No access

No Thumbnail Available