# 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.