Approximation Algorithm for the Minimum Hub Cover Set Problem

Abstract

A subset ${\mathcal{ S}}\subseteq V$ of vertices of an undirected graph $G=(V,E)$ is a hub cover when for each edge $(u,v) \in E$ , at least one of its endpoints belongs to ${\mathcal{ S}}$ , or there exists a vertex $r \in {\mathcal{ S}}$ that is a neighbor of both $u$ and $v$ . The problem of computing a minimum hub cover set in arbitrary graphs is NP-hard. This problem has applications for indexing large databases. This paper proposes $\Psi $ -MHC, the first approximation algorithm for the minimum hub cover set in arbitrary graphs to the best of our knowledge. The approximation ratio of this algorithm is $\ln \mu $ , where $\mu $ is upper bounded by $\min \left\{{\frac {1}{2}(\Delta +1)^{2}, \vert E\vert }\right\}$ and $\Delta $ is the degree of $G$ . The execution time of $\Psi $ -MHC is $O((\Delta + 1) \vert E \vert + \vert {\mathcal{ S}} \vert \vert V \vert)$ . Experimental results show that $\Psi $ -MHC far outperforms the theoretical approximation ratio for the input graph instances.

Keywords

• Approximation algorithms
• heuristics
• minimum hub cover set
• optimization