## Abstract

Given a graph class H, the task of the H-Square Root problem is to decide whether

an input graph G has a square root H from H. We are interested in the parameterized

complexity of the problem for classes H that are composed by the graphs at vertex deletion

distance at most k from graphs of maximum degree at most one, that is, we are looking

for a square root H such that there is a modulator S of size k such that H − S is the

disjoint union of isolated vertices and disjoint edges

an input graph G has a square root H from H. We are interested in the parameterized

complexity of the problem for classes H that are composed by the graphs at vertex deletion

distance at most k from graphs of maximum degree at most one, that is, we are looking

for a square root H such that there is a modulator S of size k such that H − S is the

disjoint union of isolated vertices and disjoint edges

Original language | English |
---|---|

Journal | Theory of Computing Systems |

Volume | 66 |

Pages (from-to) | 821-846 |

ISSN | 1432-4350 |

DOIs | |

Publication status | Published - 2022 |

## Keywords

- Vertex cover
- Structural parameterization
- Square root