Domination and Coverage Problems under Vulnerability Constraints

Abstract

In various domination and coverage problems, certain vertices or edges should not be dominated/covered and are designated as vulnerable. Motivated by this, we define the $k$-Vertex Maximum Domination Ratio with Vulnerable Vertices $(k\text{-}MaxDRVV)$ problem, which extends the budgeted dominating set problem to include vulnerability constraints. We propose an approximation algorithm based on an unbudgeted variant of $k\text{-}MaxDRVV$, termed the Maximum Domination Ratio with Vulnerable Vertices $(DRVV)$ problem. For bounded-degree graphs of order $n$, our algorithm provides an $O(k/n)$-approximation for the $k\text{-}MaxDRVV$ problem. We introduce the Dominating Set with Vulnerable Vertices $(DSV)$ problem, reduce it to the Red-Blue Set Cover problem, and derive a $2\sqrt{|V|\cdot (H(\hat{I}{”}_N)-\frac{1}{2}})$-approximation algorithm, where $|V|$ is the order of the graph, $\hat{I}{”}_N$ is the maximum degree among non-vulnerable vertices and $H$ is the harmonic function. Finally, we examine the Vertex Cover with Vulnerable Edges $(VCVE)$ problem, which can be naturally expressed as a special case of the Red-Blue Set Cover problem. We present a polynomial-time $2$-approximation algorithm for the $VCVE$ problem, achieving the best possible ratio.