Approximations for Fault-Tolerant Total and Partial Positive Influence Domination
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915850835984384 |
|---|---|
| author | Lamprou, Ioannis Sigalas, Ioannis Vaxevanakis, Ioannis Zissimopoulos, Vassilis |
| author_facet | Lamprou, Ioannis Sigalas, Ioannis Vaxevanakis, Ioannis Zissimopoulos, Vassilis |
| contents | In $\textit{total domination}$, given a graph $G=(V,E)$, we seek a minimum-size set of nodes $S\subseteq V$, such that every node in $V$ has at least one neighbor in $S$. We define a $\textit{fault-tolerant}$ version of total domination, where we require any node in $V \setminus S$ to have at least $m$ neighbors in $S$. Let $Δ$ denote the maximum degree in $G$. We prove a first $1 + \ln(Δ+ m - 1)$ approximation for fault-tolerant total domination. We also consider fault-tolerant variants of the weighted $\textit{partial positive influence dominating set}$ problem, where we seek a minimum-size set of nodes $S\subseteq V$, such that every node in $V$ is either a member of $S$ or the sum of weights of its incident edges leading to nodes in $S$ is at least half of the sum of weights over all its incident edges. We prove the first logarithmic approximations for the simple, total, and connected variants of this problem. To prove the result for the connected case, we extend the general approximation framework for non-submodular functions from integer-valued to fractional-valued functions, which we believe is of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12828 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximations for Fault-Tolerant Total and Partial Positive Influence Domination Lamprou, Ioannis Sigalas, Ioannis Vaxevanakis, Ioannis Zissimopoulos, Vassilis Data Structures and Algorithms In $\textit{total domination}$, given a graph $G=(V,E)$, we seek a minimum-size set of nodes $S\subseteq V$, such that every node in $V$ has at least one neighbor in $S$. We define a $\textit{fault-tolerant}$ version of total domination, where we require any node in $V \setminus S$ to have at least $m$ neighbors in $S$. Let $Δ$ denote the maximum degree in $G$. We prove a first $1 + \ln(Δ+ m - 1)$ approximation for fault-tolerant total domination. We also consider fault-tolerant variants of the weighted $\textit{partial positive influence dominating set}$ problem, where we seek a minimum-size set of nodes $S\subseteq V$, such that every node in $V$ is either a member of $S$ or the sum of weights of its incident edges leading to nodes in $S$ is at least half of the sum of weights over all its incident edges. We prove the first logarithmic approximations for the simple, total, and connected variants of this problem. To prove the result for the connected case, we extend the general approximation framework for non-submodular functions from integer-valued to fractional-valued functions, which we believe is of independent interest. |
| title | Approximations for Fault-Tolerant Total and Partial Positive Influence Domination |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.12828 |