License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.33
URN: urn:nbn:de:0030-drops-68682
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6868/
Chauhan, Ankit ;
Friedrich, Tobias ;
Rothenberger, Ralf
Greed is Good for Deterministic Scale-Free Networks
Abstract
Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. In fact, the behavior of real-world networks and random graph models can be the complete opposite of one another, depending on the considered property. Brach, Cygan, Lacki, and Sankowski [SODA 2016] introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world networks satisfy both deterministic properties and exploit them to design faster algorithms for a number of classical graph problems like transitive closure, maximum matching, determinant, PageRank, matrix inverse, counting triangles and maximum clique.
We complement the work of Brach et al. by showing that some well-studied random graph models exhibit both the mentioned PLB properties and additionally also a power-law lower bound on the degree distribution (PLB-L). All three properties hold with high probability for Chung-Lu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As a consequence, all results of Brach et al. also hold with high probability for Chung-Lu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs.
In the second part of this work we study three classical NP-hard combinatorial optimization problems on PLB networks. It is known that on general graphs, a greedy algorithm, which chooses nodes in the order of their degree, only achieves an approximation factor of asymptotically at least logarithmic in the maximum degree for Minimum Vertex Cover and Minimum Dominating Set, and an approximation factor of asymptotically at least the maximum degree for Maximum Independent Set. We prove that the PLB-U property suffices such that the greedy approach achieves a constant-factor approximation for all three problems. We also show that all three combinatorial optimization problems are APX-complete, even if all PLB-properties hold. Hence, a PTAS cannot be expected, unless P=NP.
BibTeX - Entry
@InProceedings{chauhan_et_al:LIPIcs:2016:6868,
author = {Ankit Chauhan and Tobias Friedrich and Ralf Rothenberger},
title = {{Greed is Good for Deterministic Scale-Free Networks}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {33:1--33:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-027-9},
ISSN = {1868-8969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6868},
URN = {urn:nbn:de:0030-drops-68682},
doi = {10.4230/LIPIcs.FSTTCS.2016.33},
annote = {Keywords: random graphs, power-law degree distribution, scale-free networks, PLB networks, approximation algorithms, vertex cover, dominating set, independent s}
}
|
Keywords: |
|
random graphs, power-law degree distribution, scale-free networks, PLB networks, approximation algorithms, vertex cover, dominating set, independent s |
|
Collection: |
|
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
10.12.2016 |
