Show simple item record

dc.contributor.authorDrange, Pål Grønåseng
dc.contributor.authorFomin, Fedoreng
dc.contributor.authorPilipczuk, Michal Paweleng
dc.contributor.authorVillanger, Yngveeng
dc.date.accessioned2015-03-19T08:14:11Z
dc.date.available2015-03-19T08:14:11Z
dc.date.issued2014-02-19eng
dc.identifier.isbn978-3-939897-65-1en_US
dc.identifier.issn1868-8969en_US
dc.identifier.urihttps://hdl.handle.net/1956/9589
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.language.isoengeng
dc.publisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatiken_US
dc.rightsAttribution CC BYeng
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/eng
dc.subjectedge completioneng
dc.subjectmodificationeng
dc.subjectsubexponential parameterized complexityeng
dc.titleExploring Subexponential Parameterized Complexity of Completion Problemsen_US
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2015-03-13T15:06:27Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villangeren_US
dc.identifier.doihttps://doi.org/10.4230/lipics.stacs.2014.288
dc.identifier.cristin1194527
dc.source.journalLeibniz International Proceedings in Informatics
dc.source.4025
dc.source.pagenumber288-299
dc.relation.projectEU 267959


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution CC BY
Except where otherwise noted, this item's license is described as Attribution CC BY