Chauhan, Ankit ;
Friedrich, Tobias ;
Rothenberger, Ralf
Greed is Good for Deterministic ScaleFree Networks
Abstract
Large realworld networks typically follow a powerlaw degree distribution. To study such networks, numerous random graph models have been proposed. However, realworld networks are not drawn at random. In fact, the behavior of realworld 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 powerlaw upper bound on the degree distribution (PLBU) and (2) powerlaw neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLBN). They showed that many realworld 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 wellstudied random graph models exhibit both the mentioned PLB properties and additionally also a powerlaw lower bound on the degree distribution (PLBL). All three properties hold with high probability for ChungLu 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 ChungLu 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 NPhard 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 PLBU property suffices such that the greedy approach achieves a constantfactor approximation for all three problems. We also show that all three combinatorial optimization problems are APXcomplete, even if all PLBproperties 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 ScaleFree Networks}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {33:133:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770279},
ISSN = {18688969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6868},
URN = {urn:nbn:de:0030drops68682},
doi = {10.4230/LIPIcs.FSTTCS.2016.33},
annote = {Keywords: random graphs, powerlaw degree distribution, scalefree networks, PLB networks, approximation algorithms, vertex cover, dominating set, independent s}
}
2016
Keywords: 

random graphs, powerlaw degree distribution, scalefree networks, PLB networks, approximation algorithms, vertex cover, dominating set, independent s 
Seminar: 

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Issue date: 

2016 
Date of publication: 

2016 