Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations
Source: University of Bologna
The authors prove new explicit in approximability results for the Vertex Cover Problem on the Power Law Graphs and some functional generalizations of that class of graphs. Their results depend on special bounded degree amplifier constructions for those classes of graphs and could be also of independent interest. Recently the study of large-scale real-world networks revealed common topological signatures and statistical features that are not easily captured by classical uniform random graphs such as generated by the G(n, p)- model due to Erdos and Rényi.