Sufficient conditions for the minimum of one class of extremal combinatorial problems

A class of nonlinear problems in combinatorial optimization is identified in which the behaviour of the functionalon the entire combinatorial set is dictated by its behaviour in a small vicinity. This leads to computationally effective sufficient conditions for local and global optimum. For illustration the problem of optimal graph decomposition is considered for which sufficient conditions are given; the difficulty of checking these is proportional to squared number of the graph vertices.