Solving Partial Dominating Set and Related Problems Using Twin-Width

RWTH Publications (RWTH Aachen)

Abstract

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.

Authors 3

1. Jakub Balabán
2. Daniel Mock Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen

3. Peter Rossmanith Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen