  Several important tasks in medical image analysis can be stated in the form
of an optimization problem whose feasible solutions are connected subgraphs.
Examples include the reconstruction of neural or vascular structures under
connectedness constraints. We discuss the minimum cost connected subgraph
(MCCS) problem and its approximations from the perspective of medical
applications. We propose a) objective-dependent constraints and b) novel
constraint generation schemes to solve this optimization problem exactly by
means of a branch-and-cut algorithm. These are shown to improve scalability and
allow us to solve instances of two medical benchmark datasets to optimality for
the first time. This enables us to perform a quantitative comparison between
exact and approximative algorithms, where we identify the geodesic tree
algorithm as an excellent alternative to exact inference on the examined
datasets.
