[Model] PartitionIntoTriangles

[isPANN]

---

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

Motivation

PARTITION INTO TRIANGLES (P22) from Garey & Johnson, A1.1 GT11. A classical NP-complete problem central to proving hardness of graph partitioning and covering problems. Each part of the partition must form a complete triangle (K3), making this strictly harder than PARTITION INTO PATHS OF LENGTH 2 (which only requires 2 of 3 edges).

Associated reduction rules:

• As target: R19 (EXACT COVER BY 3-SETS -> PARTITION INTO TRIANGLES) via Garey and Johnson, 1979 (Theorem 3.7; transformation from 3DM)

Definition

Name: PartitionIntoTriangles
Canonical name: PARTITION INTO TRIANGLES
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT11

Mathematical definition:

INSTANCE: Graph G = (V,E), with |V| = 3q for some integer q.
QUESTION: Can the vertices of G be partitioned into q disjoint sets V_1, V_2, . . . , V_q, each containing exactly 3 vertices, such that for each V_i = {u_i, v_i, w_i}, 1 <= i <= q, all three of the edges {u_i,v_i}, {u_i,w_i}, and {v_i,w_i} belong to E?

Variables

• Count: n = |V| variables (one per vertex), encoding the triangle group assignment
• Per-variable domain: {0, 1, ..., q-1} where q = n/3 = |V|/3, indicating which triangle the vertex belongs to
• Meaning: Variable i = j means vertex i is in triangle group V_j. A valid assignment places exactly 3 vertices per group, and the 3 vertices must form a triangle (all 3 edges present in E).

Schema (data type)

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

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

Notes:

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

Complexity

• Best known exact algorithm:
  • General graphs: O(2^n * poly(n)) via inclusion-exclusion / subset DP.
  • Bounded degree 4: O(1.0222^n) time, linear space (van Rooij, van Kooten Niekerk, Bodlaender, 2013).
  • Bounded degree 3: polynomial time (linear-time algorithm exists).
• declare_variants! complexity string: "2^num_vertices" (general brute-force bound)
• NP-completeness: NP-complete (Garey and Johnson, 1979; transformation from 3-Dimensional Matching, Theorem 3.7). Remains NP-complete on graphs of maximum degree 4.
• ETH lower bound: No subexponential-time algorithm on degree-4 graphs unless the Exponential-Time Hypothesis fails.
• References:
  • M. R. Garey and D. S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. GT11, Theorem 3.7.
  • J. M. M. van Rooij, M. van Kooten Niekerk, H. L. Bodlaender (2013). "Partition Into Triangles on Bounded Degree Graphs." Theory of Computing Systems 52(4), pp. 687–718.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), with |V| = 3q for some integer q.
QUESTION: Can the vertices of G be partitioned into q disjoint sets V_1, V_2, . . . , V_q, each containing exactly 3 vertices, such that for each V_i = {u_i, v_i, w_i}, 1 <= i <= q, all three of the edges {u_i,v_i}, {u_i,w_i}, and {v_i,w_i} belong to E?
Reference: [Schaefer, 1974]. Transformation from 3DM (see Chapter 3).
Comment: See next problem for a generalization.

How to solve

• It can be solved by (existing) bruteforce — enumerate all partitions of V into triples and check the triangle condition.
• It can be solved by reducing to integer programming — binary variables x_{v,t} for vertex v in triangle t, constraints enforcing exactly 3 vertices per triangle and all 3 edges present.
• Other: Subset DP in O(3^n * poly(n)); for degree-4 graphs, O(1.0222^n) exact algorithm.

Example Instance

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

• Edges: {0,1}, {0,2}, {1,2}, {3,4}, {3,5}, {4,5}, {6,7}, {6,8}, {7,8}, {0,3}, {2,6}, {4,7}
• q = 3, so we need 3 triangles covering all vertices
• Partition: V_1 = {0, 1, 2}, V_2 = {3, 4, 5}, V_3 = {6, 7, 8}
  • V_1: {0,1}, {0,2}, {1,2} all present -- triangle
  • V_2: {3,4}, {3,5}, {4,5} all present -- triangle
  • V_3: {6,7}, {6,8}, {7,8} all present -- triangle
• Answer: YES

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

• Edges: {0,1}, {0,2}, {1,2}, {2,3}, {3,4}, {4,5}
• q = 2, so we need 2 triangles covering all 6 vertices
• Triangles present: only {0,1,2}
• Remaining vertices {3,4,5}: edges {2,3}, {3,4}, {4,5} are present but {3,5} is missing, so {3,4,5} is not a triangle
• No valid triangle partition exists
• Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in the reduction graph; connects to Exact Cover and Graph Partitioning
Non-trivial	✅ Pass	Distinct satisfaction problem — partitioning into triangles is not equivalent to any existing model
Correctness	⚠️ Warn	Minor reference inaccuracies (see details below)
Well-written	⚠️ Warn	Example 2 has a self-correction mid-stream; a few notation issues (see details)

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. PartitionIntoTriangles does not exist in the codebase (confirmed via pred show). The problem is a classical NP-complete problem (GT11 in Garey & Johnson) and occupies a natural position in the reduction graph: it can serve as a target from Exact Cover by 3-Sets (X3C) and as a source toward graph partitioning problems. The motivation correctly identifies its role in hardness proofs.

Non-trivial

Pass. The feasibility constraint (partition vertices into disjoint triples, each forming a triangle K3) is genuinely distinct from all 24 existing problems. It is not a variant of any existing model — it is a satisfaction (decision) problem on graphs with a unique structural requirement.

Correctness

Warn. Several minor inaccuracies found:

1. Schaefer reference year: The issue cites "Schaefer, 1974" as the NP-completeness reference. Thomas J. Schaefer's well-known paper "The complexity of satisfiability problems" was published at STOC 1978, not 1974. Moreover, that paper is about SAT dichotomy, not Partition Into Triangles directly. The Garey & Johnson book (1979) lists the NP-completeness of GT11 (Partition Into Triangles) as a "Transformation from 3DM (see Chapter 3)" — this is Garey & Johnson's own reduction, not Schaefer's. The reference should be corrected accordingly.

2. van Rooij et al. journal volume: The issue says "Theory of Computing Systems 51, pp. 687–718." The actual publication is Theory of Computing Systems 52(4), pp. 687–718, 2013 (the conference version appeared at SOFSEM 2011, LNCS 6543, pp. 558–569). The year "2011" in the issue refers to the conference version, not the journal version.

3. Complexity claims are correct in substance: The O(1.0222^n) bound for degree-4 graphs, polynomial time for degree-3 graphs, and ETH lower bound are all confirmed by the van Rooij et al. paper. The general-case O(2^n * poly(n)) via inclusion-exclusion is standard.

4. Associated reductions: The issue mentions "Hyafil and Rivest, 1973" for PARTITION INTO TRIANGLES → GRAPH PARTITIONING. This reference could not be independently verified. Hyafil and Rivest (1973) published "Graph Partitioning and Constructing Optimal Decision Trees are NP-Complete Problems" — which is about decision trees, not graph partitioning from triangle partition. This should be verified.

Well-written

Warn. The issue is generally well-structured and covers all required sections. Specific items to improve:

1. Example 2 has a false start: The text first constructs a 7-edge graph, discovers it actually has a valid partition, then says "Wait -- let's make it harder" and revises the example mid-stream. The final NO instance (6 vertices, 6 edges: {0,1}, {0,2}, {1,2}, {2,3}, {3,4}, {4,5}) is correct, but the self-correction should be cleaned up for clarity.

2. Symbol q usage: q is used in both the definition (|V| = 3q) and the variable domain ({0, 1, ..., q-1}), which is consistent. However, the Variables section says "n = |V| variables" and then the domain is {0, ..., q-1}, but never explicitly says q = n/3 in that section.

3. Naming convention: The name PartitionIntoTriangles does not follow the existing naming patterns in the codebase (which use optimization prefixes like Maximum/Minimum or short names like MaxCut). Since this is a satisfaction problem without an optimization prefix, the name is acceptable — similar to Satisfiability, Factoring, etc.

4. Schema is adequate: Single graph field with SimpleGraph type, satisfaction problem with Metric = bool — this is correct and follows the codebase patterns.

5. How to solve section is good: All three solver methods are checked, which is thorough.

Recommendations

• Fix the Schaefer reference: cite Garey & Johnson (1979) directly for the NP-completeness of GT11, or cite the original 3DM reduction.
• Correct the van Rooij et al. citation to volume 52, year 2013 for the journal version (or explicitly note "SOFSEM 2011" for the conference version).
• Clean up Example 2 to remove the mid-stream self-correction — just present the final NO instance directly.
• Verify the "Hyafil and Rivest, 1973" claim for the PARTITION INTO TRIANGLES → GRAPH PARTITIONING reduction.