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 条
  • [1] Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
    Liu, Chunmei
    Song, Yinglei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2011, 22 (04) : 684 - 698
  • [2] On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
    Shen, Yilin
    Nguyen, Dung T.
    Thai, My T.
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PT 1, 2010, 6508 : 197 - 211
  • [3] Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
    Chunmei Liu
    Yinglei Song
    Journal of Combinatorial Optimization, 2011, 22 : 684 - 698
  • [4] THE CONSTANT INAPPROXIMABILITY OF THE PARAMETERIZED DOMINATING SET PROBLEM
    Chen, Yijia
    Lin, Bingkai
    SIAM JOURNAL ON COMPUTING, 2019, 48 (02) : 513 - 533
  • [5] The Constant Inapproximability of the Parameterized Dominating Set Problem
    Chen, Yijia
    Lin, Bingkai
    2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, : 505 - 514
  • [6] On dominating set of some subclasses of string graphs
    Chakraborty, Dibyayan
    Das, Sandip
    Mukherjee, Joydeep
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2022, 107
  • [7] Distributed Dominating Set Approximations beyond Planar Graphs
    Amiri, Saeed Akhoondian
    Schmid, Stefan
    Siebertz, Sebastian
    ACM TRANSACTIONS ON ALGORITHMS, 2019, 15 (03)
  • [8] New Results on Polynomial Inapproximability and Fixed Parameter Approximability of EDGE DOMINATING SET
    Escoffier, Bruno
    Monnot, Jerome
    Paschos, Vangelis Th.
    Xiao, Mingyu
    THEORY OF COMPUTING SYSTEMS, 2015, 56 (02) : 330 - 346
  • [9] Finding a dominating set on bipartite graphs
    Liedloff, Mathieu
    INFORMATION PROCESSING LETTERS, 2008, 107 (05) : 154 - 157
  • [10] The fixed set search applied to the power dominating set problem
    Jovanovic, Raka
    Voss, Stefan
    EXPERT SYSTEMS, 2020, 37 (06)
12345