Vis enkel innførsel

dc.contributor.authorDrange, Pål Grønåseng
dc.contributor.authorFomin, Fedoreng
dc.contributor.authorPilipczuk, Michal Paweleng
dc.contributor.authorVillanger, Yngveeng
dc.descriptionPresented at the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
dc.description.abstractLet F be a family of graphs. In the F-Completion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph from F as an induced subgraph. It appeared recently that special cases of F-Completion, the problem of completing into a chordal graph known as Minimum Fill-in, corresponding to the case of F = {C4,C5,C6, . . .}, and the problem of completing into a split graph, i.e., the case of F = {C4, 2K2,C5}, are solvable in parameterized subexponential time 2O(√ k log k)nO(1). The exploration of this phenomenon is the main motivation for our research on F-Completion. In this paper we prove that completions into several well studied classes of graphs without long induced cycles also admit parameterized subexponential time algorithms by showing that: The problem Trivially Perfect Completion is solvable in parameterized subexponential time 2O(√k log k)nO(1), that is F-Completion for F = {C4, P4}, a cycle and a path on four vertices. The problems known in the literature as Pseudosplit Completion, the case where F = {2K2,C4}, and Threshold Completion, where F = {2K2, P4,C4}, are also solvable in time 2O(√k log k)nO(1). We complement our algorithms for F-Completion with the following lower bounds: For F = {2K2}, F = {C4}, F = {P4}, and F = {2K2, P4}, F-Completion cannot be solved in time 2o(k)nO(1) unless the Exponential Time Hypothesis (ETH) fails. Our upper and lower bounds provide a complete picture of the subexponential parameterized complexity of F-Completion problems for F ⊆ {2K2,C4, P4}.en_US
dc.publisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatiken_US
dc.rightsAttribution CC BYeng
dc.subjectedge completioneng
dc.subjectsubexponential parameterized complexityeng
dc.titleExploring Subexponential Parameterized Complexity of Completion Problemsen_US
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villangeren_US
dc.source.journalLeibniz International Proceedings in Informatics
dc.relation.projectEU 267959

Tilhørende fil(er)


Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution CC BY
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution CC BY