[Model] PartitionIntoPerfectMatchings

[isPANN]

Motivation

PARTITION INTO PERFECT MATCHINGS (P27) from Garey & Johnson, A1.1 GT16. A classical NP-complete problem related to graph factorization. The problem asks whether the vertices of a graph can be partitioned into groups, each inducing a perfect matching (1-regular subgraph). Closely related to Schaefer's "2-colorable perfect matching" problem when K=2.

Associated rules:

• [Rule] NOT-ALL-EQUAL 3SAT to PARTITION INTO PERFECT MATCHINGS #845: NOT-ALL-EQUAL 3SAT → PartitionIntoPerfectMatchings (Schaefer, 1978)

Definition

Name: PartitionIntoPerfectMatchings
Canonical name: PARTITION INTO PERFECT MATCHINGS
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT16

Mathematical definition:

INSTANCE: Graph G = (V,E), positive integer K ≤ |V|.
QUESTION: Can the vertices of G be partitioned into k ≤ K disjoint sets V_1, V_2, . . . , V_k such that, for 1 ≤ i ≤ k, the subgraph induced by V_i is a perfect matching (consists entirely of vertices with degree one)?

Clarification: Each set V_i must have even cardinality, and every vertex in V_i must be adjacent to exactly one other vertex in V_i. Equivalently, the induced subgraph G[V_i] is a 1-regular graph (a disjoint union of edges).

Variables

• Count: n = |V| variables (one per vertex)
• Per-variable domain: {0, 1, ..., K-1}, indicating which matching group the vertex belongs to
• Meaning: Variable i = j means vertex i is assigned to group V_j. A valid assignment requires that within each group V_j, every vertex has exactly one neighbor also in V_j (the induced subgraph is a perfect matching on V_j).

Schema (data type)

Type name: PartitionIntoPerfectMatchings
Variants: graph topology (graph type parameter G)

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E)
num_matchings	usize	The bound K on the number of matching groups

Notes:

• This is a satisfaction (decision) problem: Value = Or, implementing feasibility semantics.
• Key getter methods: num_vertices() (= |V|), num_edges() (= |E|), num_matchings() (= K).
• No weight type is needed (purely structural question).
• Each V_i must have even size, and |V| must be divisible by 2 (necessary condition: each group pairs all its vertices).
• When K = 2, this is Schaefer's "2-colorable perfect matching" problem: can vertices be 2-colored so each vertex has exactly one same-color neighbor?

Complexity

• Decision complexity: NP-complete (Schaefer, 1978). Transformation from NOT-ALL-EQUAL 3SAT. Remains NP-complete for K = 2 and for planar cubic graphs.
• Best known exact algorithm: O*(K^n) via exhaustive search over vertex partitions into K groups. No significantly faster exact algorithm is known for the general case.
• Concrete complexity expression: "num_matchings^num_vertices" (for declare_variants!)
• Special cases:
  • K = 1: reduces to checking if G has a perfect matching (polynomial time, Edmonds' algorithm).
  • K = 2: NP-complete even for planar cubic graphs (Schaefer, 1978).
  • K-regular bipartite graphs: always has a partition into K perfect matchings (by Hall's theorem and repeated matching extraction), so the answer is always YES and the problem is trivially polynomial.
• References:
  • T. J. Schaefer (1978). "The complexity of satisfiability problems." In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216-226.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K ≤ |V|.
QUESTION: Can the vertices of G be partitioned into k ≤ K disjoints sets V_1, V_2, . . . , V_k such that, for 1 ≤ i ≤ k, the subgraph induced by V_i is a perfect matching (consists entirely of vertices with degree one)?
Reference: [Schaefer, 1978b]. Transformation from NOT-ALL-EQUAL 3SAT.
Comment: Remains NP-complete for K = 2 and for planar cubic graphs.

How to solve

• It can be solved by (existing) bruteforce — enumerate all assignments of vertices to K groups and check that each group induces a perfect matching (every vertex has exactly one neighbor in its group).
• It can be solved by reducing to integer programming — binary variables x_{v,j} for vertex v in group j, constraints: each vertex in exactly one group, each vertex has exactly one neighbor in the same group. Companion rule issue to be filed separately.
• Other: (TBD)

Example Instance

Instance 1 (YES — partition into perfect matchings exists):
Graph G with 4 vertices {0, 1, 2, 3} and 4 edges, K = 2:

• Edges: {0,1}, {2,3}, {0,2}, {1,3}
• Partition: V_1 = {0, 1}, V_2 = {2, 3}
  • V_1: edge {0,1} present, both have degree 1 in V_1 — perfect matching ✓
  • V_2: edge {2,3} present, both have degree 1 in V_2 — perfect matching ✓
• Answer: YES (4 valid partitions out of 16 total with K=2)

Instance 2 (NO — no partition into K perfect matchings exists):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 6 edges, K = 2:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,0} (a 6-cycle C_6)
• For V_i to be a perfect matching, each vertex in V_i needs exactly one V_i-neighbor.
• Any attempt fails: e.g., V_1 = {0,1,4,5} has vertex 0 with 2 neighbors in V_1 (vertices 1 and 5).
• Answer: NO (0 valid partitions out of 64 with K=2)

Python validation script

from itertools import product

def count_valid(n, edges, K):
    edge_set = set(edges) | set((b,a) for a,b in edges)
    count = 0
    for assign in product(range(K), repeat=n):
        valid = True
        for g in range(K):
            members = [v for v in range(n) if assign[v] == g]
            if len(members) == 0: continue
            for v in members:
                nb = sum(1 for u in members if u != v and (v,u) in edge_set)
                if nb != 1: valid = False; break
            if not valid: break
        if valid: count += 1
    return count

# Instance 1: YES
assert count_valid(4, [(0,1),(2,3),(0,2),(1,3)], 2) == 4
print("Instance 1: 4/16 valid (YES)")

# Instance 2: NO (C6)
assert count_valid(6, [(i,(i+1)%6) for i in range(6)], 2) == 0
print("Instance 2: 0/64 valid (NO)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; concrete reduction from NAE-3SAT cited
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	✅ Pass	Schaefer 1978 reference verified; definition matches G&J GT16
Well-written	⚠️ Warn	Missing ILP crossref issue; complexity expression missing

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

Pass. PartitionIntoPerfectMatchings does not exist in the codebase. The issue cites a concrete reduction from NOT-ALL-EQUAL 3SAT (Schaefer 1978), which connects it to the existing reduction graph. The existing problems PartitionIntoTriangles and PartitionIntoPathsOfLength2 are related partition-type problems but structurally distinct.

Non-trivial

Pass. This problem has genuinely different feasibility constraints from all existing problems. While the codebase has PartitionIntoTriangles (induced triangles) and PartitionIntoPathsOfLength2 (induced P_3), this problem requires each group to induce a 1-regular graph (disjoint union of edges). The constraint structure is fundamentally different — vertex degree in each group must be exactly 1, not 2 (as in paths/cycles) or forming triangles.

Correctness

Pass. Verified findings:

• Schaefer 1978 reference: Confirmed. The paper "The Complexity of Satisfiability Problems" (STOC 1978, pp. 216-226) by Thomas J. Schaefer is already in the project bibliography (schaefer1978). The paper establishes NP-completeness of "2-colorable perfect matching" via reduction from NAE-3SAT.
• G&J GT16 classification: The issue correctly identifies this as GT16 from Garey & Johnson Appendix A1.1.
• NP-completeness claim: Correct. Remains NP-complete for K=2 and planar cubic graphs (Schaefer 1978).
• K=1 polynomial case: Correct. K=1 reduces to finding a single perfect matching, solvable in polynomial time by Edmonds' algorithm.
• K-regular bipartite claim: Correct. By Hall's theorem, a K-regular bipartite graph can be decomposed into K perfect matchings.
• Complexity O(2^n):* The issue claims O*(2^n) via exhaustive search. This is a valid naive bound. No significantly faster exact algorithm is known for the general case.
• Definition correctness: The formal definition matches the G&J book text reproduced in the "Extra Remark" section. The clarification that each V_i induces a 1-regular graph is accurate.
• Examples verified: Both examples were verified by brute-force Python enumeration:
  • Example 1 (YES): 4 satisfying partitions out of 16 total configurations — adequate for round-trip testing.
  • Example 2 (NO): Confirmed no valid partition exists for C_6 with K=2.

Well-written

Warn. The issue is generally well-structured but has a few items to address:

1. Missing ILP crossref (Warn): The "How to solve" section checks the ILP box but does not link a companion [Rule] PartitionIntoPerfectMatchings to ILP issue. Per template requirements, if direct ILP solvability is claimed, a companion rule issue must be linked or ILP solving should be noted as being implemented together with the model.

2. Missing concrete complexity expression (Warn): The Complexity section says "O*(2^n) via exhaustive search" but does not provide a concrete complexity expression in terms of problem-specific getter methods. The declare_variants! macro requires a string like "num_matchings^num_vertices" (since each vertex is assigned to one of K groups, giving K^n configurations).

3. Example quality (Pass with note): Example 1 (4 vertices, K=2) is small but adequate for a satisfaction problem — it has 4 satisfying and 12 non-satisfying configurations, providing meaningful test coverage. Example 2 (6-cycle, K=2) correctly demonstrates a NO instance. Both exercise the core 1-regularity constraint.

4. Naming convention (Pass): As a satisfaction/decision problem, no Maximum/Minimum prefix is needed. The name PartitionIntoPerfectMatchings follows the pattern of existing problems (PartitionIntoTriangles, PartitionIntoPathsOfLength2).

5. Schema (Pass): The proposed schema with graph: SimpleGraph and num_matchings: usize is appropriate and consistent with similar partition problems in the codebase.

Recommendations

• Add a concrete complexity expression such as "num_matchings^num_vertices" (since each vertex is assigned to one of K groups, giving K^n configurations).
• Consider filing a companion [Rule] PartitionIntoPerfectMatchings to ILP issue or clarify that ILP solving will be implemented together with the model (per the project convention for Model issues that claim direct ILP solvability).

[isPANN]

Fix-issue changelog

• Associated rules: Linked [Rule] NOT-ALL-EQUAL 3SAT to PARTITION INTO PERFECT MATCHINGS #845 (NAE-3SAT → PartitionIntoPerfectMatchings).
• Complexity: Added concrete expression "num_matchings^num_vertices" for declare_variants!.
• Schema notes: Added getter methods (num_vertices(), num_edges(), num_matchings()).
• ILP: Added companion rule note.
• Examples: Added exact valid-partition counts (4/16 and 0/64).
• Added Python validation script.

Applied by /fix-issue.

[isPANN]

Please kindly check the following items (PR #960):

• Paper (PDF): check definition, proof sketch, example figure, and reproducible pred commands
• Implementation (Optional): spot-check the source files changed in this PR for correctness

💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.