The minimum generalized vertex cover problem

ABSTRACT

Let G = (V, E) be an undirected graph, with three numbers d₀(e) ≥ d₁(e) ≥ d₂(e) ≥ 0 for each edge e ∈ E. A solution is a subset U ⊆ V and d_i(e) represents the cost contributed to the solution by the edge e if exactly i of its endpoints are in the solution. The cost of including a vertex v in the solution is c(v). A solution has cost that is equal to the sum of the vertex costs and the edge costs. The minimum generalized vertex cover problem is to compute a minimum cost set of vertices. We study the complexity of the problem with the costs d₀(e) = 1, d₁(e) = α and d₂(e) = 0 ∀e ∈ E and c(v) = β∀v ∈ V, for all possible values of α and β. We also provide 2-approximation algorithms for the general case.

REFERENCES

• 1: Reuven Bar-Yehuda , Keren Bendel , Ari Freund , Dror Rawitz, Local ratio: A unified framework for approximation algorithms. In Memoriam: Shimon Even 1935-2004, ACM Computing Surveys (CSUR), v.36 n.4, p.422-463, December 2004 [doi>10.1145/1041680.1041683]
• 2: Bar-Yehuda, R., and Even, S. 1981. A linear time approximation algorithm for the weighted vertex cover problem. J. Algor. 2, 198--203.
• 3: Reuven Bar-Yehuda , Dror Rawitz, On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.24-35, August 18-20, 2001
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: Hassin, R., and Levin, A. 2003. The minimum generalized vertex cover problem. In Proceedings of the ESA 2003. 289--300.
• 6: Hochbaum, D. S. 2002. Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations. Europ. J. Oper. Res. 140, 291--321.
• 7: S. O. Krumke , M. V. Marathe , H. Noltemeier , R. Ravi , S. S. Ravi , R. Sundaram , H.- C. Wirth, Improving minimum cost spanning trees by upgrading nodes, Journal of Algorithms, v.33 n.1, p.92-111, Oct. 1999 [doi>10.1006/jagm.1999.1021 ]
• 8: Lawler, E. L. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston.
• 9: Nemhauser, G. L., and Trotter, Jr., L. E. 1975. Vertex packing: Structural properties and algorithms. Math. Prog. 8, 232--248.
• 10: Paik, D., and Sahni, S. 1995. Network upgrading problems. Networks. 26, 45--58.
• 11: Yannakakis, M. 1981. Edge deletion problems. SIAM J. Computing. 10, 297--309.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms

Keywords:
Vertex cover, complexity classification, local-ratio