Graph Square Roots of Small Distance from Degree One Graphs

Petr Golovach; Paloma Thomé de Lima; Charis Papadopoulos

doi:10.1007/s00224-022-10079-8

Graph Square Roots of Small Distance from Degree One Graphs

Petr Golovach, Paloma Thomé de Lima, Charis Papadopoulos

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

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

Original language	English
Journal	Theory of Computing Systems
Volume	66
Pages (from-to)	821-846
ISSN	1432-4350
DOIs	https://doi.org/10.1007/s00224-022-10079-8
Publication status	Published - 2022

Keywords

Vertex cover
Structural parameterization
Square root

Access to Document

10.1007/s00224-022-10079-8

Cite this

@article{456603022a474027b8d8e1624729b3aa,

title = "Graph Square Roots of Small Distance from Degree One Graphs",

abstract = "Given a graph class H, the task of the H-Square Root problem is to decide whetheran input graph G has a square root H from H. We are interested in the parameterizedcomplexity of the problem for classes H that are composed by the graphs at vertex deletiondistance at most k from graphs of maximum degree at most one, that is, we are lookingfor a square root H such that there is a modulator S of size k such that H − S is thedisjoint union of isolated vertices and disjoint edges",

keywords = "Vertex cover, Structural parameterization, Square root, Vertex cover, Structural parameterization, Square root",

author = "Petr Golovach and {Thom{\'e} de Lima}, Paloma and Charis Papadopoulos",

year = "2022",

doi = "10.1007/s00224-022-10079-8",

language = "English",

volume = "66",

pages = "821--846",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York LLC",

}

TY - JOUR

T1 - Graph Square Roots of Small Distance from Degree One Graphs

AU - Golovach, Petr

AU - Thomé de Lima, Paloma

AU - Papadopoulos, Charis

PY - 2022

Y1 - 2022

N2 - Given a graph class H, the task of the H-Square Root problem is to decide whetheran input graph G has a square root H from H. We are interested in the parameterizedcomplexity of the problem for classes H that are composed by the graphs at vertex deletiondistance at most k from graphs of maximum degree at most one, that is, we are lookingfor a square root H such that there is a modulator S of size k such that H − S is thedisjoint union of isolated vertices and disjoint edges

AB - Given a graph class H, the task of the H-Square Root problem is to decide whetheran input graph G has a square root H from H. We are interested in the parameterizedcomplexity of the problem for classes H that are composed by the graphs at vertex deletiondistance at most k from graphs of maximum degree at most one, that is, we are lookingfor a square root H such that there is a modulator S of size k such that H − S is thedisjoint union of isolated vertices and disjoint edges

KW - Vertex cover

KW - Structural parameterization

KW - Square root

KW - Vertex cover

KW - Structural parameterization

KW - Square root

U2 - 10.1007/s00224-022-10079-8

DO - 10.1007/s00224-022-10079-8

M3 - Journal article

SN - 1432-4350

VL - 66

SP - 821

EP - 846

JO - Theory of Computing Systems

JF - Theory of Computing Systems

ER -

Graph Square Roots of Small Distance from Degree One Graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this