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](https://mathoverflow.net/questions/99752/clique-weight-optimal-matchings-on-n-partite-graphs) 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?
> 
> 
> 



(Heuristic for) Partitioning n-partite weighted graphs into bounded n-cliques
The reduction in the answer to the question you have linked to shows that your problem is NP-complete. For a complete 3-partite graph with edge weights 1 and 2 it is NP-complete to decide if there is a decomposition into triangles of weight 1 (your weight function). Actually, usually NP-completeness of an optimization problem is *defined* by NP-completeness of the corresponding decision problem, if there exists a solution reaching a given threshold. 


