Solving Partial Dominating Set and Related Problems Using Twin-Width
| Autoři | |
|---|---|
| Rok publikování | 2025 |
| Druh | Článek ve sborníku |
| Konference | 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Klíčová slova | Partial Dominating Set; Partial Vertex Cover; meta-algorithm; counting logic; twin-width |
| Popis | 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 \phi\equiv\exists x_1\cdots \exists x_k \sum_{i\in I} \#y\,\psi_i(x_1,\ldots,x_k,y)\ge t$, where $\psi_i$ is a quantifier-free formula for each $i \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. |
| Související projekty: |