Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@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

1 Answer 1

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]]
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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