8
$\begingroup$

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.

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ I think it's not obvious how to reduce 3-dimensional matching. The weights of the triples are not independent. All triples containing an edge have at least the weight of that edge. $\endgroup$ Jun 19, 2012 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.