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 条
  • [41] MINIMUM BLOCK CONTAINING A GIVEN GRAPH
    PLESNIK, J
    ARCHIV DER MATHEMATIK, 1976, 27 (06) : 668 - 672
  • [42] ON DEGREES OF VERTICES OF DIRECTED GRAPH
    HAKIMI, SL
    JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS, 1965, 279 (04): : 290 - &
  • [43] NUMBER OF EDGES IN A GRAPH OF A GIVEN RADIUS
    VIZING, VG
    DOKLADY AKADEMII NAUK SSSR, 1967, 173 (06): : 1245 - &
  • [44] VERTICES OF GIVEN DEGREE IN A RANDOM GRAPH
    BOLLOBAS, B
    JOURNAL OF GRAPH THEORY, 1982, 6 (02) : 147 - 155
  • [45] ON GRAPHS CONTAINING A GIVEN GRAPH AS CENTER
    BUCKLEY, F
    MILLER, Z
    SLATER, PJ
    JOURNAL OF GRAPH THEORY, 1981, 5 (04) : 427 - 434
  • [46] THE ADJACENCY GRAPH DETERMINED BY A GIVEN HYPERGRAPH
    Nath, Surajit Kr
    ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2020, 25 (01): : 11 - 21
  • [47] CHROMATIC NUMBER OF SUBGRAPHS OF A GIVEN GRAPH
    RODL, V
    PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1977, 64 (02) : 370 - 371
  • [48] GRAPH-GRAMMARS AND DIAGRAM EDITING
    GOTTLER, H
    LECTURE NOTES IN COMPUTER SCIENCE, 1987, 291 : 216 - 231
  • [49] EditKG: Editing Knowledge Graph for Recommendation
    Tang, Gu
    Gan, Xiaoying
    Wang, Jinghe
    Lu, Bin
    Wu, Lyuwen
    Fu, Luoyi
    Zhou, Chenghu
    PROCEEDINGS OF THE 47TH INTERNATIONAL ACM SIGIR CONFERENCE ON RESEARCH AND DEVELOPMENT IN INFORMATION RETRIEVAL, SIGIR 2024, 2024, : 112 - 122
  • [50] Susceptibility of random graphs with given vertex degrees
    Janson, Svante
    JOURNAL OF COMBINATORICS, 2010, 1 (04) : 357 - 387