Approximation algorithms for minimum (weight) connected k-path vertex cover

作者：Li, Xiaosong; Zhang, Zhao^*; Huang, Xiaohui

来源：Discrete Applied Mathematics, 2016, 205: 101-108.

DOI：10.1016/j.dam.2015.12.004

• Connected k-path vertex cover
• Weight
• Tree
• Girth
• Approximation algorithm

A vertex subset C of a connected graph G is called a connected k-path vertex cover (CVCPk) if every path on k vertices contains at least one vertex from C, and the subgraph of G induced by C is connected. This concept originated in the field of security and supervisory control. This paper studies the minimum (weight) CVCPk problem. We first show that the minimum weight CVCPk problem can be solved in time O(n) when the graph is a tree, and can be solved in time O(m) when the graph is a uni-cyclic graph whose unique cycle has length r, where n is the number of vertices. Making use of the algorithm on trees, we present a k-approximation algorithm for the minimum (cardinality) CVCPk problem under the assumption that the graph has girth at least k. An example is given showing that performance ratio k is asymptotically tight for our algorithm.

• 出版日期2016-5-31
• 单位浙江师范大学; 新疆大学