On the vertex adjacency in a polytope of connected k-factors

R. Yu. Simanchev

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 2, pp. 235-242

Résumé

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$.

Détail

Keywords: k-factor, polytope, adjacency of vertices, clique number of a graph.