Residue Domination in Bounded-Treewidth Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909603181101056 |
|---|---|
| author | Greilhuber, Jakob Schepper, Philipp Wellnitz, Philip |
| author_facet | Greilhuber, Jakob Schepper, Philipp Wellnitz, Philip |
| contents | For the vertex selection problem $(σ,ρ)$-DomSet one is given two fixed sets $σ$ and $ρ$ of integers and the task is to decide whether we can select vertices of the input graph such that, for every selected vertex, the number of selected neighbors is in $σ$ and, for every unselected vertex, the number of selected neighbors is in $ρ$ [Telle, Nord. J. Comp. 1994]. This framework covers many fundamental graph problems such as Independent Set and Dominating Set.
We significantly extend the recent result by Focke et al. [SODA 2023] to investigate the case when $σ$ and $ρ$ are two (potentially different) residue classes modulo $m\ge 2$. We study the problem parameterized by treewidth and present an algorithm that solves in time $m^{tw} \cdot n^{O(1)}$ the decision, minimization and maximization version of the problem. This significantly improves upon the known algorithms where for the case $m \ge 3$ not even an explicit running time is known. We complement our algorithm by providing matching lower bounds which state that there is no $(m-ε)^{pw} \cdot n^{O(1)}$-time algorithm parameterized by pathwidth $pw$, unless SETH fails. For $m = 2$, we extend these bounds to the minimization version as the decision version is efficiently solvable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_07524 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Residue Domination in Bounded-Treewidth Graphs Greilhuber, Jakob Schepper, Philipp Wellnitz, Philip Data Structures and Algorithms Computational Complexity For the vertex selection problem $(σ,ρ)$-DomSet one is given two fixed sets $σ$ and $ρ$ of integers and the task is to decide whether we can select vertices of the input graph such that, for every selected vertex, the number of selected neighbors is in $σ$ and, for every unselected vertex, the number of selected neighbors is in $ρ$ [Telle, Nord. J. Comp. 1994]. This framework covers many fundamental graph problems such as Independent Set and Dominating Set. We significantly extend the recent result by Focke et al. [SODA 2023] to investigate the case when $σ$ and $ρ$ are two (potentially different) residue classes modulo $m\ge 2$. We study the problem parameterized by treewidth and present an algorithm that solves in time $m^{tw} \cdot n^{O(1)}$ the decision, minimization and maximization version of the problem. This significantly improves upon the known algorithms where for the case $m \ge 3$ not even an explicit running time is known. We complement our algorithm by providing matching lower bounds which state that there is no $(m-ε)^{pw} \cdot n^{O(1)}$-time algorithm parameterized by pathwidth $pw$, unless SETH fails. For $m = 2$, we extend these bounds to the minimization version as the decision version is efficiently solvable. |
| title | Residue Domination in Bounded-Treewidth Graphs |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2403.07524 |