COVERING A SPLIT GRAPH WITH THE MINIMUM NUMBER OF COMPLETE BIPARTITE SUBGRAPHS
Abstract
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.
About the Author
O. I. Duginov
Institute of Mathematics of the National Academy of Sciences of Belarus, Minsk
Belarus
Belarus
References
1. ЕмеличевВ. А., Мельников О. И., СарвановВ. И., Тышкевич Р. А. Лекции по теории графов. М., 2011.
2. Brandstadt A., Le V. B., Spinrad J. Graph classes: a survey. SIAM Monographs on Discrete Math. and Applications, 1999. P. 306.
3. FleischnerH., Mujuni E., Paulusma D., Szeider S. // Theoretical Computer Science. 2009. Vol. 410. P. 2045-2053.
4. Amiliastre J., Vilarem M., Janssen P. // Discrete Applied Mathematics. 1998. Vol. 86. P. 125-144.
5. CornazD., Fonplut J. // Discrete Mathematics. 2006. Vol. 306. P. 495-507.
6. 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.
7. 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.
8. Fоldes S., Hammer P. // Congressus Numerantium. 1977. Vol. 19. P. 311-315.
9. Тышкевич Р. И., Черняк А. А. // Изв. АН БССР. Сер. физ.-мат. наук. 1979. Т. 5. С. 14-26.
10. Orlin, J. // Indagationes Mathematicae. 1977. Vol. 80. P. 406-424.
11. MullerH. // Discrete Mathematics. 1996. Vol. 149. P. 159-187.
12. Lubiw A. // SIAM J. on Discrete Mathematics. 1990. Vol. 3. P. 98-115.
13. Soto J., Telha C. // Proceedings of the 15th International Conference on Integer programming and combinatoral optimization.). [S. l.], 2011. P. 389-403.
14. Лепин В. В. // Тр. Ин-та математики. 2010. Т. 18. С. 60-78.
15. Лепин В. В., Дугинов О. И. // Тр. Ин-та математики. Т. 19. С. 69-81.
16. Fishburn P. C., Hammer P. L. // Discrete Mathematics. 1996. Vol. 160. P. 127-148.
17. Weihe K. // Proceedings of the 1st Conference on Algorithms and Experiments (ALEX-1998). [S. l.], 1998. P. 1-8.
18. Kratzke T., ReznickB., WestD. // Transactions of the American mathematical society. 1988. Vol. 308. P. 637-653.
19. Дугинов О. И., Лепин В. В. // Веб-программирование и Интернет-технологии WebConf2012: материалы 2-й Междунар. науч.-практ. конф., БГУ Минск, 2012.
Review
Views: 670
Email this article 