Inapproximability of dominating set on power law graphs

被引：15
|
作者：
Gast, Mikael [1 ,2 ]
Hauptmann, Mathias [1 ]
Karpinski, Marek [1 ,3 ]
机构：
[1] Univ Bonn, Dept Comp Sci, Bonn, Germany
[2] B IT Res Sch, Dresden, Germany
[3] Univ Bonn, Hausdorff Ctr Math, Bonn, Germany
来源：
THEORETICAL COMPUTER SCIENCE | 2015年 / 562卷
关键词：
Approximation algorithms; Inapproximability; Power law graphs; Combinatorial optimization; Dominating set; MODELS; WEB;
D O I：
10.1016/j.tcs.2014.10.021
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We prove the first logarithmic lower bounds for the approximability of the MINIMUM DOMINATING SET problem for the case of connected (alpha, beta)-power law graphs for a being a size parameter and beta the power law exponent. We give also a best up to now upper approximation bound for this problem in the case of the parameters beta > 2. We develop also a new functional method for proving lower approximation bounds and display a sharp approximation phase transition area between approximability and inapproximability of the underlying problems. Our results depend on a method which could be also of independent interest. (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码：436 / 452
页数：17
相关论文
共 50 条
  • [41] Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
    de Figueiredo, Celina M. H.
    Lopes, Raul
    de Melo, Alexsander A.
    Silva, Ana
    NETWORKS, 2024, 84 (02) : 132 - 147
  • [42] On the complexity of the minimum outer-connected dominating set problem in graphs
    Pradhan, D.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (01) : 1 - 12
  • [43] The dominating set problem is fixed parameter tractable for graphs of bounded genus
    Ellis, J
    Fan, H
    Fellows, M
    ALGORITHM THEORY - SWAT 2002, 2002, 2368 : 180 - 189
  • [44] Approximating dominating set on intersection graphs of rectangles and L-frames
    Bandyapadhyay, Sayan
    Maheshwari, Anil
    Mehrabi, Saeed
    Suri, Subhash
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2019, 82 : 32 - 44
  • [45] Dominating set is fixed parameter tractable in claw-free graphs
    Cygan, Marek
    Philip, Geevarghese
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Wojtaszczyk, Jakub Onufry
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (50) : 6982 - 7000
  • [46] Edge dominating set and colorings on graphs with fixed clique-width
    Kobler, D
    Rotics, U
    DISCRETE APPLIED MATHEMATICS, 2003, 126 (2-3) : 197 - 221
  • [47] Parameterized dominating set problem in chordal graphs: complexity and lower bound
    Chunmei Liu
    Yinglei Song
    Journal of Combinatorial Optimization, 2009, 18 : 87 - 97
  • [48] On the complexity of the minimum outer-connected dominating set problem in graphs
    D. Pradhan
    Journal of Combinatorial Optimization, 2016, 31 : 1 - 12
  • [49] Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
    Czygrinow, Andrzej
    Hanckowiak, Michal
    Wawrzyniak, Wojciech
    Witkowski, Marcin
    THEORETICAL COMPUTER SCIENCE, 2020, 809 (809) : 327 - 338
  • [50] Approximating the Minimum Connected Dominating Set in Stochastic Graphs Based on Learning Automata
    Torkestani, J. Akbari
    Meybodi, M. R.
    2009 INTERNATIONAL CONFERENCE ON INFORMATION MANAGEMENT AND ENGINEERING, PROCEEDINGS, 2009, : 672 - +
12345