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.

05C40 Connectivity
05C38 Paths and cycles
05C05 Trees
68W25 Approximation algorithms
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Bondy, J. A.; Murty, U. S.R., Graph theory, (2008), Springer New York · Zbl 1134.05001
[2] 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
[3] 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
[4] 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
[5] Das, B.; Bharghavan, V., Routing in ad-hoc networks using minimum connected dominating sets, (IEEE International Conference on Communications, (1997), Montreal), 376-380
[6] Dinur, T.; Safra, S., On the hardness of approximating minimum vertex cover, Ann. of Math., 162, 439-485, (2005) · Zbl 1084.68051
[7] Fujito, T., A unified approximation algorithm for node-deletion problems, Discrete Appl. Math., 86, 213-231, (1998) · Zbl 0906.68106
[8] Jakovac, M.; Taranenko, A., On the \(k\)-path vertex cover of some graph products, Discrete Math., 313, 94-100, (2013) · Zbl 1264.05102
[9] 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
[10] Krishnamoorthy, M. S.; Deo, N., Node-deletion NP-complete problems, SIAM J. Comput., 8, 4, 619-625, (1979) · Zbl 0423.05039
[11] 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
[12] 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
[13] 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
[14] Novotny, M., Design and analysis of a generalized canvas protocol, (Proceedings of WISTP 2010, LNCS, vol. 6033, (2010)), 106-121
[15] Tu, J., A fixed-parameter algorithm for the vertex cover \(P_3\) problem, Inform. Process. Lett., 115, 96-99, (2015) · Zbl 1305.05223
[16] Tu, J.; Yang, F., The vertex cover \(P_3\) problem in cubic graphs, Inform. Process. Lett., 113, 481-485, (2013) · Zbl 1358.05234
[17] 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
[18] 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
[19] 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.