[Rule] 3-DIMENSIONAL MATCHING to 3-MATROID INTERSECTION

[isPANN]

Source: 3-DIMENSIONAL MATCHING
Target: 3-MATROID INTERSECTION

Motivation: Garey & Johnson list this as the reference transformation proving 3-Matroid Intersection is NP-complete. 3DM is a special case of 3-MI where all three matroids are partition matroids, making this a natural and direct embedding.
Reference: Garey & Johnson, Computers and Intractability, SP11, p.223

GJ Source Entry

[SP11] 3-MATROID INTERSECTION
INSTANCE: Three matroids (E,F_1),(E,F_2),(E,F_3), positive integer K≤|E|. (A matroid (E,F) consists of a set E of elements and a non-empty family F of subsets of E such that (1) S∈F implies all subsets of S are in F and (2) if two sets S,S'∈F satisfy |S|=|S'|+1, then there exists an element e∈S−S' such that (S'∪{e})∈F.)
QUESTION: Is there a subset E'⊆E such that |E'|=K and E'∈(F_1∩F_2∩F_3)?
Reference: Transformation from 3DM.
Comment: The related 2-MATROID INTERSECTION problem can be solved in polynomial time, even if the matroids are described by giving polynomial time algorithms for recognizing their members, and even if each element e∈E has a weight w(e)∈Z^+, with the goal being to find an E'∈(F_1∩F_2) having maximum total weight (e.g., see [Lawler, 1976a]).

Reduction Algorithm

Input: A 3DM instance with disjoint sets W = {w_1, ..., w_q}, X = {x_1, ..., x_q}, Y = {y_1, ..., y_q} and a set T ⊆ W × X × Y of triples.

Output: A 3-Matroid Intersection instance with three partition matroids on ground set E = T and bound K = q.

Construction:

1. Let the ground set E = T (each triple becomes an element).
2. Construct partition matroid M1 for W: for each w_i ∈ W, create a group G1_i = { t ∈ T : the W-component of t is w_i }. A set S ⊆ E is independent in M1 iff |S ∩ G1_i| ≤ 1 for all i.
3. Construct partition matroid M2 for X: for each x_j ∈ X, create a group G2_j = { t ∈ T : the X-component of t is x_j }. A set S ⊆ E is independent in M2 iff |S ∩ G2_j| ≤ 1 for all j.
4. Construct partition matroid M3 for Y: for each y_k ∈ Y, create a group G3_k = { t ∈ T : the Y-component of t is y_k }. A set S ⊆ E is independent in M3 iff |S ∩ G3_k| ≤ 1 for all k.
5. Set K = q = |W| = |X| = |Y|.

Correctness: A common independent set E' of size q in M1 ∩ M2 ∩ M3 selects exactly q triples such that each element of W, X, and Y appears in exactly one selected triple. This is precisely a perfect 3-dimensional matching.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
ground_set_size	num_triples
num_groups (per matroid)	q (=
bound	q

Validation Method

Forward direction: Given a 3DM matching M ⊆ T of size q, take E' = M. Since M uses each element of W, X, Y exactly once, E' picks at most one triple from each partition group in all three matroids. So E' is a common independent set of size q.

Backward direction: Given a common independent set E' of size q in M1 ∩ M2 ∩ M3, the q selected triples each use a distinct element from W (by M1), a distinct element from X (by M2), and a distinct element from Y (by M3). Since |E'| = q = |W| = |X| = |Y|, every element is covered exactly once. So E' is a perfect 3-dimensional matching.

Example

3DM Instance:

• W = {w1, w2}, X = {x1, x2}, Y = {y1, y2}
• T = {t0=(w1,x1,y1), t1=(w1,x2,y2), t2=(w2,x1,y2), t3=(w2,x2,y1)}

Reduction to 3-MI:

• Ground set E = {t0, t1, t2, t3} (4 elements)
• M1 (partition by W): {t0, t1} (w1-triples), {t2, t3} (w2-triples)
• M2 (partition by X): {t0, t2} (x1-triples), {t1, t3} (x2-triples)
• M3 (partition by Y): {t0, t3} (y1-triples), {t1, t2} (y2-triples)
• K = 2

Solution: E' = {t1, t3} = {(w1,x2,y2), (w2,x2,y1)}.

• M1: t1 ∈ {t0,t1}, t3 ∈ {t2,t3} -- one per group. OK.
• M2: t1 ∈ {t1,t3}, t3 ∈ {t1,t3} -- two from same group! Not independent.

E' = {t0, t2} = {(w1,x1,y1), (w2,x1,y2)}.

• M1: t0 ∈ {t0,t1}, t2 ∈ {t2,t3} -- one per group. OK.
• M2: t0 ∈ {t0,t2}, t2 ∈ {t0,t2} -- two from same group! Not independent.

E' = {t0, t3} = {(w1,x1,y1), (w2,x2,y1)}.

• M1: t0 ∈ {t0,t1}, t3 ∈ {t2,t3} -- one per group. OK.
• M2: t0 ∈ {t0,t2}, t3 ∈ {t1,t3} -- one per group. OK.
• M3: t0 ∈ {t0,t3}, t3 ∈ {t0,t3} -- two from same group! Not independent.

E' = {t1, t2} = {(w1,x2,y2), (w2,x1,y2)}.

• M1: t1 ∈ {t0,t1}, t2 ∈ {t2,t3} -- one per group. OK.
• M2: t1 ∈ {t1,t3}, t2 ∈ {t0,t2} -- one per group. OK.
• M3: t1 ∈ {t1,t2}, t2 ∈ {t1,t2} -- two from same group! Not independent.

No common independent set of size 2 exists. This corresponds to the 3DM instance having no perfect matching (every pair of triples shares a coordinate value). Answer: NO.

References

• [Lawler, 1976a]: [Lawler1976a] Eugene L. Lawler (1976). "Combinatorial Optimization: Networks and Matroids". Holt, Rinehart and Winston, New York.
• [Doron-Arad et al., 2024]: Ilan Doron-Arad et al. (2024). "You (Almost) Can't Beat Brute Force for 3-Matroid Intersection". arXiv:2412.02217.