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

Question

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.

Answer 1

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},
   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.