# 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.

##### MSC:
 05C85 Graph algorithms (graph-theoretic aspects) 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text:
##### References:
  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  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  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)  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  Du, D.-Z.; Ko, K. I.; Hu, X., Design and Analysis of Approximation Algorithms (2011), Springer  Fujito, T., A unified approximation algorithm for node-deletion problems, Discrete Appl. Math., 86, 213-231 (1998) · Zbl 0906.68106  Fujito, T., On approximability of the independent/connected edge dominating set problems, Inf. Process. Lett., 79, 261-266 (2001) · Zbl 1032.68120  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, Theor. Comput. Sci., 412, 7009-7017 (2011) · Zbl 1227.68034  Katrenič, J., A faster FPT algorithm for 3-path vertex cover, Inf. Process. Lett., 116, 4, 273-278 (2016) · Zbl 1347.68182  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. Syst. Sci., 20, 219-230 (1980) · Zbl 0436.68029  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  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  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  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)  Tu, J.; Yang, F., The vertex cover p3 problem in cubic graphs, Inf. Process. Lett., 113, 481-485 (2013) · Zbl 1358.05234  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  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  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  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  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  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  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.