Characteristics of Complexity: Clique Number of a Polytope Graph and Rectangle Covering Number

In the 1980s V.A. Bondarenko found that the clique number of the graph of a polytope in many cases corresponds to the actual complexity of the optimization problem on the vertices of the polytope. For an explanation of this phenomenon he proposed the theory of direct type algorithms. This theory asserts that the clique number of the graph of a polytope is the lower bound of the complexity of the corresponding problem in the so-called class of direct type algorithms. Moreover, it was argued that this class is wide enough and includes many classical combinatorial algorithms. In this paper we present a few examples, designed to identify the limits of applicability of this theory. In particular, we describe a modification of algorithms that is quite frequently used in practice. This modification takes the algorithms out of the specified class, while the complexity is not changed. Another, much closer to reality combinatorial characteristic of complexity is the rectangle covering number of the facet-vertex incidence matrix, introduced into consideration by M. Yannakakis in 1988. We give an example of a polytope with a polynomial (with respect to the dimension of the polytope) value of this characteristic, while the corresponding optimization problem is NP-hard.

1. Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. Ярославль: ЯрГУ, 1995. [Bondarenko V.A. Poliedralnye grafy i slozhnost v kombinatornoy optimizatsii. Yaroslavl: YarGU, 1995 (in Russian)].

2. Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. M.: ЛКИ, 2008. [Bondarenko V.A., Maksimenko A.N. Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii. Moskva: LKI, 2008 (in Russian)].

3. Бондаренко В.А., Николаев А.В. Комбинаторно-геометрические свойства задачи о разрезе // Доклады Академии наук. Математика. 2013. Т. 452, № 2. С. 127–129. (English transl.: Bondarenko V.A., Nikolaev A.V. Combinatorial and Geometric Properties of the Max-Cut and Min-Cut Problems // Doklady Mathematics. 2013. V. 88, No 2. P. 516–517.)

4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. (Garey M.R. and Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co., 1979.)

5. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. (English transl.: Yemelichev V.A., Kovalev M.M., Kravtsov M.K. Polytopes, Graphs and Optimisation; translated by G.H. Lawden. Cambridge: Cambridge Univ. Press, 1984.)

6. Колесов Е.В., Максименко А.Н. Анализ одного алгоритма для задачи о назначениях // Заметки по информатике и математике. Ярославль: ЯрГУ, 2009. Вып. 1. С. 36–40. [Kolesov E.V., Maksimenko A.N. Analiz odnogo algoritma dlya zadachi o naznacheniyakh // Zametki po informatike i matematike. Yaroslavl: YarGU, 2009. Vyp. 1. S. 36–40 (in Russian)].

7. Максименко А.Н. Комбинаторные свойства многогранника задачи о кратчайшем пути // Журнал вычислительной математики и математической физики. 2004. Т. 44. № 9. С. 1693–1696. (English transl.: Maksimenko A.N. Combinatorial properties of the polyhedron of the shortest path problem // Comput. Math. Math. Phys. 2004. V. 44, No. 9, P. 1611–1614.)

8. Максименко А.Н. k-смежностные грани булева квадратичного многогранника // Фундаментальная и прикладная математика. 2013. Т. 18, № 2. С. 95—103. [Maksimenko A.N. k-smezhnostnye grani buleva kvadratichnogo mnogogrannika // Fundamentalnaya i prikladnaya matematika. 2013. T. 18, № 2. S. 95—103 (in Russian)].

9. Мошков М.Ю. Об условных тестах // Доклады АН СССР. 1982. Т. 265, № 3. С. 550–552. (English transl.: Moshkov M.Ju. On conditional tests // Academy of Sciences Doklady. 1982. V. 265, No 3. P. 550–552.)

10. Bogomolov Yu., Fiorini S., Maksimenko A., Pashkovich K. Small Extended Formulations for Cyclic Polytopes // arXiv:1401.8138

11. Conforti M., Cornu´ejols G., and Zambelli G. Extended formulations in combinatorial optimization // A Quarterly Journal of Operations Research. 2010. V. 8, No 1. P. 1–48.

12. Deza M.M., Laurent M. Geometry of cuts and metrics. Springer, 1997.

13. Fiorini S., Massar S., Pokutta S., Tiwary H.R., de Wolf R. Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds // STOC. 2012. P. 95–106.

14. Fiorini S., Kaibel V., Pashkovich K., Theis D.O. Combinatorial Bounds on Nonnegative Rank and Extended Formulations // Discrete Math. 2013. V. 313, No 1. P. 67–83.

15. Gaiha P., Gupta S.K. Adjacent vertices on a permutohedron // SIAM Journal on Applied Mathematics. 1977. V. 32, No 2. P. 323–327.

16. Kaibel V. Extended Formulations in Combinatorial Optimization // Optima. 2011. 85.

17. Kaibel V., Weltge S. A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially // arXiv:1307.3543, 2013.

18. Maksimenko A.N. A special place of Boolean quadratic polytopes among other combinatorial polytopes // arXiv:1408.0948

19. Rothvoss T. The matching polytope has exponential extension complexity // STOC. 2014. P. 263–272.

20. Yannakakis M. Expressing combinatorial optimization problems by linear programs // J. Comput. System Sci. 1991. V. 43, No 3. P. 441–466.