The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908891794636800 |
|---|---|
| author | Greilhuber, Jakob Marx, Dániel |
| author_facet | Greilhuber, Jakob Marx, Dániel |
| contents | 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\in V(G)$, we have (1) if $v \in S$, then $|N(v) \cap S| \in σ$, and (2) if $v \notin S$, then $|N(v) \cap S| \in ρ$. 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) or (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 $\mathbb{Z}_{\geq c}$), and we try to determine the smallest constant $c_{σ,ρ}$ such that there is a $c_{σ,ρ}^{tw}\cdot 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01645 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs Greilhuber, Jakob Marx, Dániel Data Structures and Algorithms Computational Complexity 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\in V(G)$, we have (1) if $v \in S$, then $|N(v) \cap S| \in σ$, and (2) if $v \notin S$, then $|N(v) \cap S| \in ρ$. 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) or (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 $\mathbb{Z}_{\geq c}$), and we try to determine the smallest constant $c_{σ,ρ}$ such that there is a $c_{σ,ρ}^{tw}\cdot 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). |
| title | The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2506.01645 |