1-Skeletons of the Spanning Tree Problems with Additional Constraints
https://doi.org/10.18255/1818-1015-2015-4-453-463
Abstract
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.
About the Authors
V. A. Bondarenko
P.G. Demidov Yaroslavl State University
Russian Federation
Russian Federation
doctor of science, professor
Sovetskaya str., 14, Yaroslavl, 150000, Russia
A. V. Nikolaev
P.G. Demidov Yaroslavl State University
Russian Federation
Russian Federation
PhD
Sovetskaya str., 14, Yaroslavl, 150000, Russia
D. A. Shovgenov
P.G. Demidov Yaroslavl State University
Russian Federation
Russian Federation
graduate student
Sovetskaya str., 14, Yaroslavl, 150000, Russia
References
1. Бондаренко В. А., “Оценки сложности задач комбинаторной оптимизации в одном классе алгоритмов”, Доклады Академии наук, 328:1 (1993), 22–24; [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).]
2. Бондаренко В. А., Максименко А. Н., Геометрические конструкции и сложность в комбинаторной оптимизации, ЛКИ, М., 2008, 184 с.; [Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost' v kombinatornoy optimizatsii, LKI, Moscow, 2008, (in Russian).]
3. Бондаренко В. А., Николаев А. В., “Комбинаторно-геометрические свойства задачи о разрезе”, Доклады Академии наук, 452:2 (2013), 127–129; [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]
4. Пападимитриу Х., Стайглиц К., Комбинаторная оптимизация: алгоритмы и сложность, Мир, М., 1985, 512 с.; [Papadimitriou C. H., Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1982.]
5. Гэри M., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, М., 1982, 416 с.; [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.]
6. Rahman M. S., Kaykobad M., “Complexities of some interesting problems on spanning trees”, Information Processing Letters, 94:2 (2005), 93–97.
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.
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.
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.
11. Бренстед А., Введение в теорию выпуклых многогранников, Мир, М., 1988, 240 с.; [Brondsted A., An Introduction to Convex Polytopes, Springer-Verlag, 1983.]
12. Martin R. K., “Using separation algorithms to generate mixed integer model reformulations”, Operations Research Letters, 10:3 (1991), 119–128.
13. Белов Ю.А., “О плотности графа матроида”, Модели исследования операций в вычислительных системах, Яросл. гос. ун-т., Ярославль, 1985, 95–100; [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.
15. Papadimitriou C. H., “The Adjacency Relation on the Traveling Salesman Polytope is NP-Complete”, Mathematical Programming, 14:1 (1978), 312–324.
Review
For citations:
Bondarenko V.A., Nikolaev A.V., Shovgenov D.A. 1-Skeletons of the Spanning Tree Problems with Additional Constraints. Modeling and Analysis of Information Systems. 2015;22(4):453-463. (In Russ.) https://doi.org/10.18255/1818-1015-2015-4-453-463
Views:
1123
Email this article 