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
Originalsprog | Engelsk |
---|---|
Tidsskrift | Theory of Computing Systems |
Vol/bind | 66 |
Sider (fra-til) | 821-846 |
ISSN | 1432-4350 |
DOI | |
Status | Udgivet - 2022 |
Emneord
- Vertex cover
- Structural parameterization
- Square root