Abstract
We show that it can be decided in polynomial time whether a graph of maximum degree 6 has a square root; if a square root exists, then our algorithm finds one with minimum number of edges. We also show that it is FPT to decide whether a connected n-vertex graph has a square root with at most n − 1 + k edges when this problem is parameterized by k. Finally, we give an exact exponential time algorithm for the problem of finding a square root with maximum number of edges.
Supported by EPSRC (EP/G043434/1), ERC (267959) and ANR project AGAPE.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adamaszek, A., Adamaszek, M.: Uniqueness of graph square roots of girth six. Electr. J. Comb. 18(1) (2011)
Aingworth, D., Motwani, R., Harary, F.: The difference between a graph and its square. Util. Math. 54, 223–228 (1998)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)
Diestel, R.: Graph theory, 4th edn. Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg (2010)
Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)
Farzad, B., Karimi, M.: Square-root finding problem in graphs, a complete dichotomy theorem. CoRR abs/1210.7684 (2012)
Farzad, B., Lau, L.C., Le, V.B., Tuy, N.N.: Complexity of finding graph roots with girth conditions. Algorithmica 62(1-2), 38–53 (2012)
Geller, D.P.: The square root of a digraph. J. Combinatorial Theory 5, 320–321 (1968)
Lau, L.C.: Bipartite roots of graphs. ACM Transactions on Algorithms 2(2), 178–208 (2006)
Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal graph. SIAM J. Discrete Math. 18(1), 83–102 (2004)
Le, V.B., Tuy, N.N.: The square of a block graph. Discrete Mathematics 310(4), 734–741 (2010)
Le, V.B., Tuy, N.N.: A good characterization of squares of strongly chordal split graphs. Inf. Process. Lett. 111(3), 120–123 (2011)
Lin, Y.L., Skiena, S.: Algorithms for square roots of graphs. SIAM J. Discrete Math. 8(1), 99–118 (1995)
Milanic, M., Schaudt, O.: Computing square roots of trivially perfect and threshold graphs. Discrete Applied Mathematics (in press)
Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3, 23–28 (1965)
Motwani, R., Sudan, M.: Computing roots of graphs is hard. Discrete Applied Mathematics 54(1), 81–88 (1994)
Mukhopadhyay, A.: The square root of a graph. J. Combinatorial Theory 2, 290–295 (1967)
Ross, I.C., Harary, F.: The square of a tree. Bell System 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(3), 505–517 (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cochefert, M., Couturier, JF., Golovach, P.A., Kratsch, D., Paulusma, D. (2013). Sparse Square Roots. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds) Graph-Theoretic Concepts in Computer Science. WG 2013. Lecture Notes in Computer Science, vol 8165. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45043-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-45043-3_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45042-6
Online ISBN: 978-3-642-45043-3
eBook Packages: Computer ScienceComputer Science (R0)