Geodesic
1-Skeletons of the spanning tree problems with additional constraints
Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 4, pp. 453-463.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we study polyhedral properties of two spanning tree problems with additional constraints. In the first problem, it is required to find a tree with a minimum sum of edge weights among all spanning trees with the number of leaves less than or equal to a given value. In the second problem, an additional constraint is the assumption that the degree of all nodes of the spanning tree does not exceed a given value. The recognition versions of both problems are NP-complete. We consider polytopes of these problems and their 1-skeletons. We prove that in both cases it is a NP-complete problem to determine whether the vertices of 1-skeleton are adjacent. Although it is possible to obtain a superpolynomial lower bounds on the clique numbers of these graphs. These values characterize the time complexity in a broad class of algorithms based on linear comparisons. The results indicate a fundamental difference between combinatorial and geometric properties of the considered problems from the classical minimum spanning tree problem.
Keywords: spanning tree, 1-skeleton, clique number, NP-complete problem, hamiltonian chain. 
@article{MAIS_2015_22_4_a0,
     author = {V. A. Bondarenko and A. V. Nikolaev and D. A. Shovgenov},
     title = {1-Skeletons of the spanning tree problems with additional constraints},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {453--463},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2015_22_4_a0/}
}
TY  - JOUR
AU  - V. A. Bondarenko
AU  - A. V. Nikolaev
AU  - D. A. Shovgenov
TI  - 1-Skeletons of the spanning tree problems with additional constraints
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2015
SP  - 453
EP  - 463
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2015_22_4_a0/
LA  - ru
ID  - MAIS_2015_22_4_a0
ER  - 
%0 Journal Article
%A V. A. Bondarenko
%A A. V. Nikolaev
%A D. A. Shovgenov
%T 1-Skeletons of the spanning tree problems with additional constraints
%J Modelirovanie i analiz informacionnyh sistem
%D 2015
%P 453-463
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2015_22_4_a0/
%G ru
%F MAIS_2015_22_4_a0
V. A. Bondarenko; A. V. Nikolaev; D. A. Shovgenov. 1-Skeletons of the spanning tree problems with additional constraints. Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 4, pp. 453-463. http://geodesic.mathdoc.fr/item/MAIS_2015_22_4_a0/

[1] Bondarenko V. A., “Complexity bounds for combinatorial optimization problems in one class of algorithms”, Russian Academy of Sciences Doklady Mathematics, 328:1 (1993), 22–24 (in Russian) | MR | Zbl

[2] Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost' v kombinatornoy optimizatsii, LKI, Moscow, 2008 (in Russian)

[3] Bondarenko V. A., Nikolaev A. V., “Combinatorial and Geometric Properties of the Max-Cut and Min-Cut Problems”, Doklady Mathematics, 88:2 (2013), 516–517 | DOI | DOI | MR | Zbl

[4] Papadimitriou C. H., Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1982 | MR | MR | Zbl

[5] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman Co., New York, NY, USA, 1979 | MR | MR | Zbl

[6] Rahman M. S., Kaykobad M., “Complexities of some interesting problems on spanning trees”, Information Processing Letters, 94:2 (2005), 93–97 | DOI | MR | Zbl

[7] Fernandes L. M., Gouveia L., “Minimal spanning trees with a constraint on the number of leaves”, European Journal of Operational Research, 104:1 (1998), 250–261 | DOI | Zbl

[8] Goemans M. X., “Minimum Bounded-Degree Spanning Trees”, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (2006), 273–282

[9] Salamon G., Wiener G., “On finding spanning trees with few leaves”, Information Processing Letters, 105:5 (2008), 164–169 | DOI | MR | Zbl

[10] Singh M., Lau L. C., “Approximating minimum bounded degree spanning trees to within one of optimal”, Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing (2007), 661–670 | MR | Zbl

[11] Brondsted A., An Introduction to Convex Polytopes, Springer-Verlag, 1983 | MR | MR | Zbl

[12] Martin R. K., “Using separation algorithms to generate mixed integer model reformulations”, Operations Research Letters, 10:3 (1991), 119–128 | DOI | MR | Zbl

[13] Belov Y. A., “O plotnosti grafa matroida”, Modeli issledovanija operacij v vychislitelnyh sistemah, Yaroslavl state university, Yaroslavl, 1985, 95–100 (in Russian)

[14] Fujie T., “The maximum-leaf spanning tree problem: Formulations and facets”, Networks, 43:4 (2004), 212–223 | DOI | MR | Zbl

[15] Papadimitriou C. H., “The Adjacency Relation on the Traveling Salesman Polytope is NP-Complete”, Mathematical Programming, 14:1 (1978), 312–324 | DOI | MR | Zbl