{"ID":6267734,"CreatedAt":"2026-07-10T01:11:38.759438437Z","UpdatedAt":"2026-07-11T18:20:13.703712842Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07842","arxiv_id":"2607.07842","title":"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\\textit{-}Max \\ \\mathit{DRVV})$ problem, which extends the budgeted dominating set problem to include vulnerability constraints. We propose an approximation algorithm based on an unbudgeted variant of $k\\textit{-}Max \\ \\mathit{DRVV}$, termed the Maximum Domination Ratio with Vulnerable Vertices $(\\mathit{DRVV})$ problem. For bounded-degree graphs of order $n$, our algorithm provides an $O(k/n)$-approximation for the $k\\textit{-}Max \\ \\mathit{DRVV}$ problem. We introduce the Dominating Set with Vulnerable Vertices $(\\mathit{DSV})$ problem, reduce it to the Red-Blue Set Cover problem, and derive a $2\\sqrt{|V|\\cdot(H(Δ_{N})-\\frac{1}{2}})$-approximation algorithm, where $|V|$ is the order of the graph, $Δ_N$ is the maximum degree among non-vulnerable vertices and $H$ is the harmonic function. Finally, we examine the Vertex Cover with Vulnerable Edges $(\\mathit{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.","short_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\\textit{-}Max \\ \\mathit{DRVV})$ problem, which extends the budgeted dominating set pro...","url_abs":"https://arxiv.org/abs/2607.07842","url_pdf":"https://arxiv.org/pdf/2607.07842v1","authors":"[\"Ioannis Sigalas\",\"Nikolaos Lazaropoulos\",\"Ioannis Lamprou\",\"Ioannis Vaxevanakis\",\"Vassilis Zissimopoulos\"]","published":"2026-07-08T18:22:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}