Combinatorial characteristics of polytopes associated with combinatorial optimization problems can be considered to some extent as the intractability characteristics of these problems. For example, the $NP$-completeness of verifying the nonadjacency of vertices in the polytope of a problem quite often accompanies the $NP$-hardness of the problem. Another important characteristic of the polytope graph of a problem is its clique number. For a rather wide class of algorithms, the clique number is a lower bound for the time complexity of the problem. In addition, for the clique number of polytope graphs, there are known exponential lower bounds for a large number of intractable problems and known polynomial upper and lower bounds for problems solvable in polynomial time. In the present paper we consider the polytope of the problem on a weighted connected spanning $k$-regular subgraph (a connected $k$-factor) of a complete $n$-vertex graph; for $k=2$, this is the polytope of the symmetric traveling salesman problem. For the values of $k$ satisfying the conditions $k\geq 3$ and $\lceil k/2 \rceil \leq n/8 - 1$, we show that the problem of verifying the nonadjacency of vertices of this polytope is $NP$-complete and the clique number is exponential in $n$. The proofs are based on the reduction to the case $k=2$.
Keywords: $k$-factor, polytope, adjacency of vertices, clique number of a graph.
The paper was received by the Editorial Office on February 5, 2018.
Funding Agency:
Russian Foundation for Basic Research (Grant Number 18-07-00599).
Ruslan Yur’evich Simanchev, Cand. Sci. (Phys.-Math.), Omsk State University, Omsk, 644077 Russia; Omsk Scientific Center SB RAS, Omsk, 644040 Russia; Omsk State University, Omsk, 644077 Russia, e-mail: osiman@rambler.ru.
REFERENCES
1. Padberg M.W., Rinaldi G. A Branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 1991, vol. 33, no. 1, pp. 60–100. doi: 10.1137/1033004 .
2. Grotschel M., Holland O. Solution of large-scale symmetric traveling salesman problems. Math. Progr., 1991, vol. 51, no. 1-3, pp. 141–202. doi: 10.1007/BF01586932 .
3. Crowder H., Johnson E.L., Padberg M.W. Solving large-scale zero-one linear programming problems. Operations Research, 1983, vol. 31, no. 5, pp. 803–834. doi: 10.1287/opre.31.5.803 .
4. Simanchev R.Yu., Urazova I.V. Cutting planes algorithm for the connected k-factor problem using the facet inequalities [e-resource]. Proc. OPTIMA-2017 Conf., Yu.G. Evtushenko, M.Yu. Khachay, O.V. Khamisov, Yu.A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.), 2017, pp. 517–523. Available at: http://ceur-ws.org/Vol-1987/paper74.pdf .
5. Grotschel M., Wakabayashi Y. A cutting plane algorithm for a clustering problem. Math. Progr., 1989, vol. 45, no. 1–3, pp. 59–96. doi: 10.1007/BF01589097 .
6. Bondarenko V.A., Maksimenko A.N. Geometricheskie konstrukcii i slozhnost’ v kombinatornoj optimizacii. [Geometric constructions and complexity in combinatorial optimization]. Moscow: LKI Publ., 2008, 184 p. ISBN: 978-5-382-00687-1 .
7. Papadimitriou C. H. The adjacency relation on the traveling salesman polytope is NP-complete. Math. Progr., 1978, vol. 14, no. 1, pp. 312–324. doi: 10.1007/BF01588973 .
8. Bondarenko V.A. Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms. Autom. Remote Control, 1983, vol. 44, no. 1, pp. 1137–1142.
9. Edmonds J. Maximum matching and a polyhedron with 0,1-vertices. J. Research National Bureau Standards, Sec. B, 1965, vol. 69, pp. 125–130.
10. Araoz J., Cunningham W.H., Edmonds J., Green-Krotki J. Reductions to 1-matching Polyhedra. Networks, 1983, vol. 13, pp. 455–473. doi: 10.1002/net.3230130403 .
11. Gerards A.M.H. Matching. Handbooks in Operations Research and Management Science, M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhause (eds.), Amsterdam: Elsevier, 1995, vol. 7, pp. 135–224. doi: 10.1016/S0927-0507(05)80120-3 .
12. Mel’nikov O., Tyshkevich R.I., Emelichev V.A., Sarvanov V.I. Lectures on graph theory. Mannheim: B.I. Wissenschaftsverlag. 1994, 371 p. ISBN: 3-411-17121-9 . Oroginal Russian text published in Emelichev V.A. et al. Lekcii po teorii grafov, Moscow, Nauka Publ., 1990, 384 p.
13. Maksimenko A.N. The common face of some 0/1-polytopes with NP-complete nonadjacency relation. J. Math. Sci., 2014, vol. 203, no. 6, pp. 823–832. doi: 10.1007/s10958-014-2172-9 .
