Parameterized algorithms for finding square roots

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

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.-F., Golovach, P., & Paulusma, D. (online). Parameterized algorithms for finding square roots. Algorithmica, https://doi.org/10.1007/s00453-014-9967-4

• Journal Article Type: Article
• 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