# Fewest induced subgraphs of order <= k which cover every edge

I'm facing a graph problem and I'm looking to identify it, maybe as a special case of a more general problem, so that I can then find an approximation algorithm for its solution (I'm assuming it's NP-complete).

I have a graph $G$ with $|V|$ vertices. Every vertex has at least one edge connected to it. I want to find the induced subgraphs of $G$ of order $\leq k$, where every edge in $G$ is found in at least one subgraph and the number of subgraphs is minimized. I can assume as a pre-condition that a solution exists (there exist no cliques with order $>k$).

For example, here is a graph $G$ with 5 vertices. If $k=4$, there's no solution with 1 subgraph since there are more than 4 vertices in $G$. A solution for $k=4$ with 2 subgraphs is shown beside it: The order of each subgraph can be less than $k$, so $\{\{1, 2, 3\},\{1, 2, 4, 5\}\}$ is another valid solution.

This is not a solution because the black edge between $2$ and $3$ is not covered by either subgraph: All I'm looking for is a name for the problem, if it exists, so that I can research it and hopefully find an approximation algorithm. Having subgraph order $\leq k$ is a hard requirement but the "minimum number of subgraphs" part can be approximated as long as it's close to minium.

## 1 Answer

Your problem is known as $k$-clique cover. Goldschmidt, Hochbaum, Hurkens and Yu describe several approximation algorithms in their paper Approximation algorithms for the $k$-clique covering problem. The paper is from 1995, so there are likely newer works on this topic, which you can find by scanning the papers citing this paper.