2026-08-25T18:47:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27233 2026-08-25T13:18:18Z ddc:004 open_access

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs Greilhuber, Jakob Marx, Dániel Generalized Dominating Set Partial Domination Treewidth Primal Pathwidth Strong Exponential Time Hypothesis For fixed sets σ, ρ of non-negative integers, the (σ, ρ)-domination framework introduced by Telle [Nord. J. Comput. 1994] captures many classical graph problems. For a graph G, a (σ,ρ)-set is a set S of vertices such that for every v ∈ V(G), we have [(1)] 1) if v ∈ S, then |N(v) ∩ S| ∈ σ, and 2) if v ∉ S, then |N(v) ∩ S| ∈ ρ. Algorithms and lower bounds for the decision, optimization, and counting versions of finding (σ,ρ)-sets on bounded-treewidth graphs were systematically studied [van Rooij et al., ESA 2009][Focke et al., TALG 2025]. We initiate the study of a natural partial variant (σ,ρ)-MinParDomSet of the problem, in which the constraints given by σ, ρ need not be fulfilled for all vertices, but we want to find a set of size at most k that maximizes the number of vertices that are satisfied in the sense that they satisfy (1) and (2) above. Our goal is to understand whether (σ,ρ)-MinParDomSet can be solved in the same running time as the nonpartial version, or whether it is strictly harder. Formally, we consider nonempty finite or simple cofinite sets σ and ρ (simple cofinite sets are of the form ℤ_{≥ c}), and we try to determine the smallest constant c_{σ,ρ} such that there is a c_{σ,ρ}^tw ⋅ n^O(1) time algorithm for the problem if a tree decomposition of width tw is given. We obtain matching upper and lower bounds on c_{σ,ρ} for every such fixed σ and ρ under the Primal Pathwidth Strong Exponential Time Hypothesis, and establish whether the partial problem is harder than the nonpartial variant. For some sets σ and ρ, the more general (σ,ρ)-MinParDomSet has the same complexity as the nonpartial special case (e.g., for Dominating Set), while for other choices, the partial version is significantly harder (e.g., for Perfect Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakob Greilhuber and Dániel Marx 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.97 urn:nbn:de:0030-drops-272330 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.97 eng https://creativecommons.org/licenses/by/4.0/legalcode