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.
|Keywords:||Parameterized complexity, Graph square root, Generalized kernel|
|Full text:||(AM) Accepted Manuscript|
Download PDF (441Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/s00453-014-9967-4|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-014-9967-4|
|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|