Editing to a Graph of Given Degrees
classification
💻 cs.DS
keywords
graphdegreeseditinggivendeltaedgeproblemvertex
read the original abstract
We consider the Editing to a Graph of Given Degrees problem that asks for a graph G, non-negative integers d,k and a function \delta:V(G)->{1,...,d}, whether it is possible to obtain a graph G' from G such that the degree of v is \delta(v) for any vertex v by at most k vertex or edge deletions or edge additions. We construct an FPT-algorithm for Editing to a Graph of Given Degrees parameterized by d+k. We complement this result by showing that the problem has no polynomial kernel unless NP\subseteq coNP/poly.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.