Maximum persistency in energy minimization

We consider discrete pairwise energy minimization prob-lem (weighted constraint satisfaction, max-sum labeling) and methods that identify a globally optimal partial assign-ment of variables. When finding a complete optimal assign-ment is intractable, determining optimal values for a part of variables is an interesting possibility. Existing methods are based on different sufficient conditions. We propose a new sufficient condition for partial optimality which is: (1) ver-ifiable in polynomial time (2) invariant to reparametriza-tion of the problem and permutation of labels and (3) in-cludes many existing sufficient conditions as special cases. We pose the problem of finding the maximum optimal par-tial assignment identifiable by the new sufficient condition. A polynomial method is proposed which is guaranteed to assign same or larger part of variables than several ex-isting approaches. The core of the method is a specially constructed linear program that identifies persistent assign-ments in an arbitrary multi-label setting