Complexity of finding graph roots with girth conditions. (English) Zbl 1239.05127
Summary: 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.
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.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Agnarsson, G., Greenlaw, R., Halldórsson, M.M.: On powers of chordal graphs and their colorings. Congressus Numer. 144, 41–65 (2000) · Zbl 0976.05027 |
| [2] | Alon, N., Mohar, B.: The chromatic number of graph powers. Comb. Probab. Comput. 11, 1–10 (2002) · Zbl 0991.05042 |
| [3] | 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 · Zbl 1451.05040 |
| [4] | 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) · Zbl 1142.05365 |
| [5] | Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbol. Comput. 9, 251–280 (1990) · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2 |
| [6] | Cranston, D.W., Kim, S.-J.: List-coloring the square of a subcubic graph. J. Graph Theory 57, 65–87 (2007) · Zbl 1172.05023 · doi:10.1002/jgt.20273 |
| [7] | Dahlhaus, E., Duchet, P.: On strongly chordal graphs. Ars Combin. B 24, 23–30 (1987) · Zbl 0659.05059 |
| [8] | 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 · Zbl 0411.68039 |
| [9] | Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980) · Zbl 0541.05054 |
| [10] | Havet, F.: Choosability of the square of planar subcubic graphs with large girth. Discrete Math. 309(11), 3553–3563 (2009) · Zbl 1213.05084 · doi:10.1016/j.disc.2007.12.100 |
| [11] | Horton, J.D., Kilakos, K.: Minimum edge dominating sets. SIAM J. Discrete Math. 6, 375–387 (1993) · Zbl 0782.05083 · doi:10.1137/0406030 |
| [12] | Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7, 413–423 (1978) · Zbl 0386.68064 · doi:10.1137/0207033 |
| [13] | Kearney, P.E., Corneil, D.G.: Tree powers. J. Algorithms 29, 111–131 (1998) · Zbl 0919.68055 · doi:10.1006/jagm.1998.9999 |
| [14] | Lau, L.C.: Bipartite roots of graphs. ACM Trans. Algorithms 2, 178–208 (2006) · Zbl 1321.05209 · doi:10.1145/1150334.1150337 |
| [15] | Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split and chordal graphs. SIAM J. Discrete Math. 18, 83–102 (2004) · Zbl 1071.05031 · doi:10.1137/S0895480103425930 |
| [16] | Lin, Y.-L., Skiena, S.S.: Algorithms for square roots of graphs. SIAM J. Discrete Math. 8, 99–118 (1995) · Zbl 0821.05052 · doi:10.1137/S089548019120016X |
| [17] | Lubiw, A.: {\(\Gamma\)}-free matrices. Master Thesis, Dept. of Combinatorics and Optimization, University of Waterloo, Canada (1982) |
| [18] | Motwani, R., Sudan, M.: Computing roots of graphs is hard. Discrete Appl. Math. 54, 81–88 (1994) · Zbl 0812.68103 · doi:10.1016/0166-218X(94)00023-9 |
| [19] | Mukhopadhyay, A.: The square root of a graph. J. Combin. Theory 2, 290–295 (1967) · Zbl 0153.26001 · doi:10.1016/S0021-9800(67)80030-9 |
| [20] | Raychaudhuri, A.: On powers of strongly chordal and circular arc graphs. Ars Combin. 34, 147–160 (1992) · Zbl 0770.05066 |
| [21] | Ross, I.C., Harary, F.: The square of a tree. Bell Syst. Tech. J. 39, 641–647 (1960) · doi:10.1002/j.1538-7305.1960.tb03936.x |
| [22] | 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) · Zbl 0364.05027 · doi:10.1137/0206036 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
