[Rule] Graph 3-Colorability to 2-Dimensional Consecutive Sets

[isPANN]

Source: Graph 3-Colorability
Target: 2-Dimensional Consecutive Sets
Motivation: Establishes NP-completeness of 2-DIMENSIONAL CONSECUTIVE SETS via polynomial-time reduction from GRAPH 3-COLORABILITY. The reduction encodes a graph coloring problem as a partition problem on an alphabet: each edge of the graph becomes a size-3 subset containing the two endpoint symbols plus a unique dummy symbol, and finding a valid 3-coloring corresponds to partitioning the alphabet into 3 groups where each edge-subset spans exactly 3 consecutive groups with exactly one element per group.

Reference: Garey & Johnson, Computers and Intractability, Appendix A4.2, p.230

GJ Source Entry

[SR19] 2-DIMENSIONAL CONSECUTIVE SETS
INSTANCE: Finite alphabet Sigma, collection C = {Sigma_1, Sigma_2, ..., Sigma_n} of subsets of Sigma.
QUESTION: Is there a partition of Sigma into disjoint sets X_1, X_2, ..., X_k such that each X_i has at most one element in common with each Sigma_j and such that, for each Sigma_j in C, there is an index l(j) such that Sigma_j is contained in

X_{l(j)} union X_{l(j)+1} union ... union X_{l(j)+|Sigma_j|-1} ?

Reference: [Lipsky, 1977b]. Transformation from GRAPH 3-COLORABILITY.
Comment: Remains NP-complete if all Sigma_j in C have |Sigma_j| <= 5, but is solvable in polynomial time if all Sigma_j in C have |Sigma_j| <= 2.

Reduction Algorithm

Summary:
Given a GRAPH 3-COLORABILITY instance G = (V, E) with |V| = n and |E| = m, construct a 2-DIMENSIONAL CONSECUTIVE SETS instance as follows:

1. Alphabet construction: Use one symbol per vertex plus one unique dummy symbol per edge:

   • For each vertex v in V, include symbol v.
   • For each edge e = {u, v} in E, include a fresh dummy symbol d_e.
   • Total alphabet: Sigma = V union {d_e : e in E}, with |Sigma| = n + m.

2. Subset construction: For each edge e = {u, v} in E, define:
   Sigma_e = {u, v, d_e}
   This is a subset of size 3. The collection C = {Sigma_e : e in E} has |C| = m subsets.

3. Intended partition: The 3-coloring chi: V -> {1, 2, 3} yields a partition into k = 3 groups:

   • X_c = {v in V : chi(v) = c} for c in {1, 2, 3}.
   • For each edge e = {u, v}, assign dummy d_e to the unique color c* in {1,2,3} \ {chi(u), chi(v)} (which exists because chi(u) != chi(v)).
   • Each Sigma_e = {u, v, d_e} then has its three elements in three distinct groups, which are exactly {X_{chi(u)}, X_{chi(v)}, X_{c*}} = {X_1, X_2, X_3}, all consecutive.

Correctness (forward): A valid 3-coloring chi places u and v in different groups, and the dummy d_e in the unique third group. So {u, v, d_e} spans all 3 groups consecutively, with one element per group.

Correctness (reverse): If a valid partition into k groups exists with the consecutiveness property, then for each edge subset {u, v, d_e} of size 3, the three elements must be in 3 distinct consecutive groups. In particular, u and v are in different groups. Mapping groups to colors gives a valid 3-coloring.

Time complexity of reduction: O(|V| + |E|) to construct the alphabet and subsets.

Size Overhead

Symbols:

• n = num_vertices of source Graph 3-Colorability instance (|V|)
• m = num_edges of source Graph 3-Colorability instance (|E|)

Target metric (code name)	Polynomial (using symbols above)
alphabet_size	num_vertices + num_edges
num_subsets	num_edges

Derivation: The alphabet has n vertex symbols plus m dummy symbols (one per edge), totaling n + m. Each edge produces exactly one subset of size 3, so there are m subsets in total. The GJ comment says the problem remains NP-complete for subsets of size <= 5, consistent with this construction using size-3 subsets.

Validation Method

• Closed-loop test: reduce a Graph3Colorability (KColoring with k=3) instance to TwoDimensionalConsecutiveSets, solve target with BruteForce, extract solution, verify on source.
• Test with known 3-colorable graph: K_3 (triangle) is 3-colorable. The 3 vertex symbols + 3 dummy symbols should admit a valid partition into 3 groups.
• Test with known non-3-colorable graph: K_4 (complete graph on 4 vertices) is not 3-colorable. Verify no valid partition exists.
• Test with bipartite graph (2-colorable, hence also 3-colorable): verify the partition works.
• Edge case: empty graph (always 3-colorable).

Example

Source instance (Graph 3-Colorability):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 7 edges:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {0,5}, {1,4}
• (This is a cycle C_6 plus a chord {1,4})
• 3-coloring: chi(0)=1, chi(1)=2, chi(2)=1, chi(3)=2, chi(4)=3, chi(5)=2

Verify: {0,1}: 1!=2 Y, {1,2}: 2!=1 Y, {2,3}: 1!=2 Y, {3,4}: 2!=3 Y, {4,5}: 3!=2 Y, {0,5}: 1!=2 Y, {1,4}: 2!=3 Y. Valid.

Constructed target instance (TwoDimensionalConsecutiveSets):
Alphabet: Sigma = {0, 1, 2, 3, 4, 5, d01, d12, d23, d34, d45, d05, d14} (13 symbols)
Subsets:

• Sigma_{0,1} = {0, 1, d01}
• Sigma_{1,2} = {1, 2, d12}
• Sigma_{2,3} = {2, 3, d23}
• Sigma_{3,4} = {3, 4, d34}
• Sigma_{4,5} = {4, 5, d45}
• Sigma_{0,5} = {0, 5, d05}
• Sigma_{1,4} = {1, 4, d14}

Solution mapping:
From the 3-coloring chi (color 1 -> group X_1, color 2 -> group X_2, color 3 -> group X_3):

• Vertices: 0 -> X_1, 1 -> X_2, 2 -> X_1, 3 -> X_2, 4 -> X_3, 5 -> X_2
• Dummies: each d_e goes to the unique third color not used by the edge endpoints:
  • d01: colors {1,2} used, d01 -> X_3
  • d12: colors {2,1} used, d12 -> X_3
  • d23: colors {1,2} used, d23 -> X_3
  • d34: colors {2,3} used, d34 -> X_1
  • d45: colors {3,2} used, d45 -> X_1
  • d05: colors {1,2} used, d05 -> X_3
  • d14: colors {2,3} used, d14 -> X_1

Final partition:

• X_1 = {0, 2, d34, d45, d14}
• X_2 = {1, 3, 5}
• X_3 = {4, d01, d12, d23, d05}

Verification:
Each size-3 subset spans groups 1, 2, 3 (all consecutive) with exactly one element per group:

• {0, 1, d01}: 0 in X_1, 1 in X_2, d01 in X_3. Spans X_1, X_2, X_3. YES.
• {1, 2, d12}: 1 in X_2, 2 in X_1, d12 in X_3. Spans X_1, X_2, X_3. YES.
• {2, 3, d23}: 2 in X_1, 3 in X_2, d23 in X_3. Spans X_1, X_2, X_3. YES.
• {3, 4, d34}: 3 in X_2, 4 in X_3, d34 in X_1. Spans X_1, X_2, X_3. YES.
• {4, 5, d45}: 4 in X_3, 5 in X_2, d45 in X_1. Spans X_1, X_2, X_3. YES.
• {0, 5, d05}: 0 in X_1, 5 in X_2, d05 in X_3. Spans X_1, X_2, X_3. YES.
• {1, 4, d14}: 1 in X_2, 4 in X_3, d14 in X_1. Spans X_1, X_2, X_3. YES.

References

• [Lipsky, 1977b]: [Lipsky1977b] William Lipsky, Jr (1977). "One more polynomial complete consecutive retrieval problem". Information Processing Letters 6, pp. 91-93.