Drange, Pal Gronas ;
Fomin, Fedor V. ;
Pilipczuk, Michal ;
Villanger, Yngve
Exploring Subexponential Parameterized Complexity of Completion Problems
Abstract
Let F be a family of graphs. In the FCompletion problem, we are given an nvertex 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 FCompletion, the problem of completing into a chordal graph known as "Minimum Fillin", corresponding to the case of F={C_4,C_5,C_6,...}, and the problem of completing into a split graph, i.e., the case of F={C_4,2K_2,C_5}, are solvable in parameterized subexponential time. The exploration of this phenomenon is the main motivation for our research on FCompletion.
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, that is FCompletion for F={C_4,P_4}, a cycle and a path on four vertices.
 The problems known in the literature as Pseudosplit Completion, the case where F={2K_2,C_4}, and Threshold Completion, where F={2K_2,P_4,C_4}, are also solvable in subexponential time.
We complement our algorithms for $F$Completion with the following lower bounds:
 For F={2K_2}, F={C_4}, F={P_4}, and F={2K_2,P_4}, FCompletion cannot be solved in time 2^o(k).n^O(1) unless the Exponential Time Hypothesis (ETH) fails.
Our upper and lower bounds provide a complete picture of the subexponential parameterized complexity of FCompletion problems for F contained inside {2K_2,C_4,P_4}.
BibTeX  Entry
@InProceedings{drange_et_al:LIPIcs:2014:4465,
author = {Pal Gronas Drange and Fedor V. Fomin and Michal Pilipczuk and Yngve Villanger},
title = {{Exploring Subexponential Parameterized Complexity of Completion Problems}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {288299},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897651},
ISSN = {18688969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4465},
URN = {urn:nbn:de:0030drops44659},
doi = {10.4230/LIPIcs.STACS.2014.288},
annote = {Keywords: edge completion, modification, subexponential parameterized complexity}
}
2014
Keywords: 

edge completion, modification, subexponential parameterized complexity 
Seminar: 

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Issue date: 

2014 
Date of publication: 

2014 