A necessary condition for facetness of comb inequalities for a polytope of connected \(2k\)-factors (Q2713883)

For many combinatorial optimization problems, it is worth studying a polytope of connected \(k\)-factors of a complete graph. For \(k=2\), it is a polytope of Hamiltonian cycles for the symmetric traveling salesman problem. It was shown by \textit{M.~Grötschel} and \textit{M.~W.~Padberg} [Math. Program. 16, 265-280 and 281-302 (1979; Zbl 0413.90048 and Zbl 0413.90049)] that, for \(k=2\), the comb inequalities generate facets of a polytope for the symmetric travelling salesman problem. In the article under review, arbitrary even factors are studied. The author presents a necessary condition under which a comb inequality defines a facet of the polytope. A sufficient condition was obtained by \textit{R.~Yu.~Simanchev} [Diskretn. Anal. Issled. Oper. 3, No.~3, 84-110 (1996; Zbl 0915.05095)].NEWLINENEWLINEFor the entire collection see [Zbl 0935.00013].