We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Parameterized algorithms for finding square roots.

Cochefert, M. and Couturier, J-F. and Golovach, P.A. and Paulusma, D. (2014) 'Parameterized algorithms for finding square roots.', Algorithmica. .


We show that the following two problems are fixed-parameter tractable with parameter k: testing whether a connected n-vertex graph with m edges has a square root with at most n−1+k edges and testing whether such a graph has a square root with at least m−k edges. Our first result implies that squares of graphs obtained from trees by adding at most k edges can be recognized in polynomial time for every fixed k≥0; previously this result was known only for k=0. Our second result is equivalent to stating that deciding whether a graph can be modified into a square root of itself by at most k edge deletions is fixed-parameter tractable with parameter k.

Item Type:Article
Keywords:Parameterized complexity, Graph square root, Generalized kernel
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:06 January 2015
Date of first online publication:December 2014
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar