Graph clique problem

Question

I'm not sure to what degree this is a graph problem, and algorithms question, or what, but I'll give the setup:

I have a simple undirected graph given in the form (for example) $E=\{\{v_1,v_2\},\{v_0,v_1\},\{v_0,v_2\},\{v_0,v_3\},\dots\}$ where $V=\bigcup E$ and $E$ is a set of pairs, and I wish to find a representation $K=\{\{v_0,v_1,v_2\},\{v_0,v_3\},\dots\}$ such that $E=\{x:|x|=2\wedge\exists y\in K\,x\subseteq y\}$ and $|K|$ is minimal. What can be said about this problem: How hard is it? Can it be stated in terms of more common graph problems? If possible, give an algorithm for finding such a $K$ ($K$ is not unique).

It is easily observed that $K$ represents a set of cliques in the graph, so I want to relate it to the maximal clique problem, but my goal is not necessarily to find a maximal clique, just a minimal covering set of cliques.

Edit: An alternative minimality condition is to minimize $|K|+\alpha\sum_{x\in K}|x|$, which more accurately reflects my goal of using this format as a compression system for storing such undirected graphs. In my application, $\alpha=2/7$.

Answer 1

This is known as (Edge) Clique Cover. It is NP-hard and hard to approximate. Here's a paper (of which I am a coauthor) that contains some experiments. The variant where the sum of clique sizes is maximized is also NP-hard. In my experience, choosing either objective does not make a big difference, so unless you're looking for optimal solutions, the heuristics from either paper might be good for your objective, which is a mixture of these two.