Solving Partial Dominating Set and Related Problems Using Twin-Width

Abstract

Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are $\mathrm{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 $\ddot{I}•\equiv \exists x_1\cdots \exists x_k{\sum }_{\hat{I}\pm \in I}\#y\ddot{I}{ˆ}_{\hat{I}}\pm (x_1,\dots ,x_k,y)\ge t$, where $\ddot{I}{ˆ}_{\hat{I}}\pm$ is a quantifier-free formula for each $\hat{I}\pm \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.