Paper accepted at FSTTCS 2016
The Foundations of Software Technology and Theoretical Computer Science (FSTTCS) is the longest-running conference on computer science in India. It is hosted by the Indian Association for Research in Computing Science and dedicated to bringing together researchers from India and the world to present original results in foundational aspects of Computer Science and Software Technology.
The Algorithm Engineering group contributes the paper presented below.
Greed is Good for Deterministic Scale-Free Networks
Ankit Chauhan, Tobias Friedrich and Ralf Rothenberger
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 networks are not drawn at random. In fact, the behavior of real-world networks and random graph models can be completely opposite, depending on the property we look at. Brach, Cygan, Łącki, 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 degrees 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 a number of well-studied random graph classes exhibit both aforementioned 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, Geometric Inhomogeneous Random Graphs and Hyperbolic Random Graphs. All results of Brach et al. therefore also hold with high probability for these random graph classes.
In the second part of this work we study three classical NP-hard combinatorial optimization problems on deterministic PLB networks. It is known that on general graphs with maximum degree Δ, a greedy algorithm, which chooses nodes in the order of their degree, only achieves a Ω(ln Δ)-approximation for Minimum Vertex Cover and Minimum Dominating Set, and a Ω(Δ)-approximation 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 a PTAS cannot be expected, even if all three PLB-properties hold. For all three combinatorial optimization problems we prove APX-completeness for graphs with PLB-U, PLB-L and PLB-N property.