Exact and Approximate Algorithms for the Most Connected Vertex Problem

Abstract

An (edge) hidden graph is a graph whose edges are not explicitly given. Detecting the presence of an edge requires an expensive edge probing query. We consider the k Most Connected Vertex (k-MCV) problem on hidden bipartite graphs. Given a bipartite graph G with independent vertex sets B and W, the goal is to find the k vertices in B with the largest degrees using the minimum number of queries. This problem can be regarded as a top-k extension of semi-join, and is encountered in several applications in practice. If B and W have n and m vertices, respectively, the number of queries needed to solve the problem is nm in the worst case. This, however, is a pessimistic estimate on how many queries are necessary on practical data. In fact, on some inputs, the problem may be settled with only km + n queries, which is significantly lower than nm for k << n. The huge difference between km + n and nm makes it interesting to design an adaptive algorithm that is guaranteed to achieve the best possible performance on every input G. For k <= n/2, we give an algorithm that is instance optimal among a broad class of solutions. This means that, for any G, our algorithm can perform more queries than the optimal solution ( which is unknown) by only a constant factor, which can be shown at most 2. As a second step, we study an epsilon-approximate version of the k-MCV problem, where epsilon is a parameter satisfying 0 < epsilon < 1. The goal is to return k black vertices b(1), . . . , b(k) such that the degree of b(i) (i <= k) can be smaller than t(i) by a factor of at most epsilon, where t(1), . . . , t(k) ( in nonascending order) are the degrees of the k most connected black vertices. We give an efficient randomized algorithm that successfully finds the correct answer with high probability. In particular, for a fixed epsilon and a fixed success probability, our algorithm performs o(nm) queries in expectation for t(k) = omega(log n). In other words, whenever t(k) is greater than log n by more than a constant, our algorithm beats the Omega(nm) lower bound for solving the k-MCV problem exactly. All the proposed algorithms, despite the complication of their underlying theory, are simple enough for easy implementation in practice. Extensive experiments have confirmed that their performance in reality agrees with our theoretical findings very well.