Approximation Algorithm for the Minimum Hub Cover Set Problem

A subset S subset of V of vertices of an undirected graph G = (V, E) is a hub cover when for each edge (u, v) is an element of E, at least one of its endpoints belongs to S, or there exists a vertex r is an element of 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 In mu, where mu is upper bounded by min{1/2(Delta + 1)(2), vertical bar E vertical bar} and Delta is the degree of G. The execution time of psi-MHC is O((Delta + 1)vertical bar E vertical bar + vertical bar S vertical bar vertical bar E vertical bar). Experimental results show that klf-MHC far outperforms the theoretical approximation ratio for the input graph instances.

Automated summary

This paper proposes the first approximation algorithm for computing the minimum hub cover set in arbitrary graphs. Experimental results show that the algorithm outperforms the theoretical approximation ratio for the input graph instances.