# zbMATH — the first resource for mathematics

Approximation algorithms for minimum (weight) connected $$k$$-path vertex cover. (English) Zbl 1333.05168
Summary: A vertex subset $$C$$ of a connected graph $$G$$ is called a connected $$k$$-path vertex cover ($$\mathrm{CVCP}_k$$) 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) $$\mathrm{CVCP}_k$$ problem. We first show that the minimum weight $$\mathrm{CVCP}_k$$ problem can be solved in time $$O(n)$$ when the graph is a tree, and can be solved in time $$O(r n)$$ 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) $$\mathrm{CVCP}_k$$ 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.

##### MSC:
 05C40 Connectivity 05C38 Paths and cycles 05C05 Trees 68W25 Approximation algorithms 68Q25 Analysis of algorithms and problem complexity
Full Text:
##### References:
  Bondy, J. A.; Murty, U. S.R., Graph theory, (2008), Springer New York · Zbl 1134.05001  Brešar, B.; Jakovac, M.; Katrenič, J.; Semanišin, G.; Taranenko, A., On the vertex $$k$$-path cover, Discrete Appl. Math., 161, 1943-1949, (2013) · Zbl 1286.05076  Brešar, B.; Kardoš, F.; Katrenič, J.; Semanišin, G., Minimum $$k$$-path vertex cover, Discrete Appl. Math., 159, 1189-1195, (2011) · Zbl 1223.05224  Brešar, B.; Krivoš-Belluš, R.; Semanišin, G.; Šparl, P., On the weighted $$k$$-path vertex cover problem, Discrete Appl. Math., 177, 14-18, (2014) · Zbl 1297.05103  Das, B.; Bharghavan, V., Routing in ad-hoc networks using minimum connected dominating sets, (IEEE International Conference on Communications, (1997), Montreal), 376-380  Dinur, T.; Safra, S., On the hardness of approximating minimum vertex cover, Ann. of Math., 162, 439-485, (2005) · Zbl 1084.68051  Fujito, T., A unified approximation algorithm for node-deletion problems, Discrete Appl. Math., 86, 213-231, (1998) · Zbl 0906.68106  Jakovac, M.; Taranenko, A., On the $$k$$-path vertex cover of some graph products, Discrete Math., 313, 94-100, (2013) · Zbl 1264.05102  Kardoš, F.; Katrenič, J.; Schiermeyer, I., On computing the minimum 3-path vertex cover and dissociation number of graphs, Theoret. Comput. Sci., 412, 7009-7017, (2011) · Zbl 1227.68034  Krishnamoorthy, M. S.; Deo, N., Node-deletion NP-complete problems, SIAM J. Comput., 8, 4, 619-625, (1979) · Zbl 0423.05039  Lewis, J. M.; Yannakakis, M., The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci., 20, 219-230, (1980) · Zbl 0436.68029  Li, Y.; Tu, J., A 2-approximation algorithm for the vertex cover $$P_4$$ problem in cubic graphs, Int. J. Comput. Math., 91, 10, 2103-2108, (2014) · Zbl 1303.05199  Liu, X.; Lu, H.; Wang, W.; Wu, W., PTAS for the minimum $$k$$-path connected vertex cover problem in unit disk graphs, J. Global Optim., 56, 449-458, (2013) · Zbl 1275.90118  Novotny, M., Design and analysis of a generalized canvas protocol, (Proceedings of WISTP 2010, LNCS, vol. 6033, (2010)), 106-121  Tu, J., A fixed-parameter algorithm for the vertex cover $$P_3$$ problem, Inform. Process. Lett., 115, 96-99, (2015) · Zbl 1305.05223  Tu, J.; Yang, F., The vertex cover $$P_3$$ problem in cubic graphs, Inform. Process. Lett., 113, 481-485, (2013) · Zbl 1358.05234  Tu, J.; Zhou, W., A factor 2 approximation algorithm for the vertex cover $$P_3$$ problem, Inform. Process. Lett., 111, 683-686, (2011) · Zbl 1260.68304  Tu, J.; Zhou, W., A primal-dual approximation algorithm for the vertex cover $$P_3$$ problem, Theoret. Comput. Sci., 412, 7044-7048, (2011) · Zbl 1228.68033  Zhang, Y.; Shi, Y.; Zhang, Z., Approximation algorithm for the minimum weight connected $$k$$-subgraph cover problem, Theoret. Comput. Sci., 535, 54-58, (2014) · Zbl 1417.68167
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.