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 条
  • [21] MINIMAL REGULAR GRAPH CONTAINING A GIVEN GRAPH
    ERDOS, P
    KELLY, P
    AMERICAN MATHEMATICAL MONTHLY, 1963, 70 (10): : 1074 - &
  • [22] Dividing a graph by degrees
    Anstee, RP
    JOURNAL OF GRAPH THEORY, 1996, 23 (04) : 377 - 384
  • [23] ON NUMBER OF ORIENTATIONS OF A GIVEN GRAPH
    HARARY, F
    PALMER, E
    BULLETIN DE L ACADEMIE POLONAISE DES SCIENCES-SERIE DES SCIENCES MATHEMATIQUES ASTRONOMIQUES ET PHYSIQUES, 1966, 14 (03): : 125 - &
  • [24] GRAPH WITH GIVEN ACHROMATIC NUMBER
    HELL, P
    MILLER, DJ
    DISCRETE MATHEMATICS, 1976, 16 (03) : 195 - 207
  • [25] GRAPH FACTORS WITH GIVEN PROPERTIES
    KANO, M
    LECTURE NOTES IN MATHEMATICS, 1984, 1073 : 161 - 168
  • [26] On the decomposition threshold of a given graph
    Glock, Stefan
    Kuhn, Daniela
    Lo, Allan
    Montgomery, Richard
    Osthus, Deryk
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 139 : 47 - 127
  • [27] An extremal graph with given bandwidth
    Lai, Yung-Ling
    Tian, Chang-Sin
    THEORETICAL COMPUTER SCIENCE, 2007, 377 (1-3) : 238 - 242
  • [28] Graph editing to a fixed target
    Golovach, Petr A.
    Paulusma, Daniel
    Stewart, Iain
    DISCRETE APPLIED MATHEMATICS, 2017, 216 : 181 - 190
  • [29] Portable graph layout and editing
    Madden, B
    Madden, P
    Powers, S
    Himsolt, M
    GRAPH DRAWING, 1996, 1027 : 385 - 395
  • [30] PACKING AND COVERING A GIVEN DIRECTED GRAPH IN A DIRECTED GRAPH
    Yuster, Raphael
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2024, 38 (01) : 43 - 54