Approximation Algorithm for the Minimum Hub Cover Set Problem
Joel Antonio Trejo-Sánchez, Candelaria Sansores, Jesús García-Díaz, José Alberto Fernández‐Zepeda · IEEE Access · 2022
A subset S ⊆ V of vertices of an undirected graph G = (V,E) is a hub cover when for each edge (u, v) ∈ E, at least one of its endpoints belongs to S, or there exists a vertex r ∈ 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 APX-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 proportional to ln μ, where μ is upper bounded by min{1/2 Δ2, |E|} and Δ is the degree of G. The execution time of APX-MHC is O((Δ + 1)|E| + |S||V|). Experimental results show that APX-MHC far outperforms the theoretical approximation ratio for the input graph instances.