Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing non-optimal outputs) for an improved running time. For the vertex cover problem, there is a gap between theory and practice when it comes to understanding this tradeoff. On the one hand, it is known that it is NP-hard to approximate a minimum vertex cover within a factor of $\sqrt{2}$. On the other hand, a simple greedy algorithm yields close to optimal approximations in practice.

A promising approach towards understanding this discrepancy is to recognize the differences between theoretical worst-case instances and real-world networks. Following this direction, we close the gap between theory and practice by providing an algorithm that efficiently computes nearly optimal vertex cover approximations on hyperbolic random graphs; a network model that closely resembles real-world networks in terms of degree distribution, clustering, and the small-world property. More precisely, our algorithm computes a (1+o(1))-approximation, asymptotically almost surely, and has a running time of $\mathcal{O}(m \log(n))$.

... mehr

A promising approach towards understanding this discrepancy is to recognize the differences between theoretical worst-case instances and real-world networks. Following this direction, we close the gap between theory and practice by providing an algorithm that efficiently computes nearly optimal vertex cover approximations on hyperbolic random graphs; a network model that closely resembles real-world networks in terms of degree distribution, clustering, and the small-world property. More precisely, our algorithm computes a (1+o(1))-approximation, asymptotically almost surely, and has a running time of $\mathcal{O}(m \log(n))$.

... mehr

Zugehörige Institution(en) am KIT |
Institut für Theoretische Informatik (ITI) |

Publikationstyp |
Forschungsbericht/Preprint |

Publikationsjahr |
2021 |

Sprache |
Englisch |

Identifikator |
KITopen-ID: 1000138405 |

Nachgewiesen in |
arXiv |

Relationen in KITopen |

KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft

KITopen Landing Page