Geodesic
The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
Trudy Instituta matematiki, Tome 22 (2014) no. 1, pp. 51-69 
O. I. Duginov. The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs. Trudy Instituta matematiki, Tome 22 (2014) no. 1, pp. 51-69. http://geodesic.mathdoc.fr/item/TIMB_2014_22_1_a4/
@article{TIMB_2014_22_1_a4,
     author = {O. I. Duginov},
     title = {The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs},
     journal = {Trudy Instituta matematiki},
     pages = {51--69},
     year = {2014},
     volume = {22},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2014_22_1_a4/}
}
TY  - JOUR
AU  - O. I. Duginov
TI  - The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
JO  - Trudy Instituta matematiki
PY  - 2014
SP  - 51
EP  - 69
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TIMB_2014_22_1_a4/
LA  - ru
ID  - TIMB_2014_22_1_a4
ER  - 
%0 Journal Article
%A O. I. Duginov
%T The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
%J Trudy Instituta matematiki
%D 2014
%P 51-69
%V 22
%N 1
%U http://geodesic.mathdoc.fr/item/TIMB_2014_22_1_a4/
%G ru
%F TIMB_2014_22_1_a4

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

Problems of covering the vertex set (the edge set) of a simple graph with a minimum number of complete bipartite subgraphs are studied. We give a polynomial time algorithm for the first problem restricted to the class of $S_{1,2,3}$-free bipartite graphs, where $S_{1,2,3}$ is the graph with the vertex set $\{a,b,c,d,e,f,g\}$ and the edge set $\{ab,bc,cd,fe,ed,gd\}$. Besides we show that the first problem in the class of bipartite graphs cannot be approximated in polynomial time within a factor $\mathrm{const}\cdot\ln{n},$ where $n$ is the number of vertices of the given bipartite graph, unless $P=NP$. On the other hand, we give polynomial time greedy approximation algorithm within a factor $H_n$. Also we show that the second problem is NP-complete in the class of $(K_{3,4},K_{3,4}-e)$-free bipartite graphs with degrees at most 7.

[1] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, KD “Librokom”, M., 2009

[2] Lozin V. V., “$E$-svobodnye dvudolnye grafy”, Diskretnyi analiz i issledovaniya operatsii. Ser. 1, 7:1, 49–66

[3] Fleischner H., Mujuni E., Paulusma D., Szeider S., “Covering graphs with few complete bipartite subgraphs”, Theoretical Computer Science, 410 (2009), 2045–2053 | DOI

[4] Bein D., Morales L., Bein W., Shields C. O. (jr.), Meng Z., Sudborough I. H., “Clustering and the biclique partition problem”, Proceedings of the 41st Annual Hawaii International Conference on System Science (USA, 2008), 475

[5] Orlin J., “Contentment in graph theory: Covering graphs with cliques”, Indagationes Mathematicae, 39 (1977), 406–424 | DOI

[6] Amilhastre J., Janssen P., Vilarem M.-C., “Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs”, Discrete Applied Mathematics, 86 (1998), 125–144 | DOI

[7] Lepin V. V., “Lineinyi algoritm dlya vychisleniya chisla biklikovogo pokrytiya posledovatelno-parallelnogo grafa”, Trudy Instituta matematiki, 16:2 (2008), 63–75

[8] Lepin V. V., Duginov O. I., “Algoritmy dlya nakhozhdeniya pokrytii biklikami grafa s ogranichennoi putevoi shirinoi”, Trudy Instituta matematiki, 19:2 (2011), 69–81

[9] Korobitsyn D. V., “O slozhnosti opredeleniya chisla dominirovaniya v monogennykh klassakh grafov”, Diskretnaya matematika, 2:3, 90–96

[10] Lozin V., “Bipartite graphs without a skew star”, Discrete Mathematics, 257 (2002), 83–100 | DOI

[11] Chlebik M., Chlebiková J., “Approximation hardness of dominating set problems in bounded degree graphs”, Information and Computation, 206 (2008), 1264–1275 | DOI

[12] Raz R., Safra S., “A sub-constant error-probability low degree test, and a sub-constant error-probability PCP characterization of NP”, Proceedings of the twenty-ninth ACM symposium on theory of computing (1997), 475–484

[13] Vazirani V., Approximation algorithms, Springer, Berlin–Heidelberg, 2003

[14] Dawande M., Keskinocak P., Swaminathan J., “On Bipartite and Multipartite Clique Problems”, J. of Algorithms, 41 (2001), 388–403 | DOI

[15] Hochbaum D. S., “Approximating Clique and Biclique Problems”, J. of Algorithms, 29 (1998), 174–200 | DOI

[16] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya, Nauka, M., 1981

[17] Král D., Kratochvil J., Tuza Z., Woeginger G. J., “Complexity of Coloring Graphs without Forbidden Induced Subgraphs”, Graph-Theoretic Concepts in Computer Science, 2204 (2001), 254–262 | DOI