Structural recognition and a class of solvable MaxSum problems.

Boris Flach (TU Dresden, Germany)

A large number of structural recognition problems can be reduced to a MaxSum Problem for labellings on a graph (e.g. surface reconstruction using stereo images, various image segmentation problems, finding the maximum a-posteriori labelling for a Markov-Random-Field and so on). Despite of the well known fact of NP-completeness of the MaxSum Problem, it is therefore necessary to search for subclasses solvable with polynomial time complexity. We enlarge the widest class of such problems known so far (found by Ishikava et.al.) substantially. We show that any problem within this enlarged class can be equivalently transformed into a linear optimisation problem. The corresponding dual problem turns out to be a MaxPreflow problem and is therefore solvable with polynomial time complexity.