[Model] ThreeMatroidIntersection

[isPANN]

Motivation

3-MATROID INTERSECTION (P138) from Garey & Johnson, A3 SP11. Given three matroids on a common ground set and a positive integer K, determine whether there exists a common independent set of size K. NP-completeness is established by transformation from 3-Dimensional Matching (3DM), where each dimension induces a partition matroid. While 2-matroid intersection is solvable in polynomial time (Edmonds, 1970), the jump to three matroids captures NP-hardness. The restriction to partition matroids suffices for NP-completeness and provides a concrete, implementable representation.

Associated rules:

• [Rule] 3-DIMENSIONAL MATCHING to 3-MATROID INTERSECTION #857 / [Rule] 3-DIMENSIONAL MATCHING to 3-MATROID INTERSECTION #386: 3-DIMENSIONAL MATCHING → ThreeMatroidIntersection (classical NP-completeness proof from G&J)

Definition

Name: ThreeMatroidIntersection
Reference: Garey & Johnson, Computers and Intractability, A3 SP11

Mathematical definition:

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

Variables

• Count: |E| (size of the ground set)
• Per-variable domain: {0, 1}
• Meaning: Whether each element of the ground set E is included in the common independent set E'.

Schema (data type)

Type name: ThreeMatroidIntersection
Variants: Restricted to partition matroids. Each partition matroid is specified by a partition of the ground set into groups, where an independent set may contain at most one element from each group.

Field	Type	Description
ground_set_size	usize	Number of elements in the ground set E
partitions	Vec<Vec<Vec<usize>>>	Three partition matroids, each given as a list of groups (each group is a list of element indices)
bound	usize	Required size K of the common independent set

Notes:

• This is a feasibility (decision) problem: Value = Or.
• Key getter methods: ground_set_size() (= |E|), num_groups() (total number of groups across all three matroids), bound() (= K).
• The restriction to partition matroids preserves NP-completeness (the 3DM reduction uses partition matroids).

Complexity

• Decision complexity: NP-complete (Garey & Johnson, 1979; transformation from 3-Dimensional Matching). The 2-matroid intersection problem is solvable in polynomial time (Edmonds, 1970).
• Best known exact algorithm: O*(2^n) brute force, where n = |E|. Doron-Arad, Kulik, and Shachnai (2024) showed that brute force essentially cannot be beaten: any algorithm requires Ω(2^(n − 5√n log n)) oracle queries. A marginal improvement to 2^(n − Ω(log² n)) exists via Monotone Local Search (Fomin et al., 2019).
• Concrete complexity expression: "2^ground_set_size" (for declare_variants!)
• References:
  • M.R. Garey and D.S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman.
  • I. Doron-Arad, A. Kulik, H. Shachnai (2024). "You (Almost) Can't Beat Brute Force for 3-Matroid Intersection." arXiv:2412.02217.
  • F.V. Fomin, D. Lokshtanov, F. Panolan, S. Saurabh (2019). "Exact Algorithms via Monotone Local Search." J. ACM 66(2), Article 8.
  • J. Edmonds (1970). "Submodular functions, matroids, and certain polyhedra." Combinatorial Structures and Their Applications, pp. 69-87.

Extra Remark

Full book text:

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

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^|E| subsets of size K; check independence in all three matroids.)
• It can be solved by reducing to integer programming.
• Other:

Example Instance

Ground set: E = {0, 1, 2, 3, 4, 5} (6 elements), K = 2.

Matroid M1 (partition matroid): groups {0, 1, 2}, {3, 4, 5}. At most one element per group.

Matroid M2 (partition matroid): groups {0, 3}, {1, 4}, {2, 5}. At most one element per group.

Matroid M3 (partition matroid): groups {0, 4}, {1, 5}, {2, 3}. At most one element per group.

Valid common independent set of size 2: E' = {0, 5}.

• M1: 0 ∈ {0,1,2}, 5 ∈ {3,4,5} — at most one per group. ✓
• M2: 0 ∈ {0,3}, 5 ∈ {2,5} — at most one per group. ✓
• M3: 0 ∈ {0,4}, 5 ∈ {1,5} — at most one per group. ✓

Answer: YES — a common independent set of size K = 2 exists.

Why non-trivial: Of the C(6,2) = 15 possible 2-element subsets, only 3 are common independent sets ({0,5}, {1,3}, {2,4}). Most pairs (e.g., {0,3} fails M2; {0,4} fails M3; {1,2} fails M1) violate at least one matroid constraint.

Negative modification: Change K = 3. Now we need a common independent set of size 3. Each matroid M1 has 2 groups, so independent sets have size ≤ 2 in M1. Therefore no common independent set of size 3 exists. Answer: NO.

Python validation script

from itertools import combinations

def is_partition_independent(subset, groups):
    for g in groups:
        if sum(1 for e in subset if e in g) > 1:
            return False
    return True

E = list(range(6))
M1 = [{0,1,2}, {3,4,5}]
M2 = [{0,3}, {1,4}, {2,5}]
M3 = [{0,4}, {1,5}, {2,3}]

# Find all common independent sets of size 2
valid_k2 = []
for subset in combinations(E, 2):
    s = set(subset)
    if all(is_partition_independent(s, M) for M in [M1, M2, M3]):
        valid_k2.append(s)

assert {0,5} in valid_k2
assert len(valid_k2) == 3
print(f"K=2: {len(valid_k2)} common independent sets: {valid_k2}")

# Verify no common independent set of size 3
valid_k3 = []
for subset in combinations(E, 3):
    s = set(subset)
    if all(is_partition_independent(s, M) for M in [M1, M2, M3]):
        valid_k3.append(s)
assert len(valid_k3) == 0
print(f"K=3: {len(valid_k3)} common independent sets (correct: NO)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No concrete reduction to/from any existing problem is mentioned
Non-trivial	✅ Pass	Distinct feasibility constraints (3-matroid intersection) not in codebase
Correctness	✅ Pass	References verified; complexity bounds accurate (see recommendation)
Well-written	❌ Fail	Name inconsistency between title and body; missing Expected Outcome section; vague motivation

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

The issue does not mention any concrete reduction rule connecting ThreeMatroidIntersection to an existing problem in the graph. The motivation says only "A classical NP-complete problem useful for reductions" without specifying which reductions are planned. Per the check-issue criteria, a problem without any planned reduction rule would be an orphan node in the reduction graph.

Required fix: Add at least one concrete planned reduction (e.g., "3DM reduces to ThreeMatroidIntersection" or "ThreeMatroidIntersection reduces to ILP") with a reference to an existing or planned [Rule] issue.

Non-trivial

ThreeMatroidIntersection is a genuinely distinct problem. It asks whether three matroids share a common independent set of a given size. No existing problem in the codebase captures this constraint structure. The restriction to partition matroids is a reasonable implementation scope choice. Pass.

Correctness

References verified:

1. Garey & Johnson, A3 SP11: 3-MATROID INTERSECTION is indeed listed in Computers and Intractability under the Sets and Partitions category. The definition matches the standard formulation. The NP-completeness proof is via reduction from 3DM (as stated). Confirmed.

2. Doron-Arad, Kulik, Shachnai (2024): The paper "You (Almost) Can't Beat Brute Force for 3-Matroid Intersection" (December 2024, arXiv:2412.02217) confirms the lower bound of Omega(2^(n - 5*sqrt(n)*log(n))) oracle queries. Authors and year match. The specific bound quoted in the issue is correct.

3. Fomin et al., Monotone Local Search: The paper "Exact Algorithms via Monotone Local Search" was published in JACM 2019. The 2^(n - Omega(log^2 n)) upper bound referenced in the issue is consistent with the framework described. Confirmed.

4. Edmonds (1970), 2-matroid intersection in P: This is a classical result. Confirmed.

5. Example verification: The example with E = {0,...,5}, K = 2 is correct. The three feasible common independent sets of size 2 are: {0,5}, {1,3}, {2,4}. All three satisfy the partition constraints for all three matroids. Non-feasible pairs (e.g., {0,3}, {0,4}, {1,4}, {1,5}, {2,3}, {2,5}) correctly fail at least one matroid constraint.

Well-written

Failures:

1. Name inconsistency: The issue title says 3MatroidIntersection (starts with a digit, invalid Rust identifier) while the body says ThreeMatroidIntersection. These must be consistent. The body name is correct for Rust conventions (cf. ExactCoverBy3Sets in the codebase).

2. Missing Expected Outcome section: The template requires a clear expected outcome. For this satisfaction problem, the example should explicitly state: "Answer: YES. A valid common independent set is {0,5} because [justification]." While the justification is embedded in the example text, there is no dedicated "Expected Outcome" section.

3. Vague motivation: "A classical NP-complete problem useful for reductions" does not explain why this problem matters for the reduction graph or identify a concrete use case (scheduling, combinatorial optimization, etc.).

4. Complexity expression ambiguity: The Complexity section says the best known algorithm is "O*(2^n) brute force" but then mentions a 2^(n - Omega(log^2 n)) improvement via Monotone Local Search. The declared complexity for declare_variants! should use the best known bound, which is the MLS improvement — not brute force. Also, Omega(log^2 n) is not a concrete numeric value; the complexity string needs a concrete expression per project conventions.

Recommendations

• The complexity string for declare_variants! should be concrete (e.g., "2^ground_set_size" as a conservative bound, since the MLS improvement factor log^2 n is hard to express concretely and the improvement is marginal).
• Consider adding a planned reduction from ExactCoverBy3Sets (X3C) to ThreeMatroidIntersection, since X3C is already in the codebase and the classical NP-completeness proof goes through 3DM → 3-Matroid Intersection.
• The restriction to partition matroids is well-motivated for implementability — consider adding a note about why this restriction preserves NP-hardness (the Hamiltonian path reduction uses partition matroids).

[isPANN]

Fix-issue changelog

• Title: Fixed 3MatroidIntersection → ThreeMatroidIntersection (invalid Rust identifier starting with digit).
• Motivation: Rewrote vague "useful for reductions" with concrete context: 3DM transformation, 2-MI polynomial contrast, partition matroid restriction.
• Associated rules: Linked existing rule issues [Rule] 3-DIMENSIONAL MATCHING to 3-MATROID INTERSECTION #857 and [Rule] 3-DIMENSIONAL MATCHING to 3-MATROID INTERSECTION #386 (3DM → ThreeMatroidIntersection).
• Complexity: Added concrete expression "2^ground_set_size" for declare_variants!.
• Schema notes: Added getter methods (ground_set_size(), num_groups(), bound()).
• Example: Enhanced with non-trivial analysis (3/15 subsets valid) and clear negative modification (K=3 impossible since M1 has only 2 groups).
• Added Python validation script verifying both positive (3 valid sets) and negative (0 valid sets) cases.

Applied by /fix-issue.