A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 from each other. The Square Root problem is that of deciding whether a given graph admits a square root. We consider this problem for planar graphs in the context of the "distance from triviality" framework. For an integer k, a planar+kv graph is a graph that can be made planar by the removal of at most k vertices. We prove that a generalization of Square Root, in which some edges are prescribed to be either in or out of any solution, has a kernel of size O(k) for planar+kv graphs, when parameterized by k. Our result is based on a new edge reduction rule which, as we shall also show, has a wider applicability for the Square Root problem. In 1967, Mukhopadhyay [22] characterized the graphs that have a square root. In line with the aforementioned NP-completeness result of Motwani and Sudan, which appeared in 1994, this characterization does not lead to a polynomial-time algorithm for Square Root. Later results focussed on the following two recognition questions (G denotes some fixed graph class): How hard is it to recognize squares of graphs of G? How hard is it to recognize graphs of G that have a square root? Note that the second question corresponds to the Square Root problem restricted to graphs in G, whereas the first question is the same as asking whether a given graph has a square root in G. Ross and Harary [24] characterized squares of a tree and proved that if a connected graph has a tree square root, then this root is unique up to isomorphism. Lin and Skiena [18] gave a linear-time algorithm for recognizing squares of trees; they also proved that Square Root can be solved in linear time for planar graphs. Le and Tuy [16] generalized the above results for trees [18, 24] to block graphs. Nestoridis and Thilikos [23] proved that Square Root is not only polynomial-time solvable for the class of planar graphs but for any non-trivial minor-closed graph class, that is, for any graph class that does not contain all graphs and that is closed under taking vertex deletions, edge deletions and edge contractions. Lau [12] gave a polynomial-time algorithm for recognizing squares of bipartite graphs; note that Square Root is trivial for bipartite graphs, and even for K 4 -free graphs, or equivalently, graphs of clique number at most 3, as square roots of K 4 -free graphs must have maximum degree at most 2. Milanic, Oversberg and Schaudt [19] proved that line graphs can only have bipartite graphs as a square root. The same authors also gave a linear-time algorithm for Square Root restricted to line graphs. Lau and Corneil [13] gave a polynomial-time algorithm for recognizing squares of proper interval graphs and showed that the problems of recognizing squares of chordal graphs and squares of split graphs are both NP-complete. The same authors also proved that Square Root is NP-complete even for chordal graphs. Le and Tuy [17] gave a quadratictime algorithm for recognizing squares of strongly chordal split graphs. Le, Oversberg and Schaudt [14] gave polynomial algorithms for recognizing squares of ptolemaic graphs and 3-sun-free split graphs. In a more recent paper [15] , the same authors extended the latter result by giving polynomial-time results for recognizing squares of a number of other subclasses of split graphs. Milanic and Schaudt [20] proved that Square Root can be solved in linear time for trivially perfect graphs and threshold graphs. They posed the complexity of Square Root restricted to split graphs and cographs as open problems. Recently, we proved that Square Root is linear-time solvable for 3-degenerate graphs and for (K r , P t )-free graphs for any two positive integers r and t [8] . Adamaszek and Adamaszek [1] proved that if a graph has a square root of girth at least 6, then this square root is unique up to isomorphism. Farzad, Lau, Le and Tuy [7] showed that recognizing graphs with a square root of girth at least g is polynomial-time solvable if g ≥ 6 and NP-complete if g = 4. The missing case g = 5 was shown to be NP-complete by Farzad and Karimi [6] . In a previous paper [2] we proved that Square Root is polynomial-time solvable for graphs of maximum degree 6. We also considered square roots under the framework of parameterized complexity [3, 2] . We proved that the following two problems are fixedparameter 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. In particular, the first result implies that the problem of recognizing squares of tree+ke graphs, that is, graphs that can be modified into trees by removing at most k edges, is fixed-parameter tractable when parameterized by k.
As proved in REF , the decomposition of the square root of a graph G by its cut-vertices leads to a specific type of tree decompositions for G that are called "H-tree decompositions".
A Linear Kernel for Finding Square Roots of Almost Planar Graphs
ArXiv
ArXiv
Mathematics Computer Science