# (Heuristic for) Partitioning n-partite weighted graphs into bounded n-cliques

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?

-

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.

-