License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.59
URN: urn:nbn:de:0030-drops-187124
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18712/
Hegerfeld, Falko ;
Kratsch, Stefan
Tight Algorithms for Connectivity Problems Parameterized by Clique-Width
Abstract
The complexity of problems involving global constraints is usually much more difficult to understand than the complexity of problems only involving local constraints. In the realm of graph problems, connectivity constraints are a natural form of global constraints. We study connectivity problems from a fine-grained parameterized perspective. In a breakthrough result, Cygan et al. (TALG 2022) first obtained Monte-Carlo algorithms with single-exponential running time α^{tw} n^?(1) for connectivity problems parameterized by treewidth by introducing the cut-and-count-technique, which reduces many connectivity problems to locally checkable counting problems. Furthermore, the obtained bases α were shown to be optimal under the Strong Exponential-Time Hypothesis (SETH).
However, since only sparse graphs may admit small treewidth, we lack knowledge of the fine-grained complexity of connectivity problems with respect to dense structure. The most popular graph parameter to measure dense structure is arguably clique-width, which intuitively measures how easily a graph can be constructed by repeatedly adding bicliques. Bergougnoux and Kanté (TCS 2019) have shown, using the rank-based approach, that also parameterized by clique-width many connectivity problems admit single-exponential algorithms. Unfortunately, the obtained running times are far from optimal under SETH.
We show how to obtain optimal running times parameterized by clique-width for two benchmark connectivity problems, namely Connected Vertex Cover and Connected Dominating Set. These are the first tight results for connectivity problems with respect to clique-width and these results are obtained by developing new algorithms based on the cut-and-count-technique and novel lower bound constructions. Precisely, we show that there exist one-sided error Monte-Carlo algorithms that given a k-clique-expression solve
- Connected Vertex Cover in time 6^k n^?(1), and
- Connected Dominating Set in time 5^k n^?(1).
Both results are shown to be tight under SETH.
BibTeX - Entry
@InProceedings{hegerfeld_et_al:LIPIcs.ESA.2023.59,
author = {Hegerfeld, Falko and Kratsch, Stefan},
title = {{Tight Algorithms for Connectivity Problems Parameterized by Clique-Width}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {59:1--59:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18712},
URN = {urn:nbn:de:0030-drops-187124},
doi = {10.4230/LIPIcs.ESA.2023.59},
annote = {Keywords: Parameterized Complexity, Connectivity, Clique-width, Cut\&Count, Lower Bound}
}
|
Keywords: |
|
Parameterized Complexity, Connectivity, Clique-width, Cut&Count, Lower Bound |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
