Exploring Subexponential Parameterized Complexity of Completion Problems

Authors Pal Gronas Drange, Fedor V. Fomin, Michal Pilipczuk, Yngve Villanger



PDF
Thumbnail PDF

File

LIPIcs.STACS.2014.288.pdf
  • Filesize: 0.68 MB
  • 12 pages

Document Identifiers

Author Details

Pal Gronas Drange
Fedor V. Fomin
Michal Pilipczuk
Yngve Villanger

Cite AsGet BibTex

Pal Gronas Drange, Fedor V. Fomin, Michal Pilipczuk, and Yngve Villanger. Exploring Subexponential Parameterized Complexity of Completion Problems. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 288-299, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.STACS.2014.288

Abstract

Let 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={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 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, that is F-Completion 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}, F-Completion 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-Completion problems for F contained inside {2K_2,C_4,P_4}.
Keywords
  • edge completion
  • modification
  • subexponential parameterized complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail