Solving Partial Dominating Set and Related Problems Using Twin-Width

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BALABÁN Jakub MOCK Daniel ROSSMANITH Peter

Year of publication 2025
Type Article in Proceedings
Conference 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)
MU Faculty or unit

Faculty of Informatics

Citation
Keywords Partial Dominating Set; Partial Vertex Cover; meta-algorithm; counting logic; twin-width
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info