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

Posted 7 months ago
599 Views
|
6 Replies
|
1 Total Likes
|
 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
6 Replies
Sort By:
Posted 7 months ago
 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 7 months 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 7 months ago
 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" ] Or if you like, CommunityGraphPlot[g, cover] This minimum cover consists of 7, not 8, cliques. If this is not what you wanted, please clarify.
Posted 7 months ago
 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.