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.

  • $\begingroup$ I do not think this function exists. The Combinatoria tutorial doc page seems quite comprehensive, but the function is not in there I think. $\endgroup$ – Jacob Akkerboom Jun 3 '13 at 20:10
  • 1
    $\begingroup$ @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. $\endgroup$ – Mario Carneiro Jun 4 '13 at 2:30
  • $\begingroup$ Yes, I hope there will be a nice answer :). $\endgroup$ – Jacob Akkerboom Jun 4 '13 at 8:31
  • $\begingroup$ @mrm No, I just made the problem easier by adding edges to $E$ to make it almost a complete graph. A solution to this problem would still be helpful to me, though. $\endgroup$ – Mario Carneiro Feb 16 '15 at 12:16

You are asking for the minimum number of cliques that cover all the edges of $G$ such that each edge is in at least one clique. This is known as the clique covering number, denoted by $\text{cc}(G)$. The minimum number of cliques that cover all the edges of $G$ such that each edge is in exactly one clique is the clique partitioning number, denoted by $\text{cp}(G)$. In general, we have $\text{cc}(G) \leq \text{cp}(G) \leq m$.

From the work of Hall and later Erdős, Goodman, and Pósa, we have that $\text{cc}(G) \leq \text{cp}(G) \leq \lfloor n^2 / 4 \rfloor$. Moreover, a covering with at most $\lfloor n^2 / 4 \rfloor$ triangles and edges exists. The following computes such a "simple clique partition":

SimpleCliquePartition[g_] := 
  Module[{tr = EdgeList[Subgraph[g, #]] & /@ FindCycle[g, {3}, All]},
  Union[tr, Partition[Complement[EdgeList[g], Flatten[tr]], 1]]]

We can test this with say a triangle pressed against a $K_5$ with some bridges added:

g = Graph[Union[EdgeList[CompleteGraph[5]], 
    {1 <-> 6, 6 <-> 2, 6 <-> 7, 6 <-> 8, 6 <-> 9, 6 <-> 10}], VertexLabels -> "Name"];
HighlightGraph[g, SimpleCliquePartition[g]]

We can try to do a little bit better with the same idea: let us greedily find a maximum clique in $G$, remove its edges, and repeat the procedure. Compared to the "triangle and edges" method above, this should work better for denser graphs (i.e. graphs with a clique number greater than 3):

GreedyCliquePartition[g_] := Module[{mc = {}, h = g},
      mc = 
         GraphComplement[Graph[Flatten[FindClique[h]], {}]]]];
      h = EdgeDelete[h, mc];
      ]][[2, 1]]

With the same example, this is indeed better:

g = Graph[
   Union[EdgeList[CompleteGraph[5]], {1 <-> 6, 6 <-> 2, 6 <-> 7, 
     6 <-> 8, 6 <-> 9, 6 <-> 10}], VertexLabels -> "Name"];
HighlightGraph[g, GreedyCliquePartition[g]]
{Length[SimpleCliquePartition[g]], Length[GreedyCliquePartition[g]]} 
% Output: {15, 7}

Let me stress that both of these methods compute a clique partition, not a clique covering.

  • $\begingroup$ Isn't the clique covering number the number of cliques needed to cover the vertices (nodes) rather than edges? Source:mathworld.wolfram.com/CliqueCoveringNumber.html $\endgroup$ – Jacob Akkerboom Feb 21 '15 at 19:12
  • $\begingroup$ @JacobAkkerboom Usually, if a paper or some source only talks about covering the vertices, it talks about a cover. This is especially true for older sources, as covering the nodes was studied primarily. Later on edge covering was studied as well, and a distinction had to be made. However, this is all just a matter of convention :-) $\endgroup$ – Juho Feb 22 '15 at 9:20
  • $\begingroup$ Ah yes, that looks good :). I mixed stuff up myself for a moment myself when reading your edit. I hope I can look at this in more detail soon. $\endgroup$ – Jacob Akkerboom Feb 24 '15 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.