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. posed this question for odd cycle transversal and feedback vertex set. We answer it for these two and four...
Main Authors: | , , , |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2022
|
Subjects: | |
Online Access: | http://arxiv.org/abs/2212.12385 |
id |
ftarxivpreprints:oai:arXiv.org:2212.12385 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:2212.12385 2023-09-05T13:19:58+02:00 Tight Bounds for Connectivity Problems Parameterized by Cutwidth Bojikian, Narek Chekan, Vera Hegerfeld, Falko Kratsch, Stefan 2022-12-23 http://arxiv.org/abs/2212.12385 unknown http://arxiv.org/abs/2212.12385 Computer Science - Data Structures and Algorithms 05C85 text 2022 ftarxivpreprints 2023-08-16T17:27:43Z 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. 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 domintaing 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.~[STACS~2022] to solve what we call coloring-like problem. Such problems are defined by a symmetric matrix $M$ over $\mathbb{F}_2$ 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 $\mathbb{F}_p$. We apply this result to get our upper bounds for connected vertex cover and connected dominating set. The upper bounds for odd cycle transversal and feedback vertex set use a subdivision trick to get below the bounds that matrix rank would yield. Comment: 77 pages, 17 figures; accepted at STACS 2023 Text Groenland ArXiv.org (Cornell University Library) |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Computer Science - Data Structures and Algorithms 05C85 |
spellingShingle |
Computer Science - Data Structures and Algorithms 05C85 Bojikian, Narek Chekan, Vera Hegerfeld, Falko Kratsch, Stefan Tight Bounds for Connectivity Problems Parameterized by Cutwidth |
topic_facet |
Computer Science - Data Structures and Algorithms 05C85 |
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. 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 domintaing 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.~[STACS~2022] to solve what we call coloring-like problem. Such problems are defined by a symmetric matrix $M$ over $\mathbb{F}_2$ 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 $\mathbb{F}_p$. We apply this result to get our upper bounds for connected vertex cover and connected dominating set. The upper bounds for odd cycle transversal and feedback vertex set use a subdivision trick to get below the bounds that matrix rank would yield. Comment: 77 pages, 17 figures; accepted at STACS 2023 |
format |
Text |
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 |
publishDate |
2022 |
url |
http://arxiv.org/abs/2212.12385 |
genre |
Groenland |
genre_facet |
Groenland |
op_relation |
http://arxiv.org/abs/2212.12385 |
_version_ |
1776200731413446656 |