4.5.2007 HIIT Seminar

HIIT seminars in spring 2007 will be held in hall **B222** of Exactum, on Fridays starting at 10:15 a.m. Coffee available from 10.

Fri May 4
Petteri Hintsanen
The Most Reliable Subgraph Problem

Abstract:
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 of 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 discovery and analysis, focused graph pruning, and graph 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 and real data illustrate the usefulness of the concept of most reliable subgraph, and suggest that the heuristic for the general case is quite competitive.