2013/11/19 by Petr A. Golovach, Golovach, Petr A. · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1311.4768
openalex publication_date 2013/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 δ:V(G)->1,...,d, whether it is possible to obtain a graph G' from G such that the degree of v is δ(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⊆ coNP/poly.