On the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph $$G=(V,E)$$ G = ( V , E ) , the complete width of G is the minimum k such that there exist k independent sets $$\mathtt {N}_i\subseteq V$$ N i ⊆ V , $$1\le i\le k$$ 1 ≤ i ≤ k , such that the graph $$G'$$ G ′ obtained from G by adding some new edges between certain vertices inside the sets $$\mathtt {N}_i$$ N i , $$1\le i\le k$$ 1 ≤ i ≤ k , is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on $$3K_2$$ 3 K 2 -free bipartite graphs and polynomially solvable on $$2K_2$$ 2 K 2 -free bipartite graphs and on $$(2K_2,C_4)$$ ( 2 K 2 , C 4 ) -free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on $$\overline{3K_2}$$ 3 K 2 ¯ -free co-bipartite graphs and polynomially solvable on $$C_4$$ C 4 -free co-bipartite graphs and on $$(2K_2, C_4)$$ ( 2 K 2 , C 4 ) -free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most $$2^k$$ 2 k vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most $$2^k$$ 2 k vertices. Finally we determine all graphs of small complete width $$k\le 3$$ k ≤ 3 .