Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems

V. A. Bondarenko, A. V. Nikolaev, D. A. Shovgenov

P.G. Demidov Yaroslavl State University, 14 Sovetskaya str., Yaroslavl 150003, Russia

Abstract: We study the polyhedral properties of three problems of constructing an optimal biclique in a bipartite graph. In the first problem we consider a balanced biclique with the same number of vertices in both parts and arbitrary edge weights. In the other two problems it is required to find maximum or minimum unbalanced bicliques with a fixed number of vertices and non-negative edges. All three problems are established to be NP-hard. We study the polytopes and the cone decompositions of these problems and their 1-skeletons. We describe the adjacency criterion in the 1-skeleton of the balanced biclique polytope. Clique number of 1-skeleton is estimated from below by a superpolynomial function. For both unbalanced biclique problems we establish the superpolynomial lower bounds on the clique numbers of the graphs of non-negative cone decompositions. These values characterize the time complexity in a broad class of algorithms based on linear comparisons.

Keywords: biclique, 1-skeleton, cone decomposition, clique number, NP-hard problem.

UDC: 519.16+514.172.45

Received: 25.08.2016

DOI: 10.18255/1818-1015-2017-2-141-154

Bibliographic databases:

•