bH-BASES FOR A SOME CLASS OF FACET OF A CLIQUE PARTITIONING POLYTOPE
Ruslan Yu. Simanchev, P.V. SOLOVIOVA · Matematičeskie struktury i modelirovanie · 2018
Let Kn=(V,E) be a complete undirected \protect\lb n-vertex graph without loops and multiple edges. A spanning subgraph H⊂Kn is called an M-graph if each of its connected components (possibly single-vertex) is a clique. In other words, every M-graph is a regular partition of Kn into vertex-disjoint cliques. The family of all M-graphs in Kn is denoted by H. This family is the set of feasible solutions to the clique partition problem, which consists in finding an M-graph of minimum weight \cite{GroWak1990,GroWak1989,SU1} in a complete edge-weighted graph. The mentioned works consider the polyhedral properties \cite{GroPad1985} of this problem, namely, they construct classes of inequalities generating faces of the problem polyhedron, on the basis of which branch and cut algorithms are developed. In this paper, using the technique proposed in \cite{Sim2017}, we prove the facet property of inequalities of a special class with respect to the polyhedron of the clique partition problem. \\\textit{This work was supported by the Russian Foundation for Basic Research (project 18-07-00599).}