Consider a complete $N$-partite graph $X$ with $X_n$ denoting the $n$-th vertex bin for $1 \leq n \leq N$, where we may assume that each $X_n$ has $k$ vertices for some universal constant $k$. Assume that the edges have positive real weights and also consider a real number $r \geq 0$.
A clique is a collection of $N$ vertices, one from each bin. By completeness of $X$, any two such vertices are connected by an edge. The weight of a clique is defined to be the maximal weight among all edges contained in that clique.
Given $X$ and $r$ as above, is there an efficient algorithm that answers yes if it is possible decompose $X$ into $k$ cliques so that the weight of each clique is less than or equal to $r$, and no if there is no such decomposition?
My question is similar to the one here but I am not looking to minimize the clique weight across all possible decompositions, just to confirm that there is a decomposition satisfying the upper bound of $r$.
Update: Since the problem is unfortunately NP complete (see the answer below),
Are there any known polynomial-time approximations and/or practical heuristics to attack such a problem?
