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?

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?

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$. It is not even important to find the decomposition explicitly, only to confirm existence. I hope that maybe it is possible to avoid NP-completeness in this simpler setting... thank you for any help. This problem must have been studied by graph theorists but I cannot find a reference.

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?