The class of the labeling problems is NP-complete. An approach to the partial optimal labeling search for an arbitrary labeling problem is proposed. The approach is based on the solution of the auxiliary supermodular (max,+) problems, which are poli- nomially solvable.