The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs

O. I. Duginov

Trudy Instituta matematiki, Tome 22 (2014) no. 1, pp. 51-69

Résumé

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.