Geodesic
Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems
Modelirovanie i analiz informacionnyh sistem, Tome 24 (2017) no. 2, pp. 141-154.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : biclique, cone decomposition
Keywords: 1-skeleton, clique number, NP-hard problem. 
@article{MAIS_2017_24_2_a1,
     author = {V. A. Bondarenko and A. V. Nikolaev and D. A. Shovgenov},
     title = {Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {141--154},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2017_24_2_a1/}
}
TY  - JOUR
AU  - V. A. Bondarenko
AU  - A. V. Nikolaev
AU  - D. A. Shovgenov
TI  - Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2017
SP  - 141
EP  - 154
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2017_24_2_a1/
LA  - ru
ID  - MAIS_2017_24_2_a1
ER  - 
%0 Journal Article
%A V. A. Bondarenko
%A A. V. Nikolaev
%A D. A. Shovgenov
%T Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems
%J Modelirovanie i analiz informacionnyh sistem
%D 2017
%P 141-154
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2017_24_2_a1/
%G ru
%F MAIS_2017_24_2_a1
V. A. Bondarenko; A. V. Nikolaev; D. A. Shovgenov. Polyhedral characteristics of balanced and unbalanced bipartite subgraph problems. Modelirovanie i analiz informacionnyh sistem, Tome 24 (2017) no. 2, pp. 141-154. http://geodesic.mathdoc.fr/item/MAIS_2017_24_2_a1/

[1] Bondarenko V. A., “Nonpolynomial lowerbound of the traveling salesman problem complexety in one class of algorithms”, Automation and remote control, 44:9 (1983), 1137–1142 | MR | Zbl

[2] Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii, LKI, Moscow, 2008 (in Russian)

[3] 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 | DOI | DOI | MR | Zbl

[4] 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, 22:4 (2015), 453–463 (in Russian) | MR

[5] Maksimenko A. N., “Combinatorial properties of the polyhedron associated with the shortest path problem”, Comput. Math. Math. Phys., 88:2 (2013), 1611–1614 | MR | Zbl

[6] Apollonio N., Simeone B., “The maximum vertex coverage problem on bipartite graphs”, Discrete Applied Mathematics, 165 (2014), 37–48 | DOI | MR | Zbl

[7] Arbib C., Mosca R., “Polynomial algorithms for special cases of the balanced complete bipartite subgraph problem”, Journal of Combinatorial Mathematics and Combinatorial Computing, 39 (1999), 3–22 | MR

[8] Bondarenko V., Nikolaev A., “On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems”, International Journal of Mathematics and Mathematical Sciences, 2016 (2016), 7863650, 6 pp. | DOI | MR

[9] Cheng Y., Church G. M., “Biclustering of expression data”, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, 2000, 93–103

[10] Diestel R., Graph Theory, Springer-Verlag, Berlin–Heidelberg, 2010, 410 pp.

[11] Feige U., Kogan S., Hardness of approximation of the Balanced Complete Bipartite Subgraph problem, Tech. Rep. MCS04–04, Dept. of Comp. Sci. and Appl. Math., The Weizmann Inst. of Science, 2004

[12] 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, 340 pp. | MR | Zbl

[13] Grötschel M., Lovasz L., Schrijver A., Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin–Heidelberg, 1993, 362 pp. | MR

[14] Johnson D. S., “The NP-completeness column: An ongoing guide”, Journal of Algorithms, 8:3 (1987), 438–448 | DOI | MR | Zbl

[15] Joret G., Vetta A., “Reducing the rank of a matroid”, Discrete Mathematics Theoretical Computer Science, 17:2 (2015), 143–156 | MR | Zbl

[16] Hopcroft J. E., Karp R. M., “An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs”, SIAM Journal on Computing, 2:4 (1973), 225–231 | DOI | MR | Zbl

[17] Mubayi D., Turàn G., “Finding bipartite subgraphs efficiently”, Information Processing Letters, 110:5 (2010), 174–177 | DOI | MR | Zbl

[18] Ravi S. S., Lloyd E. L., “The complexity of near-optimal programmable logic array folding”, SIAM Journal on Computing, 17:4 (1988), 696–710 | DOI | MR | Zbl