pith. sign in

arxiv: 1311.4768 · v2 · pith:327XHJHYnew · submitted 2013-11-19 · 💻 cs.DS

Editing to a Graph of Given Degrees

classification 💻 cs.DS
keywords graphdegreeseditinggivendeltaedgeproblemvertex
0
0 comments X
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.