This is a graph problem known as the "Clique Edge Cover" or "Intersection Number" problem, and the goal is to find, from a given graph like $E=\{\{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\}\}$ and $V=\bigcup E$, a representation $K=\{\{a,b,c\},\{b,c,d\}\}$ of the cliques in the graph that has the smallest $|K|$, where the relation from $K$ to $E$ is that $E=\{x:|x|=2\wedge\exists y\in K\,x\subseteq y\}$, i.e. $E$ is the set of all pairs in the elements of $K$, so that the elements of $K$ are interpreted as cliques in the graph. (This is the "clique edge cover" statement of the problem, which is the one I am directly interested in, but it may help to see the "intersection number" version of the problem, described in the links above.) This problem is known NP-hard, but that's never stopped Mathematica in the past, and I am not looking for a super-optimized implementation, just one that works reasonably well on small instances.
Is there a Mathematica or Combinatorica function that directly implements a solution to this problem, and barring that, does anyone want to take a crack at implementing an algorithm to do this? This paper is an analysis of the problem that contains a few algorithms and may be helpful to this end.
I've asked this question before at math.SE, in order to find out what the problem was called.