Vertex Cover In Complex Networks

AMinimum Vertex Coveris the smallest set of vertices whose removal completely disconnects a graph. In this paper, we perform experiments on a number of graphs from standard complex networks databases addressing the problem of finding a "good" vertex cover (finding an optimum is a NP-Hard problem). In particular, we take advantage of the ubiquitous power law distribution present on many complex networks. In our experiments, we show that running a greedy algorithm in apower law graphwe can obtain a very small vertex cover typically about 1.02 times the theoretical optimum. This is an interesting practical result since theoretically we know that: (1) In a general graph, onnvertices a greedy approach cannot guarantee a factor better than lnn; (2) The best approximation algorithm known at the moment is very involved and has a much larger factor of$2 - \Theta(\frac{1}{\sqrt{\log n}})$. In fact, in the context of approximation within a constant factor, it is conjectured that there is no (2 – ϵ)-approximation algorithm for the problem; (3) Even restricted to power law graphs and probabilistic guarantees, the best known approximation rate is 1.5.