Geodesic
On the vertex adjacency in a polytope of connected k-factors
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 2, pp. 235-242 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{TIMM_2018_24_2_a21,
     author = {R. Yu. Simanchev},
     title = {On the vertex adjacency in a polytope of connected k-factors},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {235--242},
     year = {2018},
     volume = {24},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a21/}
}
TY  - JOUR
AU  - R. Yu. Simanchev
TI  - On the vertex adjacency in a polytope of connected k-factors
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2018
SP  - 235
EP  - 242
VL  - 24
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a21/
LA  - ru
ID  - TIMM_2018_24_2_a21
ER  - 
%0 Journal Article
%A R. Yu. Simanchev
%T On the vertex adjacency in a polytope of connected k-factors
%J Trudy Instituta matematiki i mehaniki
%D 2018
%P 235-242
%V 24
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a21/
%G ru
%F TIMM_2018_24_2_a21
R. Yu. Simanchev. On the vertex adjacency in a polytope of connected k-factors. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 2, pp. 235-242. http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a21/

[1] Padberg M. W., Rinaldi G., “A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems”, SIAM Review, 33:1 (1991), 60–100 | DOI | MR | Zbl

[2] Grotschel M., Holland O., “Solution of large-scale symmetric traveling salesman problems”, Math. Progr., 51:1–3 (1991), 141–202 | DOI | MR | Zbl

[3] Crowder H., Johnson E. L., Padberg M. W., “Solving large-scale zero-one linear programming problems”, Operations Research, 31:5 (1983), 803–834 | DOI | Zbl

[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. (Petrovac, Montenegro, October 2-7), 2017, 517–523 URL: http://ceur-ws.org/Vol-1987/paper74.pdf

[5] Grotschel M., Wakabayashi Y., “A cutting plane algorithm for a clustering problem”, Math. Progr., 45:1–3 (1989), 59–96 | DOI | MR | Zbl

[6] Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost v kombinatornoi optimizatsii, LKI, M., 2008, 184 pp.

[7] Papadimitriou C. H., “The adjacency relation on the traveling salesman polytope is NP-complete”, Math. Progr., 14:1 (1978), 312–324 | DOI | MR | Zbl

[8] Bondarenko V. A., “Nepolinomialnaya nizhnyaya otsenka slozhnosti zadachi kommivoyazhera v odnom klasse algoritmov”, Avtomatika i telemekhanika, 1983, no. 9, 45–50 | Zbl

[9] Edmonds J., “Maximum matching and a polyhedron with 0,1-vertices”, J. Research National Bureau Standards. Sec. B, 69 (1965), 125–130 | DOI | MR | Zbl

[10] J. Araoz, W. H. Cunningham, J. Edmonds, J. Green-Krotki, “Reductions to 1-matching polyhedra”, Networks, 13 (1983), 455–473 | DOI | MR | Zbl

[11] Gerards A. M. H., “Matching”, Handbooks in Operations Research and Management Science, 7, eds. eds. M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhause, Elsevier, Amsterdam, 1995, 135–224 | DOI

[12] V. A. Emelichev i dr., Lektsii po teorii grafov, Nauka, M., 1990, 384 pp. | MR

[13] Maksimenko A. N., “The common face of some 0/1-polytopes with NP-complete nonadjacency relation”, J. Math. Sci., 203:6 (2014), 823–832 | DOI | MR | Zbl