Approximating power node-deletion problems.

In the Power Vertex Cover (PVC) problem introduced in [1] as a generalization of the well-known Vertex Cover , we are allowed to specify costs for covering edges in a graph individually. Namely, two (nonnegative) weights, w (u , v) and w (v , u) , are associated with each edge { u , v } ∈ E of an input graph G = (V , E) , and to cover an edge { u , v } , it is required to assign "power" p ∈ R + V on vertices of G such that either p (u) ≥ w (u , v) or p (v) ≥ w (v , u). The objective is to minimize the total power assigned on V , ∑ v ∈ V p (v) , while covering all the edges of G by p. The node-deletion problem for a graph property π is the problem of computing a minimum vertex subset C ⊆ V in a given graph G = (V , E) , such that the graph satisfies π when all the vertices in C are removed from G. In this paper we consider node-deletion problems extended with the "covering-by-power" condition as in PVC, and present a unified approach for effectively approximating them. The node-deletion problems considered are Partial Vertex Cover (PartVC) , Bounded Degree Deletion (BDD) , and Feedback Vertex Set (FVS) , each corresponding to graph properties π = "the graph has at most | E | − k edges", π = "vertex degree of v is no larger than b (v) ", and π = "the graph is acyclic", respectively. After reducing these problems to the Submodular Set Cover (SSC) problem, we conduct an extended analysis of the approximability of these problems in the new setting of power covering by applying some of the existing techniques for approximating SSC. It will be shown that 1) PPartVC can be approximated within a factor of 2, 2) PBDD for b ∈ Z + V within max ⁡ { 2 , 1 + b max } , where b max = max v ∈ V ⁡ b (v) , or within 2 + log ⁡ b max (for b max ≥ 1) by a combination of the greedy SSC algorithm and the local ratio method extended for power node-deletion problems, and 3) PFVS within 2, resulting in each of these bounds matching the best one known for the corresponding original problem. • The Min-Power-Cover versions of node-deletion problems are considered, in which, given a graph G = (V , E) with two weights, w (u , v) and w (v , u) , associated with each edge { u , v } ∈ E , any edge { u , v } is to be covered by assigning "power" p ∈ R V on vertices of G such that either p (u) ≥ w (u , v) or p (v) ≥ w (v , u). • The Min-Power-Cover node-deletion problem for graph property π is then to compute p ∈ R V minimizing ∑ v ∈ V p (v) such that the graph satisfies π when all the edges covered by p are deleted from G. • The Min-Power-Cover version of Partial Vertex Cover is shown approximable within a factor of 2. • The Min-Power-Cover version of Bounded Degree Deletion with degree bound b ∈ Z + V is shown approximable within max ⁡ { 2 , 1 + b max } , where b max = max v ∈ V ⁡ b (v) , or within 2 + log ⁡ b max (for b max ≥ 1). • The Min-Power-Cover version of Feedback Vertex Set is shown approximable within 2. [ABSTRACT FROM AUTHOR]