Skip to search boxSkip to navigationSkip to main content

Graph Square Roots of Small Distance from Degree One Graphs

  • University of Bergen
    ,
  • ,
  • University of Ioannina
Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-review

Open access

Publication Information

Output type

Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-review

Original language

English

Pages from-to (Number of pages)

Pages 821-846

Journal (Volume, Issue Number)

Theory of Computing Systems (Volume 66)

Publication milestones

  • Published - 2022

Publication status

Published - 2022

ISSN

1432-4350

Publication IDs

  • Scopus: 85129179545

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

Publication metrics