ICS Theory Group

ICS 269, Spring 2004: Theory Seminar

4 June 2004:
Optimal Net Subgraph Problems with Applications

Danny Z. Chen
Department of Computer Science and Engineering
University of Notre Dame
Notre Dame, IN 46556, USA

In this talk, we introduce an interesting geometric graph called multi-column graph in the d-dimensional space (d ≥ 3), and formulate two related combinatorial optimization problems called optimal net subgraph problems on such graphs. Our formulations model a number of applied problems such as medical image segmentation, surface reconstruction with a given topology, and metric labeling. We prove that the optimal net subgraph problems on general d-D multi-column graphs (d ≥ 3) are NP-hard. For several important special cases of these problems in d-D (d ≥ 3) that arise in real applications, we present deterministic polynomial time algorithms for computing optimal solutions. Our algorithmic techniques enable us to achieve optimal solutions for several applied problems in polynomial time, such as some surface reconstruction problems in 3-D and 4-D and medical image segmentation problems in 3-D and 4-D. It is interesting to note that a previous belief was that some of these applied problems were NP-hard, and the previously best known exact algorithms for these problems, even on relatively simple cases, take at least exponential time. Our approaches can be extended to higher dimensions and to other more challenging versions. Experimental results on segmenting real medical images have shown the effectiveness and efficiency of our algorithms.