A connected graph has a \((k,\ell )\) -cover if each of its edges is contained in at least \(\ell \) cliques of order k. Motivated by recent advances in extremal combinatorics and the literature on edge modification problems, we study the algorithmic version of the (3, 1)-cover problem. Given a connected graph G, the (k, 1)-cover problem is to find the minimum number of non-edges of G, whose addition to G yields a graph with a (k, 1)-cover. We show that the (3, 1)-cover problem is \(\mathbb{N}\mathbb{P}\) -complete for general graphs. Moreover, we show that it admits no polynomial-time constant-factor approximation algorithm unless \(\mathbb {P}=\mathbb{N}\mathbb{P}\) . However, we show that the (3, 1)-cover problem can be solved in polynomial time when the input graph is chordal.