Parameterized algorithms for finding square roots

Cochefert, M.; Couturier, J-F.; Golovach, P.A.; Paulusma, D.

doi:10.1007/s00453-014-9967-4

Parameterized algorithms for finding square roots

Cochefert, M.; Couturier, J-F.; Golovach, P.A.; Paulusma, D.

Authors

M. Cochefert

J-F. Couturier

P.A. Golovach

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Abstract

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.

Citation

Cochefert, M., Couturier, J., Golovach, P., & Paulusma, D. (2014). Parameterized algorithms for finding square roots. Algorithmica, https://doi.org/10.1007/s00453-014-9967-4

Journal Article Type	Article
Publication Date	Dec 1, 2014
Deposit Date	Dec 20, 2014
Publicly Available Date	Jan 6, 2015
Journal	Algorithmica
Print ISSN	0178-4617
Electronic ISSN	1432-0541
Publisher	Springer
Peer Reviewed	Peer Reviewed
DOI	https://doi.org/10.1007/s00453-014-9967-4
Keywords	Parameterized complexity, Graph square root, Generalized kernel
Public URL	https://durham-repository.worktribe.com/output/1417632