Abstract
Let \(G=(V,E)\) be a simple graph. A set \(C \subseteq V\) is called a k-path vertex cover of G, if each k-path in G contains at least one vertex from C. In the k-path vertex cover problem, we are given a graph G and asked to find a k-path vertex cover of minimum cardinality. For \(k=3\), the problem becomes the well-known 3-path vertex cover (3PVC) problem, which has been widely studied, as per the literature. In this paper, we focus on the 3PVC problem in planar bipartite (pipartite) graphs for the most part. We first show that the 3PVC problem is NP-hard, even in pipartite graphs in which the degree of all vertices is bounded by 4. We then show that the 3PVC problem on this class of graphs admits a linear time 1.5-approximation algorithm. Finally, we show that the 3PVC problem is APX-complete in bipartite graphs. The last result is particularly interesting, since the vertex cover problem in bipartite graphs is solvable in polynomial time.
This research was supported in part by the Air-Force Office of Scientific Research through Grant FA9550-19–1-0177 and in part by the Air-Force Research Laboratory, Rome through Contract FA8750-17-S-7007.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Brešar, B., Kardoš, F., Katrenič, J., Semanišin, G.: Minimum k-path vertex cover. Discrete Appl. Math. 159(12), 1189–1195 (2011)
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1–3), 165–177 (1990)
Devi, N.S., Mane, A.C., Mishra, S.: Computational complexity of minimum P4 vertex cover problem for regular and K1, 4-free graphs. Discrete Appl. Math. 184, 114–121 (2015)
Du, D., Ko, K.-I., Hu, X., et al.: Design and Analysis of Approximation Algorithms, vol. 62. Springer, New York (2012). https://doi.org/10.1007/978-1-4614-1701-9
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. TTCSAES, Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16533-7
Gollmann, D.: Protocol analysis for concrete environments. In: Moreno Díaz, R., Pichler, F., Quesada Arencibia, A. (eds.) EUROCAST 2005. LNCS, vol. 3643, pp. 365–372. Springer, Heidelberg (2005). https://doi.org/10.1007/11556985_47
Kardoš, F., Katrenič, J., Schiermeyer, I.: On computing the minimum 3-path vertex cover and dissociation number of graphs. Theoret. Comput. Sci. 412(50), 7009–7017 (2011)
Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press (1972)
Kumar, M., Mishra, S., Devi, N.S., Saurabh, S.: Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization. Theoret. Comput. Sci. 526, 90–96 (2014)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)
Novotnỳ, M.: Design and analysis of a generalized canvas protocol. In: IFIP International Workshop on Information Security Theory and Practices, pp. 106–121 (2010)
Tu, J., Shi, Y.: An efficient polynomial time approximation scheme for the vertex cover \(p_3\) problem on planar graphs. Discussiones Math. Graph Theory 39(1), 2019
Jianhua, T., Yang, F.: The vertex cover P3 problem in cubic graphs. Inf. Process. Lett. 113(13), 481–485 (2013)
Jianhua, T., Zhou, W.: A factor 2 approximation algorithm for the vertex cover P3 problem. Inf. Process. Lett. 111(14), 683–686 (2011)
Jianhua, T., Zhou, W.: A primal-dual approximation algorithm for the vertex cover P3 problem. Theoret. Comput. Sci. 412(50), 7044–7048 (2011)
Zhang, A., Chen, Y., Chen, Z.-Z., Lin, G.: Improved approximation algorithms for path vertex covers in regular graphs. Algorithmica 82(10), 3041–3064 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Jena, S.K., Subramani, K. (2022). Analyzing the 3-path Vertex Cover Problem in Planar Bipartite Graphs. In: Du, DZ., Du, D., Wu, C., Xu, D. (eds) Theory and Applications of Models of Computation. TAMC 2022. Lecture Notes in Computer Science, vol 13571. Springer, Cham. https://doi.org/10.1007/978-3-031-20350-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-20350-3_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-20349-7
Online ISBN: 978-3-031-20350-3
eBook Packages: Computer ScienceComputer Science (R0)