The Most Reliable Subgraph Problem

摘要

We introduce the problem of finding the most reliable subgraph: given a probabilistic graph G subject to random edge failures, a set of terminal vertices, and an integer K, find a subgraph H is contained in G having K fewer edges than G, such that the probability of connecting the terminals in H is maximized. The solution has applications in link analysis and visualization. We begin by formally defining the problem in a general form, after which we focus on a two-terminal, undirected case. Although the problem is most likely computationally intractable, we give a polynomial-time algorithm for a special case where G is series-parallel. For the general case, we propose a computationally efficient greedy heuristic. Our experiments on simulated graphs illustrate the usefulness of the concept of most reliable subgraph, and suggest that the heuristic for the general case is quite competitive.