Ioannis Lamprou ; Ioannis Sigalas ; Ioannis Vaxevanakis ; Vassilis Zissimopoulos - Approximations for Fault-Tolerant Total and Partial Positive Influence Domination

dmtcs:15903 - Discrete Mathematics & Theoretical Computer Science, January 23, 2026, vol. 28:2 - https://doi.org/10.46298/dmtcs.15903
Approximations for Fault-Tolerant Total and Partial Positive Influence DominationArticle

Authors: Ioannis Lamprou ; Ioannis Sigalas ; Ioannis Vaxevanakis ; Vassilis Zissimopoulos

    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.


    Volume: vol. 28:2
    Section: Discrete Algorithms
    Published on: January 23, 2026
    Accepted on: December 11, 2025
    Submitted on: June 20, 2025
    Keywords: Data Structures and Algorithms

    Consultation statistics

    This page has been seen 49 times.
    This article's PDF has been downloaded 15 times.