Knowledge base: Warsaw University of Technology

Settings and your account

Base of Knowledge
Warsaw University of Technology

You are here:

  • Start
  • Research Outputs
  • Publications
  • Induced subgraphs of bounded treewidth and the container method
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

Metrics

Record ID
WUTc47acbcc1ded4a61964cfa16f3744154
Author
Tara Abrishami Tara Abrishami,, Author's external affiliation: Princeton University, Princeton, NJ 08544
Maria Chudnovsky Maria Chudnovsky,, Author's external affiliation: Princeton University, NJ, USA
Marcin Pilipczuk Marcin Pilipczuk,, Author's external affiliation: University of Warsaw
Paul Seymour Paul Seymour,, Author's external affiliation: Princeton University, Princeton, NJ 08544
Pages
1948-1964
Publication size in sheets
0.80
Book
Marx Dániel Dániel Marx,, Author's external affiliation: CISPA Helmholtz Center for Information Security, Germany (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
Ministerial score = 200.0, 15-06-2021, ChapterFromConference

Cite

RDF
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.

Confirmation
Are you sure?
Report incorrect data on this page