Graph cut is a popular technique for interactive image segmentation.
However, it has certain shortcomings. In particular, graph cut
has problems with segmenting thin elongated objects due to the
``shrinking bias''. To overcome this problem, we propose to impose
an additional connectivity prior, which is a very natural assumption about objects.
We formulate several versions of the connectivity constraint and show
that the corresponding optimization problems are all NP-hard.
For some of these versions we propose two optimization algorithms: (i) a practical heuristic technique which we call DijkstraGC, and (ii) a slow method based on problem decomposition which provides a lower bound on the problem. We use the second technique to verify that for some practical examples DijkstraGC is able to find the global minimum.