Sparse Square Roots

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

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.

Citation

Cochefert, M., Couturier, J.-F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2013, December). Sparse Square Roots. Presented at 39th International Workshop, WG 2013, Lübeck, Germany

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 39th International Workshop, WG 2013
• Publication Date: Jan 1, 2013
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 14, 2015
• Print ISSN: 0302-9743
• Pages: 177-188
• Series Title: Lecture notes in computer science
• Series Number: 8165
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, Lübeck, Germany, 19-21 June 2013 ; revised papers.
• ISBN: 9783642450426
• DOI: https://doi.org/10.1007/978-3-642-45043-3_16
• Public URL: https://durham-repository.worktribe.com/output/1154605