Tight Bounds for Connectivity Problems Parameterized by Cutwidth ...
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....
Main Authors: | , , , |
---|---|
Format: | Conference Object |
Language: | English |
Published: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2023
|
Subjects: | |
Online Access: | https://dx.doi.org/10.4230/lipics.stacs.2023.14 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.14 |
id |
ftdatacite:10.4230/lipics.stacs.2023.14 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.4230/lipics.stacs.2023.14 2024-09-15T18:10:19+00:00 Tight Bounds for Connectivity Problems Parameterized by Cutwidth ... Bojikian, Narek Chekan, Vera Hegerfeld, Falko Kratsch, Stefan 2023 application/pdf https://dx.doi.org/10.4230/lipics.stacs.2023.14 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.14 en eng Schloss Dagstuhl – Leibniz-Zentrum für Informatik https://dx.doi.org/10.4230/LIPIcs.STACS.2023 https://dx.doi.org/10.1145/1250790.1250801 https://dx.doi.org/10.1016/j.ic.2014.12.008 https://dx.doi.org/10.48550/arXiv.2212.12385 https://dx.doi.org/10.1007/978-3-031-15914-5_8 https://dx.doi.org/10.1137/1.9781611975031.70 https://dx.doi.org/10.1145/3148227 https://dx.doi.org/10.1109/FOCS.2011.23 https://dx.doi.org/10.4230/LIPIcs.STACS.2022.36 https://dx.doi.org/10.4230/LIPIcs.IPEC.2022.17 https://dx.doi.org/10.1006/jcss.2000.1727 https://dx.doi.org/10.1006/jcss.2001.1774 https://dx.doi.org/10.4230/LIPIcs.ESA.2018.47 https://dx.doi.org/10.1016/0020-0190(92)90234-M https://dx.doi.org/10.1137/19M1280326 https://dx.doi.org/10.1145/3170442 https://dx.doi.org/10.1137/16M1104834 info:eu-repo/semantics/openAccess Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/legalcode cc by 4.0 Parameterized complexity connectivity problems cutwidth Theory of computation → Parameterized complexity and exact algorithms Article ConferencePaper 2023 ftdatacite https://doi.org/10.4230/lipics.stacs.2023.1410.4230/LIPIcs.STACS.202310.1145/1250790.125080110.1016/j.ic.2014.12.00810.48550/arXiv.2212.1238510.1007/978-3-031-15914-5_810.1137/1.9781611975031.7010.1145/314822710.1109/FOCS.2011.2310.4230/LIPIcs.STACS.2022. 2024-08-01T08:59:19Z 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 ... : LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 14:1-14:16 ... Conference Object Groenland DataCite |
institution |
Open Polar |
collection |
DataCite |
op_collection_id |
ftdatacite |
language |
English |
topic |
Parameterized complexity connectivity problems cutwidth Theory of computation → Parameterized complexity and exact algorithms |
spellingShingle |
Parameterized complexity connectivity problems cutwidth Theory of computation → Parameterized complexity and exact algorithms Bojikian, Narek Chekan, Vera Hegerfeld, Falko Kratsch, Stefan Tight Bounds for Connectivity Problems Parameterized by Cutwidth ... |
topic_facet |
Parameterized complexity connectivity problems cutwidth Theory of computation → Parameterized complexity and exact algorithms |
description |
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 ... : LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 14:1-14:16 ... |
format |
Conference Object |
author |
Bojikian, Narek Chekan, Vera Hegerfeld, Falko Kratsch, Stefan |
author_facet |
Bojikian, Narek Chekan, Vera Hegerfeld, Falko Kratsch, Stefan |
author_sort |
Bojikian, Narek |
title |
Tight Bounds for Connectivity Problems Parameterized by Cutwidth ... |
title_short |
Tight Bounds for Connectivity Problems Parameterized by Cutwidth ... |
title_full |
Tight Bounds for Connectivity Problems Parameterized by Cutwidth ... |
title_fullStr |
Tight Bounds for Connectivity Problems Parameterized by Cutwidth ... |
title_full_unstemmed |
Tight Bounds for Connectivity Problems Parameterized by Cutwidth ... |
title_sort |
tight bounds for connectivity problems parameterized by cutwidth ... |
publisher |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
publishDate |
2023 |
url |
https://dx.doi.org/10.4230/lipics.stacs.2023.14 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.14 |
genre |
Groenland |
genre_facet |
Groenland |
op_relation |
https://dx.doi.org/10.4230/LIPIcs.STACS.2023 https://dx.doi.org/10.1145/1250790.1250801 https://dx.doi.org/10.1016/j.ic.2014.12.008 https://dx.doi.org/10.48550/arXiv.2212.12385 https://dx.doi.org/10.1007/978-3-031-15914-5_8 https://dx.doi.org/10.1137/1.9781611975031.70 https://dx.doi.org/10.1145/3148227 https://dx.doi.org/10.1109/FOCS.2011.23 https://dx.doi.org/10.4230/LIPIcs.STACS.2022.36 https://dx.doi.org/10.4230/LIPIcs.IPEC.2022.17 https://dx.doi.org/10.1006/jcss.2000.1727 https://dx.doi.org/10.1006/jcss.2001.1774 https://dx.doi.org/10.4230/LIPIcs.ESA.2018.47 https://dx.doi.org/10.1016/0020-0190(92)90234-M https://dx.doi.org/10.1137/19M1280326 https://dx.doi.org/10.1145/3170442 https://dx.doi.org/10.1137/16M1104834 |
op_rights |
info:eu-repo/semantics/openAccess Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/legalcode cc by 4.0 |
op_doi |
https://doi.org/10.4230/lipics.stacs.2023.1410.4230/LIPIcs.STACS.202310.1145/1250790.125080110.1016/j.ic.2014.12.00810.48550/arXiv.2212.1238510.1007/978-3-031-15914-5_810.1137/1.9781611975031.7010.1145/314822710.1109/FOCS.2011.2310.4230/LIPIcs.STACS.2022. |
_version_ |
1810447895483121664 |