11 December 2014, Theoretical Computer Science Seminar, David Garcia Soriano

Abstract

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\subseteq V of query vertices, find a subgraph of G that connects all query vertices and has minimum Wiener index. The problem falls naturally into the class of connectivity subgraphs, community search, and network design problems, and has potential applications in many scenarios, including visualization in online tools, finding community leaders, and finding bridges between communities. The Minimum Wiener Connector Problem admits a polynomial-time exact algorithm for the special case where the number of query vertices is bounded. We show that in the general case the problem is NP-hard and has no PTAS unless P=NP. Our main contribution is a constant-factor approximation algorithm running in time ~O(|Q||E|). A thorough experimentation on a large variety of real-world graphs confirms the practical efficiency and accuracy of our algorithm; our returned subgraphs are smaller and denser than those produced by other methods.

Joint work with Natali Ruchansky (Boston University), Francesco Bonchi (Yahoo Labs), Francesco Gullo (Yahoo Labs) and Nicolas Kourtellis (Yahoo Labs).

For more information, contact rdewolf at cwi.nl