Covering a graph with non-overlapping cliques

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.

• – Pål GD Apr 29 '15 at 22:12
• @PålGD Clique cover seems to be the term I was after - I see nothing in the link about taking edge weights into account though. See my edit for my current solution - I would love some feedback on the feasibility of the approach... – ThomasP85 Apr 30 '15 at 7:26
• Thomas, I think your views of subject boundaries are somewhat off-kilter. Computer science is not at all concerned with programming and implementations: it deals with precisely the kind of question you're asking. And graph theory and statistics are rather distant relatives: sure, graph theorists sometimes use statistics as a tool and statisticians sometimes use graphs as tools but that's about as close as they get. – David Richerby Apr 30 '15 at 8:16
• @DavidRicherby You're probably right - I don't come from either disciplines so I'm ready to be educated on the matter. My entrance into graph theory is through clustering, so I've come to see it as an extension of that branch of statistics. Thanks for your explanation. – ThomasP85 Apr 30 '15 at 8:22
• I'm also not sure what exactly you are asking. You have an approach that apparently works. But the question seems to be "what do you think?". Why are you not satisfied with your current approach? Can you make your question more precise? – Juho Apr 30 '15 at 10:38

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.

• The literature often uses either $\overline{\chi}(G) (= \chi(\overline{G}))$ or $\text{cp}(G)$ to denote the clique partitioning number, depending on the context. If you are searching for e.g. bounds, you might want to keep this in mind. – Juho May 5 '15 at 10:01
• This was exactly the kind of insight I was hoping to get. Thanks for the reference, which I'll dig into – ThomasP85 May 5 '15 at 11:35

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'
• Finding maximal cliques is not really the problem - as you note a lot of implementations for that exist. It is resolving overlaps based on edge weights... – ThomasP85 Apr 29 '15 at 10:12