vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"vestifm-35Research ArticleМАТЕМАТИКАMATHEMATICSПОКРЫТИЕ РАСЩЕПЛЯЕМОГО ГРАФА НАИМЕНЬШИМ ЧИСЛОМ ПОЛНЫХ ДВУДОЛЬНЫХ ПОДГРАФОВCOVERING A SPLIT GRAPH WITH THE MINIMUM NUMBER OF COMPLETE BIPARTITE SUBGRAPHSДугиновО. И.DuginovO. I.Институт математики Национальной академии наук Беларуси, МинскInstitute of Mathematics of the National Academy of Sciences of Belarus, Minsk201416052016015460Copyright © Дугинов О.И., 20162016Дугинов О.И.Duginov O.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/35

Рассматривается вычислительная сложность двух задач, связанных с бикликами (связными полными двудольными подграфами) графа в классе расщепляемых графов. Для заданного графа и натурального числа k, в задаче о бикликовом покрытии требуется ответить на вопрос: можно ли множество ребер графа покрыть не более k бикликами; в задаче о бикликовом покрытии вершин требуется ответить на вопрос: можно ли множество вершин графа покрыть не более k бикликами. Известно, что обе задачи являются NP-полными для двудольных графов. В работе показано, что обе задачи остаются NP-полными в классе расщепляемых графов.

In this article we consider the computational complexity of two problems related to bicliques (complete bipartite subgraphs) of a graph in the class of split graphs. Given a graph and an integer k, the biclique cover problem asks whether the edge set of the graph can be covered with at most k bicliques; the biclique vertex-cover problem asks whether the vertex set of the graph can be covered with at most k bicliques. These problems are known to be NP-complete even in the class of bipartite graphs. In this article, we show that the both problems remain NP-complete in the class of split graphs.

ReferencesЕмеличевВ. А., Мельников О. И., СарвановВ. И., Тышкевич Р. А. Лекции по теории графов. М., 2011.ЕмеличевВ. А., Мельников О. И., СарвановВ. И., Тышкевич Р. А. Лекции по теории графов. М., 2011.Brandstadt A., Le V. B., Spinrad J. Graph classes: a survey. SIAM Monographs on Discrete Math. and Applications, 1999. P. 306.Brandstadt A., Le V. B., Spinrad J. Graph classes: a survey. SIAM Monographs on Discrete Math. and Applications, 1999. P. 306.FleischnerH., Mujuni E., Paulusma D., Szeider S. // Theoretical Computer Science. 2009. Vol. 410. P. 2045-2053.FleischnerH., Mujuni E., Paulusma D., Szeider S. // Theoretical Computer Science. 2009. Vol. 410. P. 2045-2053.Amiliastre J., Vilarem M., Janssen P. // Discrete Applied Mathematics. 1998. Vol. 86. P. 125-144.Amiliastre J., Vilarem M., Janssen P. // Discrete Applied Mathematics. 1998. Vol. 86. P. 125-144.CornazD., Fonplut J. // Discrete Mathematics. 2006. Vol. 306. P. 495-507.CornazD., Fonplut J. // Discrete Mathematics. 2006. Vol. 306. P. 495-507.Chakrabarti D., Papadimitriou S., Modha D. S., Faloutsos C. // Proceedings of the 10th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD’04). [S. l.], 2004. P. 79-88.Chakrabarti D., Papadimitriou S., Modha D. S., Faloutsos C. // Proceedings of the 10th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD’04). [S. l.], 2004. P. 79-88.Heydari M. H., Morales L., Shields C. O, Sudborough I. H. // Proceedings of the 40th Annual Hawaii International Conference on System Sciences (HICSS’07). [S. l.], 2007. P. 270b.Heydari M. H., Morales L., Shields C. O, Sudborough I. H. // Proceedings of the 40th Annual Hawaii International Conference on System Sciences (HICSS’07). [S. l.], 2007. P. 270b.Fоldes S., Hammer P. // Congressus Numerantium. 1977. Vol. 19. P. 311-315.Fоldes S., Hammer P. // Congressus Numerantium. 1977. Vol. 19. P. 311-315.Тышкевич Р. И., Черняк А. А. // Изв. АН БССР. Сер. физ.-мат. наук. 1979. Т. 5. С. 14-26.Тышкевич Р. И., Черняк А. А. // Изв. АН БССР. Сер. физ.-мат. наук. 1979. Т. 5. С. 14-26.Orlin, J. // Indagationes Mathematicae. 1977. Vol. 80. P. 406-424.Orlin, J. // Indagationes Mathematicae. 1977. Vol. 80. P. 406-424.MullerH. // Discrete Mathematics. 1996. Vol. 149. P. 159-187.MullerH. // Discrete Mathematics. 1996. Vol. 149. P. 159-187.Lubiw A. // SIAM J. on Discrete Mathematics. 1990. Vol. 3. P. 98-115.Lubiw A. // SIAM J. on Discrete Mathematics. 1990. Vol. 3. P. 98-115.Soto J., Telha C. // Proceedings of the 15th International Conference on Integer programming and combinatoral optimization.). [S. l.], 2011. P. 389-403.Soto J., Telha C. // Proceedings of the 15th International Conference on Integer programming and combinatoral optimization.). [S. l.], 2011. P. 389-403.Лепин В. В. // Тр. Ин-та математики. 2010. Т. 18. С. 60-78.Лепин В. В. // Тр. Ин-та математики. 2010. Т. 18. С. 60-78.Лепин В. В., Дугинов О. И. // Тр. Ин-та математики. Т. 19. С. 69-81.Лепин В. В., Дугинов О. И. // Тр. Ин-та математики. Т. 19. С. 69-81.Fishburn P. C., Hammer P. L. // Discrete Mathematics. 1996. Vol. 160. P. 127-148.Fishburn P. C., Hammer P. L. // Discrete Mathematics. 1996. Vol. 160. P. 127-148.Weihe K. // Proceedings of the 1st Conference on Algorithms and Experiments (ALEX-1998). [S. l.], 1998. P. 1-8.Weihe K. // Proceedings of the 1st Conference on Algorithms and Experiments (ALEX-1998). [S. l.], 1998. P. 1-8.Kratzke T., ReznickB., WestD. // Transactions of the American mathematical society. 1988. Vol. 308. P. 637-653.Kratzke T., ReznickB., WestD. // Transactions of the American mathematical society. 1988. Vol. 308. P. 637-653.Дугинов О. И., Лепин В. В. // Веб-программирование и Интернет-технологии WebConf2012: материалы 2-й Междунар. науч.-практ. конф., БГУ Минск, 2012.Дугинов О. И., Лепин В. В. // Веб-программирование и Интернет-технологии WebConf2012: материалы 2-й Междунар. науч.-практ. конф., БГУ Минск, 2012.

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