Solving Partial Dominating Set and Related Problems Using Twin-Width
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915363483025408 |
|---|---|
| author | Balabán, Jakub Mock, Daniel Rossmanith, Peter |
| author_facet | Balabán, Jakub Mock, Daniel Rossmanith, Peter |
| contents | Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are $\rm W[1]$-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form $ϕ\equiv\exists x_1\cdots \exists x_k \sum_{α\in I} \#y\,ψ_α(x_1,\ldots,x_k,y)\ge t$, where $ψ_α$ is a quantifier-free formula for each $α\in I$, $t$ is an arbitrary number, and $\#y$ is a counting quantifier, can be evaluated in time $f(d,k)n$, where $n$ is the number of vertices and $d$ is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_18218 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Solving Partial Dominating Set and Related Problems Using Twin-Width Balabán, Jakub Mock, Daniel Rossmanith, Peter Data Structures and Algorithms Discrete Mathematics Logic in Computer Science Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are $\rm W[1]$-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form $ϕ\equiv\exists x_1\cdots \exists x_k \sum_{α\in I} \#y\,ψ_α(x_1,\ldots,x_k,y)\ge t$, where $ψ_α$ is a quantifier-free formula for each $α\in I$, $t$ is an arbitrary number, and $\#y$ is a counting quantifier, can be evaluated in time $f(d,k)n$, where $n$ is the number of vertices and $d$ is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set. |
| title | Solving Partial Dominating Set and Related Problems Using Twin-Width |
| topic | Data Structures and Algorithms Discrete Mathematics Logic in Computer Science |
| url | https://arxiv.org/abs/2504.18218 |