Approximating pathwidth for graphs of small treewidth

2023
journal article
article
4
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.rights.uri*
dc.share.typeotwarte czasopismo
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.rights.uri*
dc.share.type
otwarte czasopismo
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
1
Views per month
Views per city
Warsaw
1

No access

No Thumbnail Available