[Model] PartitionIntoPathsOfLength2

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] PartitionIntoPathsOfLength2"
labels: model
assignees: ''

Motivation

PARTITION INTO PATHS OF LENGTH 2 from Garey & Johnson, Chapter 3, Section 3.3, p.76. A classical NP-complete problem useful for reductions. This problem partitions graph vertices into triples, each inducing a path of length 2 (a P3 subgraph). It serves as a building block for proving NP-completeness of graph partitioning problems.

Note: This problem appears only in GJ Chapter 3 as an NP-completeness proof example; it does not have a dedicated appendix code (unlike GT11 = Partition into Triangles).

Associated reduction rules:

• As source: R31b (PARTITION INTO PATHS OF LENGTH 2 -> BOUNDED COMPONENT SPANNING FOREST) via Hadlock 1974
• As target: Reduced from 3-DIMENSIONAL MATCHING (3DM) in GJ Chapter 3

Definition

Name: PartitionIntoPathsOfLength2
Canonical name: PARTITION INTO PATHS OF LENGTH 2
Reference: Garey & Johnson, Computers and Intractability, Chapter 3, Section 3.3, p.76

Mathematical definition:

INSTANCE: Graph G = (V,E), with |V| = 3q for a positive integer q.
QUESTION: Is there a partition of V into q disjoint sets V_1, V_2, ..., V_q of three vertices each so that, for each V_t = {v_{t[1]}, v_{t[2]}, v_{t[3]}}, at least two of the three edges {v_{t[1]}, v_{t[2]}}, {v_{t[1]}, v_{t[3]}}, and {v_{t[2]}, v_{t[3]}} belong to E?

Variables

• Count: n = |V| variables (one per vertex), encoding which partition group each vertex belongs to
• Per-variable domain: {0, 1, ..., q-1} where q = |V|/3, indicating the index of the partition set the vertex is assigned to
• dims() specification: vec![q; n] where q = num_vertices / 3 and n = num_vertices
• Meaning: Variable i = j means vertex i is assigned to partition set V_j. A valid assignment must place exactly 3 vertices in each group, and each group must induce at least 2 edges (i.e., a path of length 2 or a triangle).

Schema (data type)

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

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E) with |V| = 3q

Size fields (getter methods for overhead expressions):

• num_vertices() -> usize (= |V|)
• num_edges() -> usize (= |E|)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• No weight type is needed (the question is purely structural).
• The constraint |V| = 3q (divisible by 3) is a precondition on the input.

Complexity

• Best known exact algorithm: The general problem is NP-complete. No known sub-exponential algorithm for general graphs. A brute-force approach enumerates all partitions of n vertices into groups of 3, giving O(n! / (3!^q * q!)) configurations to check, which is bounded by O(3^n) using the standard set-partition DP approach. No specific exact algorithm paper improves on this naive bound.
• NP-completeness: Proved by reduction from 3-DIMENSIONAL MATCHING (3DM) in GJ Chapter 3, p.76 (the exact theorem number should be verified from the physical book).
• Special cases: The problem of partitioning into paths of length k in bipartite graphs of maximum degree 3 is NP-complete for all k >= 2.
• declare_variants! guidance:

  crate::declare_variants! {
      PartitionIntoPathsOfLength2<SimpleGraph> => "3^num_vertices",
      / Naive set-partition DP bound; no better exact algorithm known
  }

• References:
  • M. R. Garey and D. S. Johnson (1979). Computers and Intractability, Chapter 3, p.76.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), with |V| = 3q for a positive integer q.
QUESTION: Is there a partition of V into q disjoint sets V_1, V_2, ..., V_q of three vertices each so that, for each V_t = {v_{t[1]}, v_{t[2]}, v_{t[3]}}, at least two of the three edges {v_{t[1]}, v_{t[2]}}, {v_{t[1]}, v_{t[3]}}, and {v_{t[2]}, v_{t[3]}} belong to E?

How to solve

• It can be solved by (existing) bruteforce — enumerate all partitions of V into triples and check the path condition.
• It can be solved by reducing to integer programming — assign binary variables x_{v,j} for vertex v in group j, with constraints ensuring each group has exactly 3 vertices and at least 2 internal edges.
• Other: Dynamic programming over subsets in O(3^n * poly(n)) time.

Example Instance

Instance 1 (YES — partition exists):
Graph G with 9 vertices {0, 1, 2, 3, 4, 5, 6, 7, 8} and 10 edges:

• Edges: {0,1}, {1,2}, {3,4}, {4,5}, {6,7}, {7,8}, {0,3}, {2,5}, {3,6}, {5,8}
• q = 3, so we need 3 groups of 3 vertices
• Partition: V_1 = {0, 1, 2}, V_2 = {3, 4, 5}, V_3 = {6, 7, 8}
  • V_1: edges {0,1} and {1,2} present (path 0-1-2) -- 2 edges present
  • V_2: edges {3,4} and {4,5} present (path 3-4-5) -- 2 edges present
  • V_3: edges {6,7} and {7,8} present (path 6-7-8) -- 2 edges present
• Answer: YES

Instance 2 (NO — no valid partition):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 4 edges:

• Edges: {0,1}, {2,3}, {0,4}, {1,5}
• q = 2, so we need 2 groups of 3 vertices
• Note: vertex 4 and vertex 5 have degree 1 each, vertex 2 and vertex 3 have degree 1 each
• Any group containing both vertices 4 and 5 has at most 1 edge involving them ({0,4} or {1,5}, not both unless 0 or 1 is in the group, but then we need 2 edges in the triple)
• Exhaustive check: no partition of 6 vertices into two triples yields at least 2 edges per triple
• Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all 24 existing problems
Correctness	⚠️ Warn	Reference details need minor corrections; core definition appears correct
Well-written	⚠️ Warn	Minor issues with reference numbering and complexity bound specificity

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. The problem does not exist in the current codebase (verified via pred show). The motivation is reasonable: it is a classical NP-complete problem from Garey & Johnson useful as a building block for graph partitioning reductions. The issue identifies concrete reduction connections — as a target from 3-Dimensional Matching and as a source toward Bounded Component Spanning Forest — which would connect it to the existing reduction graph.

Non-trivial

Pass. This is a genuine vertex-partition problem with a unique feasibility constraint: partitioning vertices into triples where each triple induces at least 2 edges. No existing problem in the codebase (checked all 24 problems via pred list) has this structure. It is not a variant of any existing problem — the closest would be graph coloring or set packing, but the constraints are fundamentally different (fixed-size groups with internal edge requirements vs. independent sets or set disjointness).

Correctness

Warning — minor reference issues:

1. Problem code "P10": The issue header says this is problem "P10" from GJ. However, Garey & Johnson use codes like GT (Graph Theory), ND (Network Design), SP (Sets and Partitions), etc. in their appendix. Graph partitioning problems in GJ use GT codes (e.g., GT11 = Partition into Triangles, GT14 = Partition into Forests, GT15 = Partition into Cliques, GT16 = Partition into Perfect Matchings). The actual GJ appendix code for this problem should be verified. The reference "Chapter 3, Section 3.3, p.76" likely refers to where the NP-completeness proof appears, not the appendix definition.

2. Definition correctness: The mathematical definition given (partition into triples with "at least two of the three edges") is consistent with the standard GJ formulation and is correctly stated. The issue correctly notes that this admits both paths (exactly 2 edges) and triangles (all 3 edges) within each triple.

3. NP-completeness proof: The issue claims reduction from 3-Dimensional Matching (3DM), citing "Theorem 3.5, p.76". This is a plausible reduction source (3DM is a standard NP-completeness proof origin for partition problems), but I was unable to independently verify the exact theorem number from publicly available sources.

4. Hadlock 1974 reference: The associated reduction "R31b" citing Hadlock 1974 for a reduction to Bounded Component Spanning Forest could not be verified through web search. This reference should be checked.

5. Complexity bound: The claim of O(3^n) via set-partition DP is reasonable as a naive upper bound (each vertex assigned to one of q = n/3 groups), though it is not a tight bound from a specific algorithm paper. For the declare_variants! macro, a more precise bound from the literature would be preferable.

Well-written

Warning — minor issues to address:

1. Reference numbering: "P10" should be corrected to the actual GJ appendix code (likely a GT-series number). The issue conflates the chapter where the NP-completeness proof appears (Chapter 3) with the appendix where the problem is cataloged.

2. Complexity section lacks a specific algorithm citation: The complexity section says "No known sub-exponential algorithm" and gives O(3^n) as a bound, but does not cite a specific algorithm paper. For implementation, a concrete complexity string is needed for declare_variants!. The issue should cite a specific exact algorithm or explicitly state that the brute-force bound is the best known.

3. Schema section is well-structured: The field table, satisfaction problem designation, and notes about the |V| = 3q precondition are all clear and implementable.

4. Variables section is clear: The per-variable domain {0, ..., q-1} encoding is well-defined and the semantic meaning is unambiguous.

5. Examples are good: Both YES and NO instances are non-trivial, fully worked, and hand-verifiable. The NO instance was verified by exhaustive enumeration of all 10 possible partitions of 6 vertices into 2 triples — none yields 2+ edges in both triples. The YES instance clearly shows three valid P3 paths.

6. How to solve section is complete: All three solver methods (brute-force, ILP reduction, DP) are checked with brief descriptions.

Recommendations

• Verify and correct the GJ appendix code (should be a GT-series number, not "P10").
• Add a specific citation for the best known exact algorithm complexity, or explicitly note that the naive 3^n bound is the baseline.
• The Hadlock 1974 reference for the Bounded Component Spanning Forest reduction should be verified before implementing rule R31b.