Exploring the Subexponential Complexity of Completion Problems
| Autor: | Michał Pilipczuk, Fedor V. Fomin, Yngve Villanger, Pål Grønås Drange |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | ACM Transactions on Computation Theory. 7:1-38 |
| ISSN: | 1942-3462 1942-3454 |
| DOI: | 10.1145/2799640 |
| Popis: | Let F be a family of graphs. In the F -C ompletion 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 was shown recently that two special cases of F -C ompletion , namely, (i) the problem of completing into a chordal graph known as M inimum F ill-in (SIAM J. Comput. 2013), which corresponds to the case of F ={ C 4 , C 5 , C 6 , …}, and (ii) the problem of completing into a split graph (Algorithmica 2015), that is, the case of F ={ C 4 , 2 K 2 , C 5 }, are solvable in parameterized subexponential time 2 O (√ k log k ) n O (1) . The exploration of this phenomenon is the main motivation for our research on F -C ompletion . In this article, we prove that completions into several well-studied classes of graphs without long induced cycles and paths also admit parameterized subexponential time algorithms by showing that: —The problem T rivially P erfect C ompletion , which is F - C ompletion for F ={ C 4 , P 4 }, a cycle and a path on four vertices, is solvable in parameterized subexponential time 2 O (√ k log k ) n O (1) . —The problems known in the literature as P seudosplit C ompletion , the case in which F{2 K 2 , C 4 }, and T hreshold C ompletion , in which F =2 K 2 , P 4 , C 4 }, are also solvable in time 2 O (√ k log k ) n O }(1) . We complement our algorithms for F -C ompletion with the following lower bounds: —For F ={2 K 2 }, F = { C 4 }, F ={ P o 4 }, and F ={2 K 2 , P 4 }, F -C ompletion 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 F -C ompletion problems for any F ⊆ {2 K 2 , C 4 , P 4 }. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|