I am trying to analyze the results of a physical experiment consisting of $n$ "runs" of measurements, each of which generates a set of $k$ points in Euclidean space. The following problem came up when trying to quantify the difference between these point sets. I would be extremely surprised if the problem is not already solved, but I was unable to find a solution in graph theory textbooks and on google.


I will outline the problem for $n=3$ because it is the first non-trivial case. Hopefully the solution does not fail for higher $n$. Consider a $3$-partite graph $G$ with vertex bins that we will call Red, Blue and Green. Assume that each bin has the same number of vertices, say $k>0$. Assume now that this graph is complete in the standard sense, i.e., there exists a (positively) weighted edge between any two differently colored vertices. Completeness puts us in a different situation from the one discussed [here](https://mathoverflow.net/questions/92962/k-uniform-k-partite-hypergraph-matching-in-polynomial-time).


By a *matching* $m$ I mean a partition of the vertices into $k$ $3$-cliques of the type (red, blue, green). Each clique $C$ is assigned a weight $w(C)$ which equals the maximum of the weights of the edges in that clique. So a clique consisting of vertices R,B and G is assigned the max weight of the three edges RB, RG and BG. The weight of the matching is defined to be $$W(m) = \max \lbrace w(C)~|~C \text{ is a clique of } m\rbrace.$$


Here is the question: 



> 
> Is there an efficient algorithm to compute $$\inf \lbrace W(m)~|~m \text{ is a matching of }G\rbrace ?$$
> 
> 
> 


Note that the trivial algorithm which consists of constructing all possible matchings is known to me but happens to be a computational nightmare. If this is a known / non-research problem, I apologize. Please just point me to the correct references or search terms in this case.



Clique weight-optimal matchings on n-partite graphs.
The problem is NP-complete which follows by reduction from the problem if a given 3-partite graph $G=(A\cup B\cup C,E)\ $ with $\lvert A\rvert=\lvert B\rvert=\lvert C\rvert=k\ $ can be partitioned into $k$ disjoint triangles. [Here](http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CFkQFjAD&url=http%3A%2F%2Fwww.dimi.uniud.it%2F~rrizzi%2Fclasses%2FComplexity%2Fprovette%2FMirko%2Fpt_fine.pdf&ei=vdrgT6LHMdDUsgbfrIitCA&usg=AFQjCNFztkhcEMl9y2jDKYdLkzUkbPoceA) this problem is shown to be NP-hard by reduction from 3-dimensional matching.
The triangle partition problem can be reduced to the problem from the question by assigning weight $1$ to all edges and weight $2$ to all non-edges. Then the triangle partition exists if and only if the optimal matching (in the sense of the question) has weight 1. 


