Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Finding large induced sparse subgraphs in C>t -free graphs in quasipolynomial time

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:52:07Z
dc.abstract.enFor an integer t, a graph G is called C>t-free if G does not contain any induced cycle on more than t vertices. We prove the following statement: for every pair of integers d and t and a statement φ, there exists an algorithm that, given an n-vertex C>t-free graph G with weights on vertices, finds in time n(log3 n) a maximum-weight vertex subset S such that G[S] has degeneracy at most d and satisfies φ. The running time can be improved to n(log2 n) assuming G is Pt-free, that is, G does not contain an induced path on t vertices. This expands the recent results of the authors [FOCS 2020 and SOSA 2021] on the Maximum Weight Independent Set problem on Pt-free graphs in two directions: by encompassing the more general setting of C>t-free graphs, and by being applicable to a much wider variety of problems, such as Maximum Weight Induced Forest or Maximum Weight Induced Planar Graph.
dc.abstract.plW pracy rozważamy problem znajdowania największego podgrafu o ograniczonej degeneracji, spełniającego zadaną formułę CMSO2. Pokazujemy, że problem ten da się rozwiązać w czasu quasiwielomianowym w klasie grafów bez indukowanych cykli długości większej niż t.[CR][LF]Implikuje to quasiwielomianowe algorytmy dla klasycznych problemów, w tym największego zbioru niezależnego czy najmniejszego zbioru przecinającego wszystkie cykle.
dc.affiliationUniwersytet Warszawski
dc.conference.countryWłochy
dc.conference.datefinish2021-06-25
dc.conference.datestart2021-06-21
dc.conference.placeVirtual
dc.conference.seriesACM Symposium on Theory of Computing
dc.conference.seriesACM Symposium on Theory of Computing
dc.conference.seriesshortcutSTOC
dc.conference.shortcutSTOC 2021
dc.conference.weblinkhttp://acm-stoc.org/stoc2021/
dc.contributor.authorRzążewski, Paweł
dc.contributor.authorGartland, Peter
dc.contributor.authorLokshtanov, Daniel
dc.contributor.authorPilipczuk, Marcin
dc.contributor.authorPilipczuk, Michał
dc.date.accessioned2024-01-25T00:40:53Z
dc.date.available2024-01-25T00:40:53Z
dc.date.copyright2021-06-15
dc.date.issued2021
dc.description.accesstimeAT_PUBLICATION
dc.description.financePublikacja bezkosztowa
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.1145/3406325.3451034
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/107160
dc.identifier.weblinkhttps://dl.acm.org/doi/10.1145/3406325.3451034
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages330–341
dc.rightsCC-BY
dc.sciencecloudnosend
dc.subject.enindependent set
dc.subject.enfeedback vertex set
dc.subject.enPt-free graphs
dc.subject.enC>t-free graphs
dc.subject.plFinding large induced sparse subgraphs in C>t -free graphs in quasipolynomial time
dc.titleFinding large induced sparse subgraphs in C>t -free graphs in quasipolynomial time
dc.typeJournalArticle
dspace.entity.typePublication