I'd like to take an undirected graph and express it (meaning all of its edges) using only cliques (ideally minimizing their sum cardinality).
It's clear that actually finding the minimum solution is at least as hard as the set-cover problem, but set-cover has good approximation algorithms. Does anyone know a good approximation algorithm for this?
Particularly, if I start with each edge as its own clique and then arbitrarily choose two cliques from my list (whose union also forms a clique) and merge them and do this over and over until I can't merge any more, what's the worst case (as a ratio / the minimal solution)? Is there some heuristic I should use to determine what to merge next?