Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
I do not think this function exists. The Combinatoria tutorial doc page seems quite comprehensive, but the function is not in there I think. –  Jacob Akkerboom Jun 3 '13 at 20:10
@Jacob I suspected as much, since I checked the docs myself and didn't see anything obviously related. (That's why I opened this question.) Still, it never hurts to get a second opinion, and maybe someone will feel ambitious enough to implement it themselves. –  Mario Carneiro Jun 4 '13 at 2:30
Yes, I hope there will be a nice answer :). –  Jacob Akkerboom Jun 4 '13 at 8:31
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.