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 条
  • [21] Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
    Dory, Michal
    Ghaffari, Mohsen
    Ilchi, Saeed
    PROCEEDINGS OF THE 2022 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, PODC 2022, 2022, : 292 - 300
  • [22] Complexity and inapproximability results for the Power Edge Set problem
    Sonia Toubaline
    Claudia D’Ambrosio
    Leo Liberti
    Pierre-Louis Poirion
    Baruch Schieber
    Hadas Shachnai
    Journal of Combinatorial Optimization, 2018, 35 : 895 - 905
  • [23] Liar's Dominating Set in Unit Disk Graphs
    Jallu, Ramesh K.
    Jena, Sangram K.
    Das, Gautam K.
    COMPUTING AND COMBINATORICS (COCOON 2018), 2018, 10976 : 516 - 528
  • [24] Dominating set and hamiltonicity in claw-heavy graphs
    Cai, Junqing
    ARS COMBINATORIA, 2018, 141 : 21 - 27
  • [25] Approximating the minimum independent dominating set in perturbed graphs
    Tong, Weitian
    Goebel, Randy
    Lin, Guohui
    THEORETICAL COMPUTER SCIENCE, 2014, 554 : 275 - 282
  • [26] FAST ALGORITHMS FOR THE DOMINATING SET PROBLEM ON PERMUTATION GRAPHS
    TSAI, KH
    HSU, WL
    ALGORITHMICA, 1993, 9 (06) : 601 - 614
  • [27] A strengthened analysis of an algorithm for DOMINATING SET in planar graphs
    Hagerup, Torben
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (06) : 793 - 798
  • [28] A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
    Wawrzyniak, Wojciech
    INFORMATION PROCESSING LETTERS, 2014, 114 (03) : 94 - 98
  • [29] Improved approximations of independent dominating set in bounded degree graphs
    Alimonti, P
    Calamoneri, T
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 1997, 1197 : 2 - 16
  • [30] The Parameterized Complexity of Dominating Set and Friends Revisited for Structured Graphs
    Misra, Neeldhara
    Rathi, Piyush
    COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2019, 11532 : 299 - 310
12345