Parameterized Algorithms for Finding Square Roots

2016 
We show that the following two problems are fixed-parameter tractable with parameter $$k$$k: testing whether a connected $$n$$n-vertex graph with $$m$$m edges has a square root with at most $$n-1+k$$n-1+k edges and testing whether such a graph has a square root with at least $$m-k$$m-k edges. Our first result implies that squares of graphs obtained from trees by adding at most $$k$$k edges can be recognized in polynomial time for every fixed $$k\ge 0$$k?0; previously this result was known only for $$k=0$$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$$k edge deletions is fixed-parameter tractable with parameter $$k$$k.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    25
    References
    14
    Citations
    NaN
    KQI
    []