The energy minimization problem for undirected graphical models, also known as MAP-inference for Markov random fields (MRFs), is in general NP-hard. We propose a polynomial time algorithm to obtain a part of its optimal nonrelaxed integral solution. Our method works by starting with variables from a convex relaxation solution and iteratively removing (pruning) variables that do not meet our partial optimality criteria. The approach leverages existing solvers for the relaxed problem and is applicable to models with arbitrary factors of an arbitrary order — a level of generality not achieved by prior partial optimality methods. Empirically, our pruning strategy outperforms previous approaches regarding the number of persistently labeled variables, and its runtime is determined by the underlying convex relaxation solver.

MAP-inference in graphical models is a fundamental computational problem in computer vision with applications ranging from stereo matching, optical flow, image segmentation, to object recognition. Given the NP-hardness of the general problem, two main approaches have emerged: approximate inference methods (e.g., message passing, graph cuts) that find good but potentially suboptimal solutions, and convex relaxation methods (e.g., LP relaxation) that provide lower bounds but may yield fractional (non-integer) solutions. A third avenue, which we pursue, is partial optimality: the goal is to identify a subset of variables whose optimal labels can be determined with certainty, even when the complete solution cannot be efficiently computed. Prior methods for partial optimality, such as QPBO (roof duality), are limited to binary variables and pairwise factors.

A graphical model (or factor graph) consists of variables X = {x_1, ..., x_n}, each taking values in a discrete label set, and factors (or potentials) that encode local dependencies. The MAP-inference problem seeks the labeling that minimizes the sum of all factor costs: argmin_x sum_f theta_f(x_f). The LP relaxation replaces integer constraints with their convex hull, yielding a lower bound on the optimal energy. When the LP solution is integral (all variables take integer values), it is provably optimal. When it is fractional, only a subset of variables may be at integral values, and the question becomes: which of these integral variables can be guaranteed to retain their values in the true optimal solution? This is the partial optimality question.

Our approach is based on a simple but powerful principle: we can certify that a variable takes a specific label in the optimal solution by showing that assigning any other label would increase the energy beyond the LP lower bound. Formally, for each variable x_i and each candidate label l, we fix x_i = l and re-solve the LP relaxation for the remaining variables. If the resulting lower bound exceeds the best known upper bound (from any feasible integer solution), then label l can be pruned — it is guaranteed not to appear in any optimal solution. When all labels but one are pruned for a variable, that variable is persistently labeled — its optimal assignment is determined. The iterative pruning process continues until no more labels can be eliminated.

We establish several theoretical properties of our pruning approach. First, the method is correct: any variable persistently labeled by our algorithm is guaranteed to take that label in all optimal solutions — not just one optimal solution, but every optimal solution (in case of ties). Second, the method is applicable to graphical models with factors of arbitrary order, including higher-order potentials (triplets, quadruplets, etc.) that arise in many vision applications. Third, our pruning subsumes the classical QPBO (roof duality) method as a special case when restricted to binary pairwise models. Fourth, the computational complexity is polynomial in the problem size, as each pruning step involves solving an LP relaxation (polynomial) and the total number of pruning iterations is bounded.

The practical algorithm proceeds in several phases. First, an initial LP relaxation is solved using an off-the-shelf solver (e.g., TRW-S, MPLP, or CPLEX). Second, a feasible integer solution is obtained (e.g., by rounding the LP solution or running a local search heuristic) to establish an upper bound. Third, the pruning loop iterates over all variables and labels: for each, the LP is re-solved with the variable fixed, and labels whose lower bound exceeds the upper bound are removed. The algorithm exploits several efficiency optimizations: variables that are already integral in the relaxation are checked first (they are most likely to be prunable), and the LP re-optimization warm-starts from the previous solution, making each iteration much cheaper than a cold start.

We evaluate on standard MRF benchmarks including stereo matching (Tsukuba, Venus, Teddy) and image segmentation problems from the OpenGM benchmark. The key metric is the percentage of persistently labeled variables — higher is better, as it means more of the solution is guaranteed optimal. Our method persistently labels significantly more variables than QPBO and its extensions, particularly on multi-label and higher-order models where QPBO is inapplicable. On stereo matching instances, we achieve persistent labeling rates exceeding 90% in many cases, meaning the vast majority of pixel disparities are provably optimal. The runtime overhead of pruning is modest relative to the LP relaxation itself, typically adding only 20-50% to the total computation time.

We have presented a pruning-based approach to partial optimality for MAP-inference in general graphical models. Our method provably identifies variables whose optimal labels can be determined in polynomial time, extending partial optimality guarantees from binary pairwise models to models with arbitrary factors and label spaces. The practical impact is substantial: on standard vision benchmarks, the majority of variables can be persistently labeled, effectively reducing the hard combinatorial problem to a much smaller residual. By bridging the gap between convex relaxation solutions and integral optimal solutions, our approach provides a principled way to extract reliable partial information from intractable optimization problems.