Abstract. The paper studies crown reductions for the Minimum Weighted Vertex Cover problem introduced recently for the unweighted case by Fellows et al. ([15], [1] ). We show a close relation of crown reductions to Nemhauser and Trotter reductions based on the linear programming relaxation of the problem. So called strong crown reductions, suitable for finding (or counting) all minimum vertex covers, or finding a minimum vertex cover under some additional constraints, are also introduced and studied. We show how crown decompositions and strong crown decompositions can be computed in polynomial time. For weighted König-Egerváry graphs (G, w) we show how the set of vertices belonging to all minimum vertex covers, and the set of vertices belonging to no minimum vertex covers, can be efficiently computed. Further, for some specific classes of graphs, simple algorithms for the Min-VC problem with a constant approximation factor r < 2 are provided. On the other hand, we conclude that for the regular graphs, or for the Hamiltonian connected graphs, the problem is as hard to approximate as for general graphs. It is demonstrated how the results about strong crown reductions can be used to achieve a linear size problem kernel for some related vertex cover problems.
A crown reduction based approach to tackle the minimum weighted vertex cover and Nemhauser-Trotter approaches based on relaxed version of NP-problem is explored by Miroslav Chlebíka and Janka Chlebíková in REF .
Crown reductions for the Minimum Weighted Vertex Cover problem
Discret. Appl. Math.
Discret. Appl. Math.
Computer Science Mathematics