Editing to a Graph of Given Degrees

被引:1
|
作者
Golovach, Petr A. [1 ,2 ]
机构
[1] Univ Bergen, Dept Informat, N-5008 Bergen, Norway
[2] Russian Acad Sci, Steklov Inst Math St Petersburg, St Petersburg 196140, Russia
关键词
HEREDITARY PROPERTIES; COMPLEXITY;
D O I
10.1007/978-3-319-13524-3_17
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the Editing to a Graph of Given Degrees problem that for a graph G, non-negative integers d, k and a function delta : V (G) -> {1,..., d}, asks 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 subset of coNP/poly.
引用
收藏
页码:196 / 207
页数:12
相关论文
共 50 条