zbMATH — the first resource for mathematics

Approximation algorithms for minimum weight connected 3-path vertex cover. (English) Zbl 1428.05297
Summary: A \(k\)-path vertex cover \(( \text{VCP}_k)\) is a vertex set \(C\) of graph \(G\) such that every path of \(G\) on \(k\) vertices has at least one vertex in \(C\). Because of its background in keeping data integrality of a network, minimum \(\text{VCP}_k\) problem \(( \text{MinVCP}_k)\) has attracted a lot of researches in recent years. This paper studies the minimum weight connected \(\text{VCP}_k\) problem \(( \text{MinWCVCP}_k)\), in which every vertex has a weight and the \(\text{VCP}_k\) found by the algorithm induces a connected subgraph and has the minimum weight. It is known that \(\text{MinWCVCP}_k\) is set-cover-hard. We present two polynomial-time approximation algorithms for \(\text{MinWCVCP}_3\). The first one is a greedy algorithm achieving approximation ratio \(3\ln n\). The difficulty lies in its analysis dealing with a non-submodular potential function. The second algorithm is a 2-stage one, finding a \(\text{VCP}_3\) in the first stage and then adding more vertices for connection. We show that its approximation ratio is at most \(\ln \delta_{\max} + 4 + \ln 2\), where \(\delta_{\max}\) is the maximum degree of the graph. Considering the inapproximability of this problem, this ratio is asymptotically tight.

05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] 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
[2] 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
[3] Chang, M. S.; Chen, L. H.; Hung, L. J.; Rossmanith, P.; Su, P. C., Fixed-parameter algorithms for vertex cover p3, Discrete Optim., 19, 12-22 (2016) · Zbl 1387.05248
[4] Camby, E.; Cardinal, J.; Chapelle, M.; Fiorini, S.; Joret, G., A primal-dual 3-approximation algorithm for hitting 4-vertex paths, Proceedings of the ninth International Colloquium on Graph Theory and Combinatorics (ICGT)61 (2014)
[6] Devi, N. S.; Maneb, A.; Mishra, S., Computational complexity of minimum p4 vertex cover problem for regular and k1,4-free graphs, Discrete Appl. Math., 184, 114-121 (2015) · Zbl 1311.05088
[7] Du, D.-Z.; Ko, K. I.; Hu, X., Design and Analysis of Approximation Algorithms (2011), Springer
[8] Fujito, T., A unified approximation algorithm for node-deletion problems, Discrete Appl. Math., 86, 213-231 (1998) · Zbl 0906.68106
[10] Fujito, T., On approximability of the independent/connected edge dominating set problems, Inf. Process. Lett., 79, 261-266 (2001) · Zbl 1032.68120
[11] Jakovac, M.; Taranenko, A., On the k-path vertex cover of some graph products, Discrete Math., 313, 94-100 (2013) · Zbl 1264.05102
[12] Kardoš, F.; Katrenič, J.; Schiermeyer, I., On computing the minimum 3-path vertex cover and dissociation number of graphs, Theor. Comput. Sci., 412, 7009-7017 (2011) · Zbl 1227.68034
[13] Katrenič, J., A faster FPT algorithm for 3-path vertex cover, Inf. Process. Lett., 116, 4, 273-278 (2016) · Zbl 1347.68182
[14] Krishnamoorthy, M. S.; Deo, N., Node-deletion NP-complete problems, SIAM J. Comput., 8, 4, 619-625 (1979) · Zbl 0423.05039
[16] Lewis, J. M.; Yannakakis, M., The node-deletion problem for hereditary properties is NP-complete, J. Comput. Syst. Sci., 20, 219-230 (1980) · Zbl 0436.68029
[17] Li, X.; Zhang, Z.; Huang, X., Approximation algorithms for minimum (weight) connected k-path vertex cover, Discrete Appl. Math., 205, 101-108 (2016) · Zbl 1333.05168
[18] Li, Y.; Tu, J., A 2-approximation algorithm for the vertex cover p4 problem in cubic graphs, Int. J. Comput. Math., 91, 10, 2103-2108 (2014) · Zbl 1303.05199
[19] Liu, X.; Lu, H.; Wang, W.; Wu, W., PTAS for the minimum k-path connected vertex cover problem in unit disk graphs, J. Glob. Optim., 56, 449-458 (2013) · Zbl 1275.90118
[20] Novotný, M., Design and analysis of a generalized canvas protocol, Proceedings of the International Workshop on Information Security Theory and Practices (WISTP), 6033, 106-121 (2010)
[21] Tu, J.; Yang, F., The vertex cover p3 problem in cubic graphs, Inf. Process. Lett., 113, 481-485 (2013) · Zbl 1358.05234
[22] Tu, J.; Zhou, W., A factor 2 approximation algorithm for the vertex cover p3 problem, Inf. Process. Lett., 111, 683-686 (2011) · Zbl 1260.68304
[23] Tu, J.; Zhou, W., A primal-dual approximation algorithm for the vertex cover p3 problem, Theor. Comput. Sci., 412, 7044-7048 (2011) · Zbl 1228.68033
[24] Wang, L.; Zhang, X.; Zhang, Z.; Broersma, H., A PTAS for the minimum weight connected vertex cover p3 problem on unit disk graphs, Theor. Comput. Sci., 571, 58-66 (2015) · Zbl 1312.68234
[25] Wang, L.; Du, W.; Zhang, Z.; Zhang, X., A PTAS for minimum weighted connected vertex cover p3 problem in 3-dimensional wireless sensor networks, J. Comb. Optim., 33, 1, 106-122 (2017) · Zbl 1366.90204
[26] Xiao, M.; Kou, S., Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems, Theor. Comput. Sci., 657, 86-97 (2017) · Zbl 1357.05146
[27] Xiao, Y.; Du, X., A survey on sensor network security, (Li, Y.; etal., Wireless Sensor Networks and Applications, Signals and Communication Technology Series (2008), Springer: Springer Heidelberg), 403-421
[28] Zhang, Y.; Shi, Y.; Zhang, Z., Approximation algorithm for the minimum weight connected k-subgraph cover problem, Theor. 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.