Abstract
Graph G is the square of graph H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Given H it is easy to compute its square H 2, however Motwani and Sudan proved that it is NP-complete to determine if a given graph G is the square of some graph H (of girth 3). In this paper we consider the characterization and recognition problems of graphs that are squares of graphs of small girth, i.e. to determine if G=H 2 for some graph H of small girth. The main results are the following.
-
There is a graph theoretical characterization for graphs that are squares of some graph of girth at least 7. A corollary is that if a graph G has a square root H of girth at least 7 then H is unique up to isomorphism.
-
There is a polynomial time algorithm to recognize if G=H 2 for some graph H of girth at least 6.
-
It is NP-complete to recognize if G=H 2 for some graph H of girth 4.
These results almost provide a dichotomy theorem for the complexity of the recognition problem in terms of girth of the square roots. The algorithmic and graph theoretical results generalize previous results on tree square roots, and provide polynomial time algorithms to compute a graph square root of small girth if it exists. Some open questions and conjectures will also be discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agnarsson, G., Greenlaw, R., Halldórsson, M.M.: On powers of chordal graphs and their colorings. Congressus Numer. 144, 41–65 (2000)
Alon, N., Mohar, B.: The chromatic number of graph powers. Comb. Probab. Comput. 11, 1–10 (2002)
Brandstädt, A., Le, V.B., Sritharan, R.: Structure and linear time recognition of 4-leaf powers. ACM Trans. Algorithms 5 (2008), Article No. 11
Chang, M.-S., Ko, M.-T., Lu, H.-I.: Linear time algorithms for tree root problems. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Lecture Notes in Computer Science, vol. 4059, pp. 411–422. Springer, Berlin (2006)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbol. Comput. 9, 251–280 (1990)
Cranston, D.W., Kim, S.-J.: List-coloring the square of a subcubic graph. J. Graph Theory 57, 65–87 (2007)
Dahlhaus, E., Duchet, P.: On strongly chordal graphs. Ars Combin. B 24, 23–30 (1987)
Garey, M.R., Johnson, D.S.: Computers and Intractability—A Guide to the Theory of NP-Completeness. Freeman, New York (1979). Twenty-third printing 2002
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
Havet, F.: Choosability of the square of planar subcubic graphs with large girth. Discrete Math. 309(11), 3553–3563 (2009)
Horton, J.D., Kilakos, K.: Minimum edge dominating sets. SIAM J. Discrete Math. 6, 375–387 (1993)
Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7, 413–423 (1978)
Kearney, P.E., Corneil, D.G.: Tree powers. J. Algorithms 29, 111–131 (1998)
Lau, L.C.: Bipartite roots of graphs. ACM Trans. Algorithms 2, 178–208 (2006)
Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split and chordal graphs. SIAM J. Discrete Math. 18, 83–102 (2004)
Lin, Y.-L., Skiena, S.S.: Algorithms for square roots of graphs. SIAM J. Discrete Math. 8, 99–118 (1995)
Lubiw, A.: Γ-free matrices. Master Thesis, Dept. of Combinatorics and Optimization, University of Waterloo, Canada (1982)
Motwani, R., Sudan, M.: Computing roots of graphs is hard. Discrete Appl. Math. 54, 81–88 (1994)
Mukhopadhyay, A.: The square root of a graph. J. Combin. Theory 2, 290–295 (1967)
Raychaudhuri, A.: On powers of strongly chordal and circular arc graphs. Ars Combin. 34, 147–160 (1992)
Ross, I.C., Harary, F.: The square of a tree. Bell Syst. Tech. J. 39, 641–647 (1960)
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6, 505–517 (1977)
Author information
Authors and Affiliations
Corresponding author
Additional information
Nguyen Ngoc Tuy is supported by the Ministry of Education and Training, Vietnam, Grant No. 3766/QD-BGD & DT.
Rights and permissions
About this article
Cite this article
Farzad, B., Lau, L.C., Le, V.B. et al. Complexity of Finding Graph Roots with Girth Conditions. Algorithmica 62, 38–53 (2012). https://doi.org/10.1007/s00453-010-9442-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-010-9442-9