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 条
  • [31] PTAS for the minimum weighted dominating set in growth bounded graphs
    Zhong Wang
    Wei Wang
    Joon-Mo Kim
    Bhavani Thuraisingham
    Weili Wu
    Journal of Global Optimization, 2012, 54 : 641 - 648
  • [32] PTAS for the minimum weighted dominating set in growth bounded graphs
    Wang, Zhong
    Wang, Wei
    Kim, Joon-Mo
    Thuraisingham, Bhavani
    Wu, Weili
    JOURNAL OF GLOBAL OPTIMIZATION, 2012, 54 (03) : 641 - 648
  • [33] Polynomial Kernels for Dominating Set in Graphs of Bounded Degeneracy and Beyond
    Philip, Geevarghese
    Raman, Venkatesh
    Sikdar, Somnath
    ACM TRANSACTIONS ON ALGORITHMS, 2012, 9 (01)
  • [34] Refined search tree technique for DOMINATING SET on planar graphs
    Alber, J
    Fan, HB
    Fellows, MR
    Fernau, H
    Niedermeier, R
    Rosamond, F
    Stege, U
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2001, 2001, 2136 : 111 - 122
  • [35] Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors
    Fomin, Fedor V.
    Lokshtanov, Daniel
    Saurabh, Saket
    Thilikos, Dimitrios M.
    ACM TRANSACTIONS ON ALGORITHMS, 2018, 14 (01)
  • [36] A refined search tree technique for Dominating Set on planar graphs
    Alber, J
    Fan, HB
    Fellows, MR
    Fernau, H
    Niedermeier, R
    Rosamond, F
    Stege, U
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2005, 71 (04) : 385 - 405
  • [37] Approximability of the vertex cover problem in power-law graphs
    Gast, Mikael
    Hauptmann, Mathias
    THEORETICAL COMPUTER SCIENCE, 2014, 516 : 60 - 70
  • [38] Minimum Power Dominating Sets of Random Cubic Graphs
    Kang, Liying
    Wormald, Nicholas
    JOURNAL OF GRAPH THEORY, 2017, 85 (01) : 152 - 171
  • [39] Parameterized dominating set problem in chordal graphs: complexity and lower bound
    Liu, Chunmei
    Song, Yinglei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (01) : 87 - 97
  • [40] On the complexity of the minimum outer-connected dominating set problem in graphs
    Pradhan, D.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (01) : 1 - 12
12345