Article ID Journal Published Year Pages File Type
434042 Theoretical Computer Science 2015 13 Pages PDF
Abstract

We consider the Editing to a Graph of Given Degrees problem that asks for a graph G  , non-negative integers d,kd,k and a function δ:V(G)→{1,…,d}δ:V(G)→{1,…,d}, whether it is possible to obtain a graph G′G′ from G such that the degree of v   is δ(v)δ(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+kd+k. We complement this result by showing that the problem has no polynomial kernel unless NP⊆coNP/polyNP⊆coNP/poly.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,