Parameterized Algorithms for Finding Square Roots

Manfred Cochefert, Jean-François Couturier, Petr A. Golovach +2

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…