1
$\begingroup$

I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class.

Now I am looking for the optimal subset such that each of the N classes is represented exactly once. Not all objects can be combined with each other, e.g. object (N=1,k=1) might not be compatible with (N=2, k=4).

I can formulate this problem as looking for the maximal clique on a N-partite graph (but maybe there are other formulations that I'm not aware of). My question is whether an efficient algorithm exists for solving this problem.

From https://stackoverflow.com/questions/2801138/find-all-complete-sub-graphs-within-a-graph:

This is known as the clique problem; it's hard and is in NP-complete in general, and yes there are many algorithms to do this.

If the graph has additional properties (e.g. it's bipartite), then the problem becomes considerably easier and is solvable in polynomial time

This implies that an efficient algorithm might exist for my problem, but I can't find it...

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

A maximal clique and a maximum clique are in general different. A set of vertices $S$ is a maximal clique if $S$ is a clique and you cannot add any vertex to $S$ such that the resulting set would form a clique. The set $S$ forms a maximum clique when there is no other set of vertices that forms a clique that is larger than $S$.

You mention bipartite graphs, but the complete $k$-partite graph is not bipartite if $k \geq 3$ (but it is for $k=2$). A bipartite graph contains no triangles, so in such a graph a maximum clique has size (at most) 2, so an efficient algorithm can just return a single edge.

Let $G = K_{n_1,\ldots,n_q}$ for positive integers $n_1,n_2,\ldots,n_q \geq 2$. You can verify that $G$ has maximum clique size $q$, and a total of $n_1 \cdot n_2 \cdots \cdot n_q$ such cliques. An algorithm for enumerating all of them reduces to basic combinatorics (pick one vertex, then how many choices for the remaining vertices do you have when forming a clique?)

Improve this answer
$\endgroup$
2
$\begingroup$

I'm afraid this is NP-hard, as it's essentially just the regular Maximum Clique problem in disguise: every graph $G = (V, E)$ is a $|V|$-partite graph, with a single vertex in each part. So if an algorithm could efficiently solve the $(N=|V|, k=1)$ setting of your problem, it could efficiently solve Maximum Clique.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks - are there fast (approximation) algorithms to just identify a clique of size N, if it exists? $\endgroup$
    – Lars Velten
    Commented May 9, 2019 at 13:10
  • $\begingroup$ @LarsVelten There are good and practical tools for finding a maximum clique, or even enumerating all maximum or maximal cliques. One such tool is cliquer. But max. clique is very hard to approximate; so you will not find good theoretical algorithms for the problem. $\endgroup$
    – Juho
    Commented May 9, 2019 at 13:11
  • $\begingroup$ @LarsVelten: Maximum Clique is essentially impossible to approximate -- for example, unless P=NP, no polynomial-time algorithm exists that will give an answer that is at most, say, 100x smaller than the true answer. $\endgroup$
    – j_random_hacker
    Commented May 9, 2019 at 13:23
  • $\begingroup$ @Juho Cliquer is exactly what I was looking for, thank you! $\endgroup$
    – Lars Velten
    Commented May 9, 2019 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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