# Is there a function to generate a minimal clique cover?

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.

-
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
@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. – 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 Posa, 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},
Reap[
While[!EmptyGraphQ[h],
mc =
Sow[EdgeList[
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.

-
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 – Jacob Akkerboom Feb 21 '15 at 19:12
@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 :-) – Juho Feb 22 '15 at 9:20
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. – Jacob Akkerboom Feb 24 '15 at 16:21