University of Sussex
Browse

File(s) not publicly available

Crown reductions for the minimum weighted vertex cover problem

journal contribution
posted on 2023-06-07, 20:04 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková
The paper studies crown reductions for the Minimum Weighted Vertex Cover problem introduced recently in the unweighted case by Fellows et al. [Blow-Ups, Win/Win's and crown rules: some new directions in FPT, in: Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG'03), Lecture notes in computer science, vol. 2880, 2003, pp. 1-12, Kernelization algorithms for the vertex cover problem: theory and experiments, in: Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, Louisiana, January 2004, pp. 62-69]. We describe in detail a close relation of crown reductions to Nemhauser and Trotter reductions that are based on the linear programming relaxation of the problem. We introduce and study the so-called strong crown reductions, suitable for finding (or counting) all minimum vertex covers, or finding a minimum vertex cover under some additional constraints. It is described how crown decompositions and strong crown decompositions suitable for such problems can be computed in polynomial time. For weighted Konig-Egervary graphs (G,w) we observe that 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.

History

Publication status

  • Published

Journal

Discrete Applied Mathematics

ISSN

0166-218X

Issue

3

Volume

156

Page range

292-312

Pages

21.0

Department affiliated with

  • Mathematics Publications

Full text available

  • No

Peer reviewed?

  • Yes

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC