Hegerfeld, Falko ;
Kratsch, Stefan
Towards Exact Structural Thresholds for Parameterized Complexity
Abstract
Parameterized complexity seeks to optimally use input structure to obtain faster algorithms for NPhard problems. This has been most successful for graphs of low treewidth, i.e., graphs decomposable by small separators: Many problems admit fast algorithms relative to treewidth and many of them are optimal under the Strong ExponentialTime Hypothesis (SETH). Fewer such results are known for more general structure such as low cliquewidth (decomposition by large and dense but structured separators) and more restrictive structure such as low deletion distance to some sparse graph class.
Despite these successes, such results remain "islands" within the realm of possible structure. Rather than adding more islands, we seek to determine the transitions between them, that is, we aim for structural thresholds where the complexity increases as input structure becomes more general. Going from deletion distance to treewidth, is a single deletion set to a graph with simple components enough to yield the same lower bound as for treewidth or does it take many disjoint separators? Going from treewidth to cliquewidth, how much more density entails the same complexity as cliquewidth? Conversely, what is the most restrictive structure that yields the same lower bound?
For treewidth, we obtain both refined and new lower bounds that apply already to graphs with a single separator X such that GX has treewidth at most r = 𝒪(1), while G has treewidth X+𝒪(1). We rule out algorithms running in time 𝒪^*((r+1ε)^k) for Deletion to rColorable parameterized by k = X; this implies the same lower bound relative to treedepth and (hence) also to treewidth. It specializes to 𝒪^*((3ε)^k) for Odd Cycle Transversal where tw(GX) ≤ r = 2 is best possible. For cliquewidth, an extended version of the above reduction rules out time 𝒪^*((4ε)^k), where X is allowed to be a possibly large separator consisting of k (true) twinclasses, while the treewidth of G  X remains r; this is proved also for the more general Deletion to rColorable and it implies the same lower bound relative to cliquewidth. Further results complement what is known for Vertex Cover, Dominating Set and Maximum Cut. All lower bounds are matched by existing and newly designed algorithms.
BibTeX  Entry
@InProceedings{hegerfeld_et_al:LIPIcs.IPEC.2022.17,
author = {Hegerfeld, Falko and Kratsch, Stefan},
title = {{Towards Exact Structural Thresholds for Parameterized Complexity}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {17:117:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772600},
ISSN = {18688969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17373},
URN = {urn:nbn:de:0030drops173734},
doi = {10.4230/LIPIcs.IPEC.2022.17},
annote = {Keywords: Parameterized complexity, lower bound, vertex cover, odd cycle transversal, SETH, modulator, treedepth, cliquewidth}
}
14.12.2022
Keywords: 

Parameterized complexity, lower bound, vertex cover, odd cycle transversal, SETH, modulator, treedepth, cliquewidth 
Seminar: 

17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Issue date: 

2022 
Date of publication: 

14.12.2022 