11
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Jun 3, 2013 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$ Jun 4, 2013 at 2:30
  • $\begingroup$ Yes, I hope there will be a nice answer :). $\endgroup$ Jun 4, 2013 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$ Feb 16, 2015 at 12:16

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Feb 21, 2015 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, 2015 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$ Feb 24, 2015 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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