Simple view

Full metadata view

Authors

Statistics

Approximating pathwidth for graphs of small treewidth

treewidth

pathwidth

We describe a polynomial-time algorithm which, given a graph G with treewidth

dc.abstract.en | 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. | pl |

dc.affiliation | Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej | pl |

dc.contributor.author | Groenland, Carla | pl |

dc.contributor.author | Joret, Gwenaël | pl |

dc.contributor.author | Nadara, Wojciech | pl |

dc.contributor.author | Walczak, Bartosz - 114113 | pl |

dc.date.accessioned | 2023-03-24T08:38:54Z | |

dc.date.available | 2023-03-24T08:38:54Z | |

dc.date.issued | 2023 | pl |

dc.date.openaccess | 0 | |

dc.description.accesstime | w momencie opublikowania | |

dc.description.number | 2 | pl |

dc.description.version | ostateczna wersja wydawcy | |

dc.description.volume | 19 | pl |

dc.identifier.articleid | 16 | pl |

dc.identifier.doi | 10.1145/3576044 | pl |

dc.identifier.eissn | 1549-6333 | pl |

dc.identifier.issn | 1549-6325 | pl |

dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/309412 | |

dc.language | eng | pl |

dc.language.container | eng | pl |

dc.rights | Dodaję tylko opis bibliograficzny | * |

dc.rights.licence | OTHER | |

dc.rights.uri | * | |

dc.share.type | otwarte czasopismo | |

dc.subject.en | treewidth | pl |

dc.subject.en | pathwidth | pl |

dc.subtype | Article | pl |

dc.title | Approximating pathwidth for graphs of small treewidth | pl |

dc.title.journal | ACM Transactions on Algorithms | pl |

dc.type | JournalArticle | pl |

dspace.entity.type | Publication |