Clique weight-optimal matchings on n-partite graphs.

Question

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.

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.

Answer 1

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 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.

Answer 2

No, I don't think there is an efficient algorithm for this problem (unless P=NP). See 3-dimensional matching for an unweighted version of this problem (i.e. you can think of having 2 types of weights, one very small, so you'd never take it, and the other big enough).