Message Boards Message Boards

Find the minimal amount of cliques to cover the whole network?

Posted 6 years ago

Dear all,

I'm new to Mathematica and would love to use the language to solve a network problem, which bothers me for a while. I'm trying to find the minimal amount of cliques that I need to cover the whole network using each node only once. During my Internet search I discovered this site https://mathematica.stackexchange.com/questions/26296/is-there-a-function-to-generate-a-minimal-clique-cover ,which already tries this. But the posted program returns not the number I'm looking for.

This is as far as I got at the moment:

g = Graph[{0 <-> 1, 0 <-> 4, 0 <-> 7, 0 <-> 10, 0 <-> 14, 1 <-> 3, 
   1 <-> 4, 1 <-> 6, 1 <-> 7, 1 <-> 11, 1 <-> 13, 1 <-> 16, 2 <-> 5, 
   2 <-> 7, 2 <-> 8, 2 <-> 14, 2 <-> 15, 2 <-> 16,
   3 <-> 4, 3 <-> 6, 3 <-> 12, 3 <-> 13, 3 <-> 16, 3 <-> 17, 4 <-> 5, 
   4 <-> 6, 4 <-> 8, 4 <-> 16, 5 <-> 7, 5 <-> 8, 5 <-> 12, 5 <-> 13,
   5 <-> 16, 5 <-> 18, 5 <-> 19, 6 <-> 14, 7 <-> 14, 7 <-> 15, 
   7 <-> 18, 7 <-> 19, 8 <-> 9, 8 <-> 11, 8 <-> 15, 8 <-> 16, 
   9 <-> 12, 9 <-> 13, 9 <-> 14,
   10 <-> 15, 10 <-> 19, 11 <-> 16, 11 <-> 17, 11 <-> 18, 12 <-> 19, 
   13 <-> 17, 13 <-> 18, 13 <-> 19, 15 <-> 16, 15 <-> 17, 15 <-> 19}, 
  VertexLabels -> "Name"]
a = FindClique[g, Infinity, All]

Note: I know that I have to improve the implementation of my graph, but this I'll do on my own later on.

With FindClique[,Infinity, All] I've got every single Clique which is possible besides the 'trivial Cliques' containing only the edge itself, which I would like to allow additionally.

My idea, which I failed to implement, is the following one:

First I could create a new graph, with the edges representing the former found cliques, and connect them only if the cliques they represent contain one or more equal edges. Afterwards I could take the minimum of independent edges of this new graph and check if they contain as many edges as I had in the first graph(in this example 20). If that's the case I'm done and have my number, else I could take another minimal sample or increase the number by 1 until I found my number.

Do you think this is an appropriate way of solving my issue and do you have any suggestion how to tackle it?

Best, Robert

POSTED BY: Robert Marks
6 Replies

I'm glad it helped. If you find any issues with the package, let me know. The next version will include functions for minimum clique cover and clique covering number calculations.

POSTED BY: Szabolcs Horvát
Posted 6 years ago

Hey Horvát,

thank you very much for your answer. Your IGraph/M package was exactly what I was looking for. Thanks a lot.

Best, Robert

POSTED BY: Robert Marks

With FindClique[,Infinity, All] I've got every single Clique which is possible besides the 'trivial Cliques' containing only the edge itself, which I would like to allow additionally.

What you say is not quite accurate. FindClique finds maximal cliques, including two-vertex cliques. It does not find non-maximal ones.

POSTED BY: Szabolcs Horvát

Can you clarify what exactly you want to compute?

Do you need a clique vertex cover or a clique edge cover? I assume you mean the former, since you said that each vertex must be present in only one clique.

This problem is equivalent to colouring the complement graph.

My package IGraph/M has minimum colouring functionality.

Now we can do this:

g = Graph[{0 <-> 1, 0 <-> 4, 0 <-> 7, 0 <-> 10, 0 <-> 14, 1 <-> 3, 
    1 <-> 4, 1 <-> 6, 1 <-> 7, 1 <-> 11, 1 <-> 13, 1 <-> 16, 2 <-> 5, 
    2 <-> 7, 2 <-> 8, 2 <-> 14, 2 <-> 15, 2 <-> 16, 3 <-> 4, 3 <-> 6, 
    3 <-> 12, 3 <-> 13, 3 <-> 16, 3 <-> 17, 4 <-> 5, 4 <-> 6, 4 <-> 8,
     4 <-> 16, 5 <-> 7, 5 <-> 8, 5 <-> 12, 5 <-> 13, 5 <-> 16, 
    5 <-> 18, 5 <-> 19, 6 <-> 14, 7 <-> 14, 7 <-> 15, 7 <-> 18, 
    7 <-> 19, 8 <-> 9, 8 <-> 11, 8 <-> 15, 8 <-> 16, 9 <-> 12, 
    9 <-> 13, 9 <-> 14, 10 <-> 15, 10 <-> 19, 11 <-> 16, 11 <-> 17, 
    11 <-> 18, 12 <-> 19, 13 <-> 17, 13 <-> 18, 13 <-> 19, 15 <-> 16, 
    15 <-> 17, 15 <-> 19}, VertexLabels -> "Name"];

This is a minimum colouring of the complement graph:

In[41]:= IGMinimumVertexColoring@GraphComplement[g]    
Out[41]= {5, 7, 7, 5, 1, 5, 7, 7, 2, 3, 6, 6, 6, 6, 1, 4, 3, 2, 1, 4}

IGraph/M has a function to convert a labelling of vertices with (possibly equal) consecutive integers (i.e. "membership indices") to partitions that contain vertices with the same indices.

Thus we can obtain the vertex clique cover like this:

In[42]:= cover = IGMembershipToPartitions[g]@IGMinimumVertexColoring@GraphComplement[g]
Out[42]= {{0, 7, 14}, {1, 4, 3, 6}, {10, 15, 19}, {11, 18}, {13, 17}, {16, 2, 5, 8}, {12, 9}}

This form is easy to visualize:

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

Mathematica graphics

Or if you like,

CommunityGraphPlot[g, cover]

Mathematica graphics

This minimum cover consists of 7, not 8, cliques. If this is not what you wanted, please clarify.

POSTED BY: Szabolcs Horvát
Posted 6 years ago

To be more specific on the failure of the stated article in my case. If I use those functions I get a result like {44,33}; which isn't the number I'm looking for. I used a well known example data set, to create the graph and the solution for my problem should be 8, which isn't what the functions of the article return.

POSTED BY: Robert Marks

During my Internet search I discovered this site https://mathematica.stackexchange.com/questions/26296/is-there-a-function-to-generate-a-minimal-clique-cover ,which already tries this. But the posted program returns not the number I'm looking for.

It might be good if you post a specific example where that implementation fails and explain how it fails, then notify the author of that answer.

POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract