Abstract. A class of polynomially solvable problems of combinatorial optimization is treated. It is shown that this class includes certain problems with specially structured initial data. The reasoning is illustrated with the NP-hard traveling salesman problem.

Keywords: intractable problem, polynomial algorithm, NP-complete problem, traveling salesman problem, assignment problem, solvable subclass of problems, combinatorial optimization, matrix of Supnik, Kalmanson, Demidenko, and Monge.