Back
Induced subgraphs of bounded treewidth and the container method
Authors:
- Tara Abrishami,
- Maria Chudnovsky,
- Marcin Pilipczuk,
- Paweł Rzążewski,
- Paul Seymour
Abstract
A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By Pt we denote a path on t vertices. In this paper we give polynomial-time algorithms for the following problems: • the Maximum Weight Independent Set problem in long-hole-free graphs, and • the Feedback Vertex Set problem in P5-free graphs
- Record ID
- WUTc47acbcc1ded4a61964cfa16f3744154
- Author
- Pages
- 1948-1964
- Publication size in sheets
- 0.80
- Book
- Marx Dániel Dániel Marx (eds.): Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021, Society for Industrial and Applied Mathematics, ISBN 978-1-61197-646-5. DOI:10.1137/1.9781611976465 Opening in a new tab
- Keywords in Polish
- zbiór niezależny, zbió przecinający wszystkie cykle, grafy P5-wolne
- Keywords in English
- independent set, feedback vertex set, P5-free graphs
- Abstract in Polish
- W pracy pokazujemy, że wiele naturalnych problemów, w tym problem największego zbioru niezależnego czy problem najmniejszego zbioru przecinającego wszystkie cykle, można rozwiązać w czasie wielomianowym w grafach, które nie zawierają indukowanej ścieżki o 5 wierzchołkach oraz w grafach, które nie zawierają indukowanego cyklu o co najmniej 5 wierzchołkach.
- DOI
- DOI:10.1137/1.9781611976465.116 Opening in a new tab
- URL
- https://epubs.siam.org/doi/10.1137/1.9781611976465.116 Opening in a new tab
- Language
- eng (en) English
- Score (nominal)
- 200
- Score source
- conferenceList
- Score
- = 200.0, 05-05-2022, ChapterFromConference
Share
- Uniform Resource Identifier
- https://repo.pw.edu.pl/info/article/WUTc47acbcc1ded4a61964cfa16f3744154/
- URN
urn:pw-repo:WUTc47acbcc1ded4a61964cfa16f3744154
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.