# 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
@MarioCarneiro I am curious if there have been any developments in the language to cater for this question :-) Did you end up getting any solution at all? There might be something in V10 that makes coding up at least a slow brute force method easier for the problem. –  mrm Feb 16 at 11:57
@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 at 12:16

This is a partial answer that offers two solutions that you might be happy with. First, you are asking for the minimum number of cliques that cover all the edges of $G$ such that each edge is in exactly 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 at least 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$. The following computes $\text{cp}(G)$, and is thus an upper bound. Observe this is just the number, not an explicit collection of cliques.

ChromaticNumber[g_] := Module[{k = 1},
While[ChromaticPolynomial[g, k] == 0, ++k]; k]

CliqueCoverNumber[g_] := ChromaticNumber[GraphComplement[g]];


A small example with a $K_5$ with a triangle pressed against it:

g = Graph[Union[EdgeList[CompleteGraph[5]], {1 <-> 6, 6 <-> 2}],
VertexLabels -> "Name"]
{ChromaticNumber[g], CliqueCoverNumber[g]}


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 cover":

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


We can test this with the same graph as above, 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, SimpleCliqueCover[g]]

-
Just let me know if there is a more direct way of computing the chromatic number in V10, by the way. –  mrm Feb 20 at 12:33
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 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 :-) –  mrm Feb 22 at 9:20
@JacobAkkerboom Actually sorry, I had this straight in my head, but had written it down incorrectly. It should be fixed now. –  mrm Feb 24 at 15:45
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 at 16:21