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.STACS.2023.14
URN: urn:nbn:de:0030-drops-176667
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17666/
Bojikian, Narek ;
Chekan, Vera ;
Hegerfeld, Falko ;
Kratsch, Stefan
Tight Bounds for Connectivity Problems Parameterized by Cutwidth
Abstract
In this work we start the investigation of tight complexity bounds for connectivity problems parameterized by cutwidth assuming the Strong Exponential-Time Hypothesis (SETH). Van Geffen et al. [Bas A. M. van Geffen et al., 2020] posed this question for Odd Cycle Transversal and Feedback Vertex Set. We answer it for these two and four further problems, namely Connected Vertex Cover, Connected Dominating Set, Steiner Tree, and Connected Odd Cycle Transversal. For the latter two problems it sufficed to prove lower bounds that match the running time inherited from parameterization by treewidth; for the others we provide faster algorithms than relative to treewidth and prove matching lower bounds. For upper bounds we first extend the idea of Groenland et al. [Carla Groenland et al., 2022] to solve what we call coloring-like problems. Such problems are defined by a symmetric matrix M over ?₂ indexed by a set of colors. The goal is to count the number (modulo some prime p) of colorings of a graph such that M has a 1-entry if indexed by the colors of the end-points of any edge. We show that this problem can be solved faster if M has small rank over ?_p. We apply this result to get our upper bounds for CVC and CDS. The upper bounds for OCT and FVS use a subdivision trick to get below the bounds that matrix rank would yield.
BibTeX - Entry
@InProceedings{bojikian_et_al:LIPIcs.STACS.2023.14,
author = {Bojikian, Narek and Chekan, Vera and Hegerfeld, Falko and Kratsch, Stefan},
title = {{Tight Bounds for Connectivity Problems Parameterized by Cutwidth}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {14:1--14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-266-2},
ISSN = {1868-8969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17666},
URN = {urn:nbn:de:0030-drops-176667},
doi = {10.4230/LIPIcs.STACS.2023.14},
annote = {Keywords: Parameterized complexity, connectivity problems, cutwidth}
}
|
Keywords: |
|
Parameterized complexity, connectivity problems, cutwidth |
|
Collection: |
|
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
03.03.2023 |
