Covering a graph with non-overlapping cliques

Question

I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows:

• Every subgraph must be a complete graph/clique
• No vertex can be part of two or more subgraphs
• Subgraphs that can be merged with other subgraphs while remaining complete cannot exist
• When multiple possible complete subgraphs/cliques are present, chose the one with highest within-clique edge weight

Below is an obvious example. Multiple maximal cliques exists, but it is very clear to the beholder which two should constitute the subgraphs.

Community detection are not a good fit (at least the algorithms I've looked into) because they don't enforce completeness within the communities. Furthermore the graphs that I'm working with are quite small and dense, and community detection algorithms will often just find one large community.

My main approach now is thus to find all maximal cliques, and then somehow remove unwanted cliques based on edge weights but I'm at a loss as to what the best approach for the latter part is...

Edit: This is my current implementation

1. Detect maximal cliques in the graph.
2. Sort the cliques in descending order based on their minimum edge weight within the clique.
3. Iterate over the sorted cliques, adding cliques to my result list if, and only if, its member vertices are not present in any already selected clique.

4. After iteration see if any vertices in the original graph are present in any of the selected cliques.

   • If all vertices are present, exit.
   • If not create a subgraph of the original graph containing the missing vertices and repeat 1-4.

This is sort of similar to @kurtosis answer but handles edge weights as well as the case where vertices are left out of the initial iteration.

Edit 2: To clarify what I'm asking (because it might be less obvious after the first edit). My problem remains as described in the first part. After posing the question I've developed a solution as described in the first edit, that seems to get the job done, but it is, in my view, not very elegant. It might be the only way to solve the given problem, but I wouldn't know as graph theory is not my main area. Thus I'm still curious if there are other more efficient approaches to solving the problem.

Answer 1

Thus I'm still curious if there are other more efficient approaches to solving the problem.

If you take the complement graph $\overline{G}$, then your problem corresponds to a coloring problem. Cover by cliques in $G$ is the same as covering by independent set in $\overline{G}$.

The problem is para-NP-hard in the unweighted case and the problem is just hard no matter what you do.

There is an algorithm computing the chromatic number in time $O^*(2^n)$ using exponential space, and in time $O(2.2461^n)$ using polynomial space.

The fastest algorithm I know to get the coloring runs in time $O^*((1+\sqrt[3] 3)^n) = O(2.4423^n)$.

[1] Fomin, F. V., & Kratsch, D. (2010). Exact exponential algorithms. An EATCS Series — Texts in Theoretical Computer Science. Springer.

Answer 2

Try out classical Bron-Kerbosch algorithm. It finds all maximal cliques in a graph and is implemented, for example, in well-known python library networkx: http://networkx.lanl.gov/reference/generated/networkx.algorithms.clique.find_cliques.html

Nevertheless, the cliques still can be overlapping, so the problem of finding the optimal non-overlapping clique set is open. I'm not aware of latest proceedings in the research on this topic. But you can concoct and apply some simple greedy heuristics, like this:

1. Sort all the obtained cliques by the number of participating nodes in descending order, breaking ties with the sum of edge weights
2. Take the first clique as a first community and move to the second
3. If the second clique doesn't overlap the first one, take it as a second community, else move to the third clique, and so on
4. If i-th clique doesn't include any of the nodes taking part in the already selected communities, add i-th clique to the communities, and mark all it's nodes as 'already visited'