2026-07-20T07:27:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4465 2024-03-06T10:35:05Z ddc:004 open_access

Exploring Subexponential Parameterized Complexity of Completion Problems Drange, Pal Gronas Fomin, Fedor V. Pilipczuk, Michal Villanger, Yngve edge completion modification subexponential parameterized complexity 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}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pal Gronas Drange and Fedor V. Fomin and Michal Pilipczuk and Yngve Villanger 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.288 urn:nbn:de:0030-drops-44659 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.288 eng https://creativecommons.org/licenses/by/3.0/legalcode