The minimum generalized vertex cover problem
Refael Hassin, Asaf Levin · ACM Transactions on Algorithms · 2006
Let G = ( V , E ) be an undirected graph, with three numbers d 0 ( e ) ≥ d 1 ( e ) ≥ d 2 ( 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 0 ( e ) = 1, d 1 ( e ) = α and d 2 ( 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.