×

Computing roots of graphs is hard. (English) Zbl 0812.68103

Summary: The square of an undirected graph \(G\) is the graph \(G^ 2\) on the same vertex set such that there is an edge between two vertices in \(G^ 2\) if and only if they are at distance at most 2 in \(G\). The \(k\)th power of a graph is defined analogously. It has been conjectured that the problem of computing any square root of a square graph, or even that of deciding whether a graph is a square, is NP-hard. We settle this conjecture in the affirmative.

MSC:

68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Escalante, F.; Montejano, L.; Rojano, T., Characterization of \(n\)-path graphs and of graphs having \(n\) th root, J. Combin. Theory Ser. B, 16, 282-289 (1974) · Zbl 0268.05118
[2] Fleischner, H., The square of every two-connected graphs is Hamiltonian, J. Combin. Theory Ser. B, 16, 29-34 (1974) · Zbl 0256.05121
[3] Garey, M. R.; Johnson, D. S., Computers and Intractability — A Guide to the Theory of NP-completeness (1979), Freeman: Freeman Oxford, NY · Zbl 0411.68039
[4] Geller, D. P., The square root of a digraph, J. Combin. Theory Ser. B, 5, 320-321 (1968) · Zbl 0167.22402
[5] Harary, F.; Karp, R. M.; Tutte, W. T., A criterion for planarity of the square of a graph, J. Combin. Theory Ser. B, 2, 395-405 (1967) · Zbl 0153.25902
[6] Lau, H. T., Finding a Hamiltonian cycle in the square of a block, (Ph.D. Thesis (1980), School of Computer Science, McGill University: School of Computer Science, McGill University Montreal) · Zbl 0456.05041
[7] Lin, Y-L.; Skiena, S. S., Algorithms for square roots of graphs, (Tech. Report TR#91/11 (1991), Department of Computer Science: Department of Computer Science SUNY Stony Brook) · Zbl 0821.05052
[8] Linial, N., Locality in distributed graph algorithms, SIAM J. Computing, 21, 193-320 (1992) · Zbl 0787.05058
[9] Mukhopadhyay, A., The square root of a graph, J. Combin. Theory Ser. B, 2, 290-295 (1967) · Zbl 0153.26001
[10] Ross, D. J.; Harary, F., The square root of a tree, Bell System Tech. J, 39, 641-647 (1960)
[11] Sekanina, M., On an ordering of the set of vertices of a connected graph, (Tech. Rept. No. 412 (1960), Publ. Fac. Sci. Univ. Brno) · Zbl 0118.18903
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.