2
$\begingroup$

Does Mathematica have a method to partition the vertices of a graph into maximal independent subsets, such that each subset generates a complete subgraph?

Edit: The partition should be maximal in the sense that the inclusion of a new vertex into any subset should result in non-empty intersections between the subsets, or in the subsets no longer generating complete subgraphs.

$\endgroup$
  • $\begingroup$ igraph has maximal.clqiues (is it what you need?), so you can use IGraphR. Is this an acceptable solution? (I think I recommended this package to you before.) $\endgroup$ – Szabolcs Dec 5 '14 at 18:00
  • $\begingroup$ @Szabolcs Not exactly, because maximal cliques are not a partition of the vertices (some maximal cliques intersect each other). I want to partition the vertices into cliques. $\endgroup$ – becko Dec 5 '14 at 18:44
  • $\begingroup$ What is the result you'd expect here? Graph[{1 <-> 2, 1 <-> 3, 1 <-> 4, 1 <-> 5, 2 <-> 3, 2 <-> 4, 2 <-> 5, 3 <-> 4, 3 <-> 5, 4 <-> 5, 4 <-> 6, 4 <-> 7, 5 <-> 6, 5 <-> 7, 6 <-> 7}, VertexLabels -> "Name"]. {{1,2,3},{4,5,6,7}} and {{1,2,3,4,5},{6,7}} are both good solutions? $\endgroup$ – Szabolcs Dec 5 '14 at 19:24
  • $\begingroup$ I don't expect a specific result. I know there are several ways to do the partition I want. What I want is something similar to what FindGraphCommunitites does, but only choosing communities that are cliques. I hope it's clearer now. $\endgroup$ – becko Dec 5 '14 at 19:26
  • $\begingroup$ I was just trying to make sure I understood. It sounds like my example above is correct, right? $\endgroup$ – Szabolcs Dec 5 '14 at 19:29
2
$\begingroup$

You can just create a graph on the maximal cliques, where cliques are joined if they share any elements. Then you find maximal independent sets in the derived graph-of-cliques. (This is easily adaptable if you do not require cliques to be maximal, just throw in a bunch more vertices into cv to account for sub-cliques.)

n = 15; a = RandomReal[{0.7, 0.9}];
g = RandomGraph[{20, Ceiling[a n (n - 1)/2]}, VertexLabels -> "Name"]
cv = Join[FindClique[g, n, All]];
ce = {};
For[i = 1, i <= Length[cv], i++,
 For[j = 1, j < i, j++,
  If[Intersection[cv[[i]], cv[[j]]] != {}, 
   ce = Append[ce, cv[[j]] <-> cv[[i]]]]
 ];
];
cg = Graph[cv, ce, VertexLabels -> "Name"]
FindIndependentVertexSet[cg]

This is not especially efficient, I'm not sure if you are looking to do some massive computation, in which case a more clever or efficient implementation is necessary. But this is quite easy and requires only the two basic commands FindClique and FindIndependentVertexSet (which are really the same anyway). Note that these commands always return maximal things (so FindClique will not return {1,2,3} if it also returns {1,2,3,4} in its list of cliques).

In this, I've just used n and a to give us a fairly dense graph.

The FindClique[g,n,All] means it finds All cliques in g up to size n (i.e. all sizes). Now, the last line may actually not be what you want. I guess what you really want is not maximal in terms of vertices of cv, but in terms of the total number of vertices covered by that independent-set-of-cliques in the original g, in which case, you can use a similar hack to get:

is = FindIndependentVertexSet[cg, Length[cv], All];
ism = 0; L[s_] := Length[Union[s]]; ismax = {};
For[i = 1, i <= Length[is], i++,
 Which[
  L[is[[i]]] > ism, ismax = {is[[i]]}; ism = L[is[[i]]],
  L[is[[i]]] == ism, ismax = Append[ismax, is[[i]]]
 ];
];

The entire set of maximum size maximal clique sets is ismax and you can see them all with GraphHighlight if you want. That might look something like:

BuildCliques[iss_] := Join[
 Union @@ iss,
 Union @@ 
 Table[Map[#[[1]] <-> #[[2]] &, Subsets[iss[[i]], {2}]], {i, 1, Length[iss]}]
];
Manipulate[
 Graph[g, GraphHighlight -> BuildCliques[is[[i]]]],
 {i, 1, Length[is], 1}]

I haven't really taken any time to make this code clever or optimized, but I think it does what you want, although probably not good for large graphs.

$\endgroup$
2
$\begingroup$

This is known as the clique cover problem and it is equivalent to colouring the complement graph.

Thus we can use the colouring functionality from IGraph/M.

Here's an example:

This is just a style that makes it easier to see what is going on, and cross-reference the visualization with the raw result.

style = {GraphStyle -> "BasicBlack", VertexSize -> {"Scaled", 0.05}, 
   VertexLabels -> Placed[Automatic, Center], 
   VertexLabelStyle -> White, EdgeStyle -> Thick};

Here's a sample graph:

SeedRandom[42]
rg = RandomGraph[{20, 40}, style]

enter image description here

Find the vertex cover:

cover = IGMembershipToPartitions[rg]@IGMinimumVertexColoring@GraphComplement[rg]
(* {{1, 3}, {2, 14, 16}, {4, 9}, {5, 13, 20}, {6, 10}, {7, 18}, {8, 11}, {12, 19}, {15, 17}} *)

IGMembershipToPartitions is just a helper to convert a list of colours into groups of vertices having the same colour. You can read up on it in detail in the IGraph/M documentation.

Visualize it:

HighlightGraph[rg, Subgraph[rg, #] & /@ cover, 
 GraphHighlightStyle -> "DehighlightGray"]

Mathematica graphics

The next version of IGraph/M (possibly 0.3.100 unless everything comes together for 0.4 ...) will have clique cover as a ready-to-use function,

IGCliqueCover[rg]
(* {{1, 3}, {2, 14, 16}, {4, 9}, {5, 13, 20}, {6, 10}, {7, 18}, {8, 11}, {12, 19}, {15, 17}} *)

Compared to the above implementation, this function improves performance and ensures that things work in special situations too (e.g. directed graphs).

Also, if you don't need a minimum clique cover (i.e. fewest cliques), then you may want to use the much faster IGVertexColoring instead of IGMinimumVertexColoring.

$\endgroup$
-1
$\begingroup$

Here is how

g = RandomGraph[{20, 25}, VertexLabels -> "Name"]

Clique figure

FindClique[g, Infinity, All]

{{3, 4, 17}, {2, 10, 16}, {13, 15}, {13, 14}, {12, 16}, {12, 14}, {11,
   19}, {11, 13}, {7, 9}, {6, 20}, {6, 17}, {6, 10}, {5, 17}, {5, 
  14}, {5, 7}, {3, 8}, {3, 7}, {1, 13}, {1, 9}, {2, 9}, {2, 4}, {18}}

In general you cannot partition a graph entirely into cliques, as you seek.

$\endgroup$
  • $\begingroup$ It's not 100% clear to me what the OP is asking, but this seems to find all cliques, not just the maximal cliques (int this sense). $\endgroup$ – Szabolcs Dec 5 '14 at 18:13
  • $\begingroup$ This is not a partition of the vertices. Note that the cliques have non-empty intersections. $\endgroup$ – becko Dec 5 '14 at 18:42
  • $\begingroup$ Please clarify what you're seeking. As stated, in general you cannot partition a graph into cliques as you seem to request. What would you accept as output for the RandomGraph in the figure, for instance, where there are no independent cliques? $\endgroup$ – David G. Stork Dec 5 '14 at 19:06
  • $\begingroup$ @DavidG.Stork A trivial partition into cliques that works for any graph is a partition into subsets containing single vertices. Of course, that's not what I want, but it illustrates that a partition with the conditions I seek always exists. It's only a matter of choosing the most appropriate. $\endgroup$ – becko Dec 5 '14 at 19:08
  • 1
    $\begingroup$ There are 9 configurations that meet his criteria in your graph, one of which is {{2, 10, 16}, {12, 14}, {11, 19}, {7, 9}, {6, 20}, {5, 17}, {3, 8}, {1, 13}, {18}}. $\endgroup$ – Kellen Myers Dec 5 '14 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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