On the complete width and edge clique cover problems

NEW

Problem: Reconstructed decision problem: given a finite simple graph $G$ that is $2K_2$-free and an integer $k$, decide whether the complete width $\operatorname{cw}(G)\le k$. Here $\operatorname{cw}(G)$ is the minimum number of independent sets of $G$ whose union, as pairs, covers every non-edge of $G$. Equivalently, for $\overline G$, this is EDGE CLIQUE COVER: $\operatorname{cw}(G)=\theta_e(\overline G)$. Since $\overline{2K_2}=C_4$, the equivalent problem is EDGE CLIQUE COVER on $C_4$-free graphs.

Result: The problem is NP-complete.

Proof sketch. Reduce from VERTEX COVER on graphs $H$ of girth at least $5$, which is NP-complete.

Given such an $H$, construct a graph $X$. For each edge $e\in E(H)$, create a vertex $x_e$, and add one vertex $c$ adjacent to every $x_e$. If two edges $e,f$ of $H$ share an endpoint, add edge $x_ex_f$. For every such incident pair $\{e,f\}$, add a vertex $y_{ef}$ adjacent exactly to $x_e,x_f$. Let

The graph $X$ is $C_4$-free: any induced $C_4$ using some $y_{ef}$ would have adjacent neighbors $x_e,x_f$, giving a chord; any induced $C_4$ using $c$ has a chord through $c$; and an induced $C_4$ inside the $x_e$-vertices would correspond to a $4$-cycle in $H$, impossible since $H$ has girth at least $5$.

Every $y_{ef}$ forces one clique $\{y_{ef},x_e,x_f\}$, so any edge clique cover has at least $P$ such cliques, and these cliques cover all edges among the $x_e$'s. The only remaining edges are $cx_e$. A clique containing $c$ corresponds to a clique in the line graph $L(H)$; since $H$ is triangle-free, every such clique consists of edges incident to a single vertex of $H$. Thus covering all edges $cx_e$ is exactly choosing vertices of $H$ incident to every edge, i.e. a vertex cover. Therefore

where $\tau(H)$ is the vertex-cover number of $H$.

Hence $H$ has a vertex cover of size at most $k$ iff $X$ has an edge clique cover of size at most $P+k$. This proves EDGE CLIQUE COVER is NP-hard on $C_4$-free graphs. It is plainly in NP. Taking complements gives NP-completeness of COMPLETE WIDTH on $2K_2$-free graphs.

Citation: The reduction uses the standard NP-completeness of VERTEX COVER/INDEPENDENT SET on graphs of girth at least $5$, e.g. O. J. Murphy, “Computing independent sets in graphs with large girth,” Discrete Applied Mathematics 35 (1992), 167–170.