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][1] 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?


  [1]: http://mathoverflow.net/questions/99752/clique-weight-optimal-matchings-on-n-partite-graphs