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.ICALP.2023.27
URN: urn:nbn:de:0030-drops-180798
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18079/
Bodlaender, Hans L. ;
Groenland, Carla ;
Pilipczuk, Michał
Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters
Abstract
We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows:
- Binary CSP parameterized by the vertex cover number is W[3]-complete. More generally, for every positive integer d, Binary CSP parameterized by the size of a modulator to a treedepth-d graph is W[2d+1]-complete. This provides a new family of natural problems that are complete for odd levels of the W-hierarchy.
- We introduce a new complexity class XSLP, defined so that Binary CSP parameterized by treedepth is complete for this class. We provide two equivalent characterizations of XSLP: the first one relates XSLP to a model of an alternating Turing machine with certain restrictions on conondeterminism and space complexity, while the second one links XSLP to the problem of model-checking first-order logic with suitably restricted universal quantification. Interestingly, the proof of the machine characterization of XSLP uses the concept of universal trees, which are prominently featured in the recent work on parity games.
- We describe a new complexity hierarchy sandwiched between the W-hierarchy and the A-hierarchy: For every odd t, we introduce a parameterized complexity class S[t] with W[t] ⊆ S[t] ⊆ A[t], defined using a parameter that interpolates between the vertex cover number and the treedepth. We expect that many of the studied classes will be useful in the future for pinpointing the complexity of various structural parameterizations of graph problems.
BibTeX - Entry
@InProceedings{bodlaender_et_al:LIPIcs.ICALP.2023.27,
author = {Bodlaender, Hans L. and Groenland, Carla and Pilipczuk, Micha{\l}},
title = {{Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {27:1--27:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18079},
URN = {urn:nbn:de:0030-drops-180798},
doi = {10.4230/LIPIcs.ICALP.2023.27},
annote = {Keywords: Parameterized Complexity, Constraint Satisfaction Problems, Binary CSP, List Coloring, Vertex Cover, Treedepth, W-hierarchy}
}
|
Keywords: |
|
Parameterized Complexity, Constraint Satisfaction Problems, Binary CSP, List Coloring, Vertex Cover, Treedepth, W-hierarchy |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
