[Rule] 3-PARTITION to INTERSECTION GRAPH FOR SEGMENTS ON A GRID #375
Description
Source: 3-PARTITION
Target: INTERSECTION GRAPH FOR SEGMENTS ON A GRID
Motivation: Skipped — source problem 3-Partition is a specialization of Partition (partition into triples with size constraints). Implement the general Partition model and reductions first.
Reference: Garey & Johnson, Computers and Intractability, ND46, p.219
Specialization Note
- 3-Partition is a restriction of Partition where elements must be grouped into triples, each summing to a target value.
- Neither Partition (P139) nor 3-Partition (P142) has a codebase implementation yet.
- Blocked on: Partition model implementation (P139), then 3-Partition (P142).