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 条
  • [1] Editing to a Graph of Given Degrees
    Golovach, Petr A.
    THEORETICAL COMPUTER SCIENCE, 2015, 591 : 72 - 84
  • [2] Editing to a Connected Graph of Given Degrees
    Golovach, Petr A.
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE, PT II, 2014, 8635 : 324 - 335
  • [3] Editing to a planar graph of given degrees
    Dabrowski, Konrad K.
    Golovach, Petr A.
    van 't Hof, Pim
    Paulusma, Daniel
    Thilikos, Dimitrios M.
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 85 : 168 - 182
  • [4] Editing to a connected graph of given degrees
    Golovach, Petr A.
    INFORMATION AND COMPUTATION, 2017, 256 : 131 - 147
  • [5] Graph Editing to a Given Degree Sequence
    Golovach, Petr A.
    Mertzios, George B.
    COMPUTER SCIENCE - THEORY AND APPLICATIONS, CSR 2016, 2016, 9691 : 177 - 191
  • [6] Graph editing to a given degree sequence
    Golovach, Petr A.
    Mertzios, George B.
    THEORETICAL COMPUTER SCIENCE, 2017, 665 : 1 - 12
  • [7] Parameterized graph editing with chosen vertex degrees
    Mathieson, Luke
    Szeider, Stefan
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2008, 5165 : 13 - 22
  • [8] The Greedy Independent Set in a Random Graph with Given Degrees
    Brightwell, Graham
    Janson, Svante
    Luczak, Malwina
    RANDOM STRUCTURES & ALGORITHMS, 2017, 51 (04) : 565 - 586
  • [9] THE PROBABILISTIC PROPERTIES OF A RANDOM GRAPH WITH A GIVEN SET OF DEGREES OF THE VERTICES
    MIRONOV, AA
    SOVIET JOURNAL OF COMPUTER AND SYSTEMS SCIENCES, 1991, 29 (03): : 51 - 59
  • [10] A Note on the Markovian SIR Epidemic on a Random Graph with Given Degrees
    Luczak, Malwina
    JOURNAL OF THEORETICAL PROBABILITY, 2024, 37 (02) : 1039 - 1051