# 3-dimensional matching approximation algorithm (implementation details)

I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below: How can I construct the maximum matching M_r in S_r in linear time in line 8?

$X, Y, Z$ are disjoint sets; a matching $M$ is a subset of $S$ s.t. no two triples in $M$ have the same coordinate at any dimension.

$\text{Algorithm: unweighted 3-dimensional matching (2-approximation)} \\ \text{Input: a set$S\subseteq X \times Y \times Z$of triples} \\ \text{Output: a matching M in S}$

 1) construct maximal matching M in S;
2) change = TRUE;
3) while (change) {
4)   change = FALSE;
5)   for each triple (a,b,c) in M {
6)     M = M - {(a,b,c)};
7)     let S_r be the set of triples in S not contradicting M;
8)     construct a maximum matching M_r in S_r;
9)     if (M_r contains more than one triple) {
10)       M = M \cup M_r;
11)       change = TRUE;
12)     } else {
13)       M = M \union {(a,b,c)};
14)     }
15) }


• Welcome! "Implementation details" is something this site is not about, but it seems as if you were after an algorithm? – Raphael Jul 1 '12 at 21:45
• Well, I want to implement this algorithm in $O(n^3)$. – Reibach Jul 1 '12 at 21:48

We don't need the maximum matching, just one of cardinality $2$ if it exists.
Scan $S_r$ looking for a triple $T$ such that $\lvert T \cap \{a, b, c\}\rvert = 1$. If no such $T$ exists, then the maximum cardinality of a matching is clearly $1$. Otherwise, assume without loss of generality that $T = \{a, x, y\}$.
Scan $S_r$ again looking for a triple $U$ such that $T \cap U = \varnothing$. If no such $U$ exists, then every triple intersects both $\{a, b, c\}$ and $T$. For every $U \in S_r$, we have $\{a\} \subseteq U$ or $\{b, x\} \subseteq U$ or $\{b, y\} \subseteq U$ or $\{c, x\} \subseteq U$ or $\{c, y\} \subseteq U$.
There are several possibilities for a cardinality-$2$ matching $\{T_1, T_2\}$. There's an easy test for those of type $\{b, x\} \subseteq T_1$ and $\{c, y\} \subseteq T_2$. Similarly, $\{b, y\}$ and $\{c, x\}$. The only other types are the four like $\{a\} \subseteq T_1$ and $\{b, x\} \subseteq T_2$. To test for those, gather all triples of the form $\{b, x, z\} \in S_r$ and discard the ones in excess of three. Try each of the remainder against all possibilities containing $a$. The three $\{b, x, z\}$ candidates suffice because no triple containing neither $b$ nor $x$ intersects all three.
• Why do we only need to consider matchings of cardinality 2? And why is it that if no $T \neq \{a,b,c\}$ exists such that $|T \cap \{a,b,c\}| = 1$ that the cardinality of the matching is 1? – Reibach Jul 3 '12 at 21:55
• "Why do we only need to consider matchings of cardinality 2?" It suffices either to verify that $S_r$ is maximum or grow the matching. "And why is it that..." If every triple has two elements in common with {a, b, c}, then every pair of triples has at least one element in common by the pigeonhole principle. – Herm Jul 4 '12 at 2:03