The Buss Reduction for the \(k\)-Weighted Vertex Cover Problem

Hong Xu, Xin-Zeng Wu, Cheng Cheng, Sven Koenig, and T. K. Satish Kumar. The Buss reduction for the \(k\)-weighted vertex cover problem. In Proceedings of the 15th International Symposium on Artificial Intelligence and Mathematics (ISAIM). 2018. URL: http://isaim2018.cs.virginia.edu/papers/ISAIM2018_Xu_etal.pdf.
[full text] [slides] [BibTeX▼]

@inproceedings{xu2018,
    author = "Xu, Hong and Wu, Xin-Zeng and Cheng, Cheng and Koenig, Sven and Kumar, T. K. Satish",
    title = "The {Buss} Reduction for the \(k\)-Weighted Vertex Cover Problem",
    year = "2018",
    booktitle = "Proceedings of the 15th International Symposium on Artificial Intelligence and Mathematics (ISAIM)",
    url = "http://isaim2018.cs.virginia.edu/papers/ISAIM2018\_Xu\_etal.pdf",
    customlinkslides = "http://files.hong.me/papers/xu2018-slides.pdf"
}

Abstract

The \(k\)-vertex cover (\(k\)-VC) problem is to find a VC of cardinality no more than \(k\) on a given undirected graph, and the \(k\)-weighted VC (\(k\)-WVC) problem is to find a VC of a weight no more than \(k\) on a given vertex-weighted undirected graph. In this paper, we generalize the Buss reduction, an important kernelization technique for the \(k\)-VC problem, to the \(k\)-WVC problem. We study its properties for the \(k\)-VC problem and the \(k\)-WVC problem on surrogates of large real-world graphs that are generated using the Erd\Hos-R\'enyi model and the Barab\'asi-Albert model. We also argue that our study of the Buss reduction bears important implications on the kernelization of combinatorial problems that have been shown to be reducible to WVC problems.

Presentation

Full Text

[download]