[Rule] Permutation Generation to MinimumRegisterSufficiencyForLoops

[isPANN]

Source: Permutation Generation
Target: REGISTER SUFFICIENCY FOR LOOPS

Motivation: Establishes NP-completeness of Register Sufficiency for Loops, which is equivalent to circular arc graph coloring — assigning colors to arcs on a circle so no two overlapping arcs share a color. This is a fundamental problem in compiler optimization (loop register allocation) and connects to interval scheduling, graph coloring, and circular arc graph theory. Solvable in polynomial time for any fixed K.

Reference: Garey & Johnson, Computers and Intractability, A11 PO3

GJ Source Entry

[PO3] REGISTER SUFFICIENCY FOR LOOPS
INSTANCE: Set V of loop variables, a loop length N ∈ Z+, for each variable v ∈ V a start time s(v) ∈ Z₀+ and a duration l(v) ∈ Z+, and a positive integer K.
QUESTION: Can the loop variables be safely stored in K registers, i.e., is there an assignment f: V → {1,2,...,K} such that if f(v) = f(u) for some u ≠ v ∈ V, then s(u) ≤ s(v) implies s(u) + l(u) ≤ s(v) and s(v) + l(v) (mod N) ≤ s(u)?
Reference: [Garey, Johnson, Miller, and Papadimitriou, 1978]. Transformation from permutation generation.
Comment: Solvable in polynomial time for any fixed K.

Reduction Algorithm

Reference: [Garey, Johnson, Miller, and Papadimitriou, 1978]. Transformation from permutation generation.

Summary:
The problem is equivalent to coloring a circular arc graph: each loop variable v defines an arc on a circle of circumference N, from position s(v) to position (s(v) + l(v)) mod N. Two variables conflict (cannot share a register) iff their arcs overlap. The question is: can the arcs be colored with ≤ K colors?

The reduction is from permutation generation (determining if a given permutation can be generated by a specific mechanism) to circular arc graph coloring. The construction maps the permutation structure onto arc intervals such that the chromatic number of the resulting circular arc graph equals the answer to the permutation generation problem.

Solution extraction: The coloring f: V → {1,...,K} directly gives the register assignment.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_variables	|V| (number of loop variables = number of arcs)
loop_length	N (circle circumference)
threshold	K

Validation Method

• Closed-loop test: construct circular arc graph, solve coloring with BruteForce, verify no two overlapping arcs share a color
• Verify that max clique size ≤ K (necessary condition: chromatic number ≥ clique number)
• Test with instances where chromatic number > clique number (this can happen for circular arc graphs, unlike interval graphs)
• Test edge case: fixed K (polynomial-time solvable)

Example

Source instance (Register Sufficiency for Loops):
Loop length: N = 12
Variables with (start time, duration):

• v₁: s=0, l=5 → arc [0, 5)
• v₂: s=3, l=4 → arc [3, 7)
• v₃: s=6, l=5 → arc [6, 11)
• v₄: s=9, l=6 → arc [9, 3) (wraps around: 9→12→3)
• v₅: s=1, l=3 → arc [1, 4)
• v₆: s=7, l=3 → arc [7, 10)

Conflict graph (overlapping arcs):

• v₁ overlaps v₂ (0–5 ∩ 3–7), v₅ (0–5 ∩ 1–4), v₄ (wraps: 9–3 ∩ 0–5)
• v₂ overlaps v₁, v₅ (3–7 ∩ 1–4), v₃ (3–7 ∩ 6–11)
• v₃ overlaps v₂, v₆ (6–11 ∩ 7–10), v₄ (6–11 ∩ 9–3)
• v₄ overlaps v₁, v₃, v₆ (wraps: 9–3 ∩ 7–10)
• v₅ overlaps v₁, v₂
• v₆ overlaps v₃, v₄

Register assignment with K=3:

• f(v₁) = 1, f(v₂) = 2, f(v₃) = 1, f(v₄) = 2, f(v₅) = 3, f(v₆) = 3

Verification:

• v₁(1) and v₂(2): overlap, different registers ✓
• v₁(1) and v₅(3): overlap, different registers ✓
• v₁(1) and v₄(2): overlap, different registers ✓
• v₂(2) and v₅(3): overlap, different registers ✓
• v₂(2) and v₃(1): overlap, different registers ✓
• v₃(1) and v₆(3): overlap, different registers ✓
• v₃(1) and v₄(2): overlap, different registers ✓
• v₄(2) and v₆(3): overlap, different registers ✓

K=3 suffices. Maximum clique size is 3 (e.g., {v₁, v₂, v₅} all mutually overlap at position 3), so K=2 is impossible.

Why it's non-trivial: The wrap-around (v₄) creates circular dependencies that prevent a simple left-to-right greedy coloring. Unlike interval graphs (where chromatic number = clique number), circular arc graphs can require more colors than the maximum clique size.

References

• [Garey, Johnson, Miller, and Papadimitriou, 1978]: [Garey1978c] M. R. Garey and D. S. Johnson and G. L. Miller and C. H. Papadimitriou (1978). "Unpublished results".