maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2017-2-141-154mais-505Research ArticleОригинальные статьиArticlesПолиэдральные характеристики задач о сбалансированном и несбалансированном двудольных подграфахPolyhedral Characteristics of Balanced and Unbalanced Bipartite Subgraph Problemshttps://orcid.org/0000-0002-5976-3446БондаренкоВладимир АлександровичBondarenkoVladimir

д-р физ.-мат. наук, профессор

ул. Советская, 14, г. Ярославль, 150003, Россия

doctor of science, professor

14 Sovetskaya str., Yaroslavl 150003, Russia

bond@bond.edu.yar.ruhttps://orcid.org/0000-0003-4705-2409НиколаевАндрей ВалерьевичNikolaevAndrei

канд. физ.-мат. наук

ул. Советская, 14, г. Ярославль, 150003, Россия

PhD

14 Sovetskaya str., Yaroslavl 150003, Russia

andrei.v.nikolaev@gmail.comhttps://orcid.org/0000-0003-2022-4514ШовгеновДжамболет АзаматовичShovgenovDzhambolet

аспирант

ул. Советская, 14, г. Ярославль, 150003, Россия

graduate student

14 Sovetskaya str., Yaroslavl 150003, Russia

djsh92@mail.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation201729042017242141154Copyright © Бондаренко В.А., Николаев А.В., Шовгенов Д.А., 20172017Бондаренко В.А., Николаев А.В., Шовгенов Д.А.Bondarenko V., Nikolaev A., Shovgenov D.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/505

Исследуются полиэдральные характеристики трех задач о построении оптимальных полных двудольных подграфов двудольных графов. В первой задаче рассматриваются сбалансированные подграфы с одинаковым числом вершин в каждой доле и произвольными весами ребер. В двух других задачах речь идет о несбалансированных подграфах максимального и минимального веса с неотрицательными ребрами. Устанавливается, что все три задачи являются NP-трудными. В работе изучаются многогранники и конусные разбиения рассматриваемых задач, а также их графы. Для задачи о сбалансированном подграфе приводится условие смежности вершин в полиэдральном графе и графе соответствующего конусного разбиения. Плотность полиэдрального графа оценивается снизу сверхполиномиальной функцией. Для задач о несбалансированных подграфах строятся сверхполиномиальные нижние оценки плотности графов неотрицательных конусных разбиений. Полученные результаты характеризуют временную трудоемкость задач в широком классе алгоритмов, использующих линейные сравнения.

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.

полный двудольный графполиэдральный графконусное разбиениеплотность графаNP-трудная задачаbiclique1-skeletoncone decompositionclique numberNP-hard problemReferencesБондаренко В.А., “Неполиномиальная нижняя оценка сложности задачи коммивояжера в одном классе алгоритмов”, Автоматика и телемеханика, 9 (1983), 45– 50; [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.]Бондаренко В.А., “Неполиномиальная нижняя оценка сложности задачи коммивояжера в одном классе алгоритмов”, Автоматика и телемеханика, 9 (1983), 45– 50; [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.]Бондаренко В.А., Максименко А.Н., Геометрические конструкции и сложность в комбинаторной оптимизации, ЛКИ, М., 2008, 184 с.; [Bondarenko V.A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii, LKI, Moscow, 2008, (in Russian).]Бондаренко В.А., Максименко А.Н., Геометрические конструкции и сложность в комбинаторной оптимизации, ЛКИ, М., 2008, 184 с.; [Bondarenko V.A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii, LKI, Moscow, 2008, (in Russian).]Бондаренко В.А., Николаев А.В., “Комбинаторно-геометрические свойства задачи о разрезе”, Доклады Академии наук, 452:2 (2013), 127–129; [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.]Бондаренко В.А., Николаев А.В., “Комбинаторно-геометрические свойства задачи о разрезе”, Доклады Академии наук, 452:2 (2013), 127–129; [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.]Бондаренко В.А., Николаев А.В., Шовгенов Д.А., “Полиэдральные графы задач об остовных деревьях при дополнительных ограничениях”, Моделирование и анализ информационных систем, 22:4 (2015), 453–463; [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).]Бондаренко В.А., Николаев А.В., Шовгенов Д.А., “Полиэдральные графы задач об остовных деревьях при дополнительных ограничениях”, Моделирование и анализ информационных систем, 22:4 (2015), 453–463; [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).]Максименко А.Н., “Комбинаторные свойства многогранника задачи о кратчайшем пути”, Ж. вычисл. матем. и матем. физ., 44:9 (2004), 1693–1696; [Maksimenko A.N., “Combinatorial properties of the polyhedron associated with the shortest path problem”, Comput. Math. Math. Phys., 88:2 (2013), 1611–1614.]Максименко А.Н., “Комбинаторные свойства многогранника задачи о кратчайшем пути”, Ж. вычисл. матем. и матем. физ., 44:9 (2004), 1693–1696; [Maksimenko A.N., “Combinatorial properties of the polyhedron associated with the shortest path problem”, Comput. Math. Math. Phys., 88:2 (2013), 1611–1614.]Apollonio N., Simeone B., “The maximum vertex coverage problem on bipartite graphs”, Discrete Applied Mathematics, 165 (2014), 37–48.Apollonio N., Simeone B., “The maximum vertex coverage problem on bipartite graphs”, Discrete Applied Mathematics, 165 (2014), 37–48.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.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.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), 6 pages, Article ID 7863650.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), 6 pages, Article ID 7863650.Cheng Y., Church G. M., “Biclustering of expression data”, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, 2000, 93–103.Cheng Y., Church G. M., “Biclustering of expression data”, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, 2000, 93–103.Diestel R., Graph Theory, Springer-Verlag Berlin Heidelberg, 2010, 410 pp.Diestel R., Graph Theory, Springer-Verlag Berlin Heidelberg, 2010, 410 pp.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.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.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.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.GroЁtschel M., Lovasz L., Schrijver A., Geometric Algorithms and Combinatorial Optimization, Springer–Verlag Berlin Heidelberg, 1993, 362 pp.GroЁtschel M., Lovasz L., Schrijver A., Geometric Algorithms and Combinatorial Optimization, Springer–Verlag Berlin Heidelberg, 1993, 362 pp.Johnson D. S., “The NP-completeness column: An ongoing guide”, Journal of Algorithms, 8:3 (1987), 438–448.Johnson D. S., “The NP-completeness column: An ongoing guide”, Journal of Algorithms, 8:3 (1987), 438–448.Joret G., Vetta A., “Reducing the rank of a matroid”, Discrete Mathematics & Theoretical Computer Science, 17:2 (2015), 143–156.Joret G., Vetta A., “Reducing the rank of a matroid”, Discrete Mathematics & Theoretical Computer Science, 17:2 (2015), 143–156.Hopcroft J. E., Karp R. M., “An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs”, SIAM Journal on Computing, 2:4 (1973), 225–231.Hopcroft J. E., Karp R. M., “An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs”, SIAM Journal on Computing, 2:4 (1973), 225–231.Mubayi D., Tura`n G., “Finding bipartite subgraphs efficiently”, Information Processing Letters, 110:5 (2010), 174–177.Mubayi D., Tura`n G., “Finding bipartite subgraphs efficiently”, Information Processing Letters, 110:5 (2010), 174–177.Ravi S. S., Lloyd E. L., “The complexity of near-optimal programmable logic array folding”, SIAM Journal on Computing, 17:4 (1988), 696–710.Ravi S. S., Lloyd E. L., “The complexity of near-optimal programmable logic array folding”, SIAM Journal on Computing, 17:4 (1988), 696–710.

The authors declare that there are no conflicts of interest present.