Abstract
We consider the 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 or equal a given value. In the second problem, an additional constraint is the assumption that the degree of all vertices of the spanning tree does not exceed a given value. The decision versions of both problems are NP-complete. We consider the 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 in combinatorial and geometric properties between the considered problems and the classical minimum spanning tree problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Belov, Y.A., On clique number of matroid skeleton, in Modeli issledovaniya operacii v vychislitel’nykh sistemakh (Models of Operations Research in Computer Systems), Yaroslavl, 1985, pp. 95–100
Bondarenko, V.A., Complexity bounds for combinatorial optimization problems in one class of algorithms, Russ. Acad. Sci. Dokl. Math., 1993, vol. 328, no 1, pp. 22–24.
Bondarenko, V.A. and Maksimenko, A.N., Geometricheskie konstruktsii i slozhnost’ v kombinatornoi optimizatsii (Geometric Constructs and Complexity in Combinatorial Optimization), Moscow: LKI, 2008.
Bondarenko, V.A. and Nikolaev, A.V., Combinatorial and geometric properties of the max-cut and min-cut problems, Dokl. Math., 2013, vol. 88, no. 2, pp. 516–517.
Brondsted, A., An Introduction to Convex Polytopes, Springer-Verlag, 1983.
Fernandes, L.M. and Gouveia, L., Minimal spanning trees with a constraint on the number of leaves, Eur. J. Oper. Res., 1998, vol. 104, no. 1, pp. 250–261.
Fujie, T., The maximum-leaf spanning tree problem: Formulations and facets, Networks, 2004, vol. 43, no. 4, pp. 212–223.
Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, New York: W. H. Freeman & Co, 1979.
Goemans, M.X., Minimum bounded-degree spanning trees, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 273–282
Martin, R.K., Using separation algorithms to generate mixed integer model reformulations, Oper. Res. Lett., 1991, vol. 10, no. 3, pp. 119–128.
Papadimitriou, C.H., The adjacency relation on the traveling salesman polytope is NP-complete, Math. Progr., 1978, vol. 14, no. 1, pp. 312–324.
Papadimitriou, C.H. and Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity, Upper Saddle River, NJ: Prentice-Hall, Inc., 1982.
Rahman, M.S. and Kaykobad, M., Complexities of some interesting problems on spanning trees Inf. Process. Lett., 2005, vol. 94, no. 2, pp. 93–97.
Salamon, G. and Wiener, G., On finding spanning trees with few leaves, Inf. Process. Lett., 2008, vol. 105, no. 5, pp. 164–169.
Singh, M. and 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, pp. 661–670
Author information
Authors and Affiliations
Corresponding author
Additional information
Published in Russian in Modelirovanie i Analiz Informatsionnykh Sistem, 2015, Vol. 22, No. 4, pp. 453–462.
The article was translated by the authors.
About this article
Cite this article
Bondarenko, V.A., Nikolaev, A.V. & Shovgenov, D.A. 1-Skeletons of the Spanning Tree Problems with Additional Constraints. Aut. Control Comp. Sci. 51, 682–688 (2017). https://doi.org/10.3103/S0146411617070033
Received:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S0146411617070033