Connected Vertex Cover in 2-Connected Planar Graph with Maximum Degree 4 is NP-complete

Authors: Priyadarsini P. L. K, Hemalatha T.

Abstract:

This paper proves that the problem of finding connected vertex cover in a 2-connected planar graph ( CVC-2 ) with maximum degree 4 is NP-complete. The motivation for proving this result is to give a shorter and simpler proof of NP-Completeness of TRA-MLC (the Top Right Access point Minimum-Length Corridor) problem [1], by finding the reduction from CVC-2. TRA-MLC has many applications in laying optical fibre cables for data communication and electrical wiring in floor plans.The problem of finding connected vertex cover in any planar graph ( CVC ) with maximum degree 4 is NP-complete [2]. We first show that CVC-2 belongs to NP and then we find a polynomial reduction from CVC to CVC-2. Let a graph G0 and an integer K form an instance of CVC, where G0 is a planar graph and K is an upper bound on the size of the connected vertex cover in G0. We construct a 2-connected planar graph, say G, by identifying the blocks and cut vertices of G0, and then finding the planar representation of all the blocks of G0, leading to a plane graph G1. We replace the cut vertices with cycles in such a way that the resultant graph G is a 2-connected planar graph with maximum degree 4. We consider L = K -2t+3 t i=1 di where t is the number of cut vertices in G1 and di is the number of blocks for which ith cut vertex is common. We prove that G will have a connected vertex cover with size less than or equal to L if and only if G0 has a connected vertex cover of size less than or equal to K.

Keywords: NP-complete, 2-Connected planar graph, block, cut vertex

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1080318

References:

[1] A. Gonzalez-Gutierrez and T. F. Gonzalez, " Complexity of the Minimum-Length Corridor Problem", J. Comp. eometry, Theory and Applns.,Els. vol. 37, no. 2,2007,pp. 72-103.
[2] M.R.Garey and D. S. Johnson, "The Rectilinear Steiner Tree Problem is NP - complete",J. Appl. Math.(SIAM), vol. 32, no. 4, 1977, pp. 826-834.
[3] D.B.West, Introduction to Graph Theory, Prentice Hall of India, 1999.
[4] J.A.Bondy and U. S. R. Murty, Graph Theory With Applications, The Macmillan press Ltd, 1976
[5] R.Weiskircher, "Drawing Planar Graphs", from M.Kaufmann & D. Wagner (Eds.): Drawing Graphs, LNCS 2025,Springer-Verlag, 2001, pp. 23-45.
[6] D.Jungnickel, Graphs, Networks and Algorithms, Springer-verlag, 2005.
[7] M.R.Garey & D.S.Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., 1979.
[8] M.R.Garey, D.S.Johnson and Stockmeyer, "Some simplified NP-complete problems",Proc. of the sixth annual ACM Symposium on theory of computing, 1974, pp. 47-63
[9] C.H.Papadimitriou & K.Steiglitz, Combinatorial optimization: Algorithms and Complexity, Prentice Hall India, 1997.