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

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs

Uproszczony widok
dc.abstract.enLet C and D be hereditary graph classes. Consider the following problem: given a graph G∈ D, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C. We prove that it can be solved in 2 o(n) time, where n is the number of vertices of G, if the following conditions are satisfied:the graphs in C are sparse, i.e., they have linearly many edges in terms of the number of vertices;the graphs in D admit balanced separators of size governed by their density, e.g., O(Δ) or O(m), where Δ and m denote the maximum degree and the number of edges, respectively; andthe considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes C and D:a largest induced forest in a Pt-free graph can be found in 2O~(n2/3) time, for every fixed t; anda largest induced planar graph in a string graph can be found in 2O~(n2/3) time.
dc.abstract.plW pracy badamy złożoność problemu znajdowania największego indukowanego podgrafu, należącego do zadanej klasy C. Pokazujemy, że przy pewnych naturalnych założeniach dotyczących instancji wejściowej i klasy C, problem można rozwiązać w czasie podwykładniczym.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorWalczak, Bartosz
dc.contributor.authorLeeuwen, Erik Jan van
dc.contributor.authorRzążewski, Paweł
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorNovotná, Jana
dc.contributor.authorOkrasa, Karolina
dc.date.accessioned2024-01-26T09:20:49Z
dc.date.available2024-01-26T09:20:49Z
dc.date.copyright2020-07-31
dc.date.issued2021
dc.description.accesstimeBEFORE_PUBLICATION
dc.description.financePublikacja bezkosztowa
dc.description.versionORIGINAL_AUTHOR
dc.description.volume83
dc.identifier.doi10.1007/S00453-020-00745-Z
dc.identifier.issn0178-4617
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/121043
dc.identifier.weblinkhttps://link.springer.com/article/10.1007%2Fs00453-020-00745-z
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofAlgorithmica
dc.relation.pages2634–2650
dc.rightsCC-BY
dc.sciencecloudnosend
dc.subject.enSubexponential algorithm
dc.subject.enFeedback vertex set
dc.subject.enPt-free graphs
dc.subject.enString graphs
dc.subject.plAlgorytmy podwykładnicze
dc.subject.plZbiór przecinający wszystkie cykle
dc.subject.plgrafy bez P_t
dc.titleSubexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs
dc.typeJournalArticle
dspace.entity.typePublication