The Wiener index of a graph is the sum of all pairwise shortest-path distances between its vertices. In this paper we study the novel problem of finding a minimum Wiener connector : given a connected graph G = (V, E) and a set Q ⊆ V of query vertices, find a subgraph of G that connects all query vertices and has minimum Wiener index. We show that Min Wiener Connector admits a polynomial-time (albeit impractical) exact algorithm for the special case where the number of query vertices is bounded. We show that in general the problem is NP-hard, and has no PTAS unless P = NP. Our main contribution is a constantfactor approximation algorithm running in time O(|Q||E|). A thorough experimentation on a large variety of realworld graphs confirms that our method returns smaller and denser solutions than other methods, and does so by adding to the query set Q a small number of "important" vertices (i.e., vertices with high centrality).
The minimum wiener connector problem is finding a small connected subgraph to minimize the sum of all pairwise shortest-path distances between the discovered vertices REF .
The Minimum Wiener Connector Problem
SIGMOD '15
Computer Science Mathematics