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.
展开▼
