VERTEX COVER IN COMPLEX NETWORKS

Mariana O. Da Silva (), Gustavo A. Gimenez-Lugo () and Murilo V. G. Da Silva ()
Additional contact information
Mariana O. Da Silva: DAINF, Universidade Tecnológica Federal do Paraná, Rua Sete de Setembro, 3164, Curitiba-PR, CEP 80230-901, Brazil
Gustavo A. Gimenez-Lugo: DAINF, Universidade Tecnológica Federal do Paraná, Rua Sete de Setembro, 3164, Curitiba-PR, CEP 80230-901, Brazil
Murilo V. G. Da Silva: DAINF, Universidade Tecnológica Federal do Paraná, Rua Sete de Setembro, 3164, Curitiba-PR, CEP 80230-901, Brazil

International Journal of Modern Physics C (IJMPC), 2013, vol. 24, issue 11, 1-9

Abstract: 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.

Keywords: Complex networks; power law graphs; vertex cover; greedy algorithms; 11.25.Hf; 123.1K (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183113500782
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:24:y:2013:i:11:n:s0129183113500782

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183113500782

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().