Characteristics of complexity: clique number of a polytope graph and rectangle covering number

A. N. Maksimenko

Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 5, pp. 116-130

Résumé

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.

Détail

Keywords: combinatorial optimization, convex polytopes, complexity of problems and algorithms, 1-skeleton of a polytope, clique number, extended formulations, rectangle covering number.
Mots-clés : facet-vertex incidence matrix