2026-07-22T18:26:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24120 2025-11-12T13:33:17Z ddc:004 open_access

Solving Partial Dominating Set and Related Problems Using Twin-Width Balabán, Jakub Mock, Daniel Rossmanith, Peter Partial Dominating Set Partial Vertex Cover meta-algorithm counting logic twin-width Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are 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 ϕ≡∃ x₁⋯ ∃ x_k ∑_{α ∈ I} #y ψ_α(x₁,…,x_k,y) ≥ t, where ψ_α is a quantifier-free formula for each α ∈ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Balabán and Daniel Mock and Peter Rossmanith 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.13 urn:nbn:de:0030-drops-241203 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode