[Model] TwoDimensionalConsecutiveSets

[isPANN]

Motivation

2-DIMENSIONAL CONSECUTIVE SETS (P167) from Garey & Johnson, A4 SR19. An NP-complete problem from the domain of storage and retrieval. Given an alphabet and a collection of subsets, the question asks whether the alphabet can be partitioned into disjoint groups arranged in a sequence such that each subset is "covered" by consecutive groups with at most one element per group. This generalizes the consecutive sets problem to a two-dimensional arrangement.

Associated rules:

• R113: Graph 3-Colorability -> 2-Dimensional Consecutive Sets (as target)

Definition

Name: TwoDimensionalConsecutiveSets
Canonical name: 2-DIMENSIONAL CONSECUTIVE SETS
Reference: Garey & Johnson, Computers and Intractability, A4 SR19

Mathematical definition:

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}?

Variables

• Count: alphabet_size variables, one per symbol, each assigned to a group index.
• Per-variable domain: Each symbol is assigned to a group index in {0, ..., alphabet_size - 1} (at most alphabet_size groups).
• dims(): vec![alphabet_size; alphabet_size] — each of the alphabet_size symbols can be placed in any of up to alphabet_size groups.
• evaluate(): Given group assignments, build the partition X_1, ..., X_k (ignoring empty groups). Return true iff (1) each X_i intersects each subset Sigma_j in at most one element, and (2) each Sigma_j's elements are spread across exactly |Sigma_j| consecutive groups.

Schema (data type)

Type name: TwoDimensionalConsecutiveSets
Variants: None

Field	Type	Description
alphabet_size	usize	Size of the alphabet Sigma (elements are {0, ..., alphabet_size - 1})
subsets	Vec<Vec<usize>>	The collection C of subsets of Sigma

Size fields (getter methods for overhead expressions and declare_variants!):

• alphabet_size() — returns alphabet_size
• num_subsets() — returns subsets.len()

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Unlike ConsecutiveSets (SR18), there is no explicit bound K; the question is purely about the existence of a valid partition.
• The number of groups k is a decision variable bounded by alphabet_size (at most one element per group in the worst case).
• The partition into groups can be viewed as a 2D arrangement: the groups form one dimension (columns) and the elements within each group form the other dimension (rows).

Complexity

• Best known exact algorithm: O*(alphabet_size^alphabet_size) by trying all assignments of symbols to groups and checking the coverage and intersection constraints.
• NP-completeness: NP-complete [Lipski, 1977b]. Transformation from GRAPH 3-COLORABILITY.
• declare_variants! complexity string: "alphabet_size^alphabet_size"
• Restricted cases: Remains NP-complete if all Sigma_j in C have |Sigma_j| <= 5. Solvable in polynomial time if all Sigma_j in C have |Sigma_j| <= 2.
• References:
  • W. Lipski Jr. (1977). "One more polynomial complete consecutive retrieval problem." Information Processing Letters, 6(3):91-93.
  • W. Lipski Jr. (1977). "Two NP-complete problems related to information retrieval." Fundamentals of Computation Theory, FCT 1977, Lecture Notes in Computer Science, vol. 56, Springer.

Extra Remark

Full book text:

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 X1, X2, ..., Xk such that each Xi 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 Xl(j) union Xl(j)+1 union ... union Xl(j)+|Sigma_j|-1?
Reference: [Lipski, 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.

How to solve

• It can be solved by (existing) bruteforce -- enumerate all partitions of Sigma into ordered groups and verify the intersection and consecutiveness constraints.
• It can be solved by reducing to integer programming -- assign each symbol to a group index, add constraints for intersection bounds and consecutive coverage.
• Other: Constraint programming with propagation; reduction from/to graph coloring for small subset sizes.

Example Instance

Instance 1 (YES instance):
alphabet_size = 6 (symbols: {0, 1, 2, 3, 4, 5})
Subsets: C = [{0, 1, 2}, {3, 4, 5}, {1, 3}, {2, 4}, {0, 5}]

A naive partition into 3 groups X_1 = {0, 3}, X_2 = {1, 4}, X_3 = {2, 5} satisfies the intersection constraint (each group has at most 1 element per subset), but fails consecutiveness: {0, 5} has 0 in X_1 and 5 in X_3, which are not consecutive groups.

Partition into 4 groups: X_1 = {0}, X_2 = {1, 5}, X_3 = {2, 3}, X_4 = {4}.

Verification:

• {0, 1, 2}: 0 in X_1, 1 in X_2, 2 in X_3. Groups 1,2,3 consecutive. YES.
• {3, 4, 5}: 5 in X_2, 3 in X_3, 4 in X_4. Groups 2,3,4 consecutive. YES.
• {1, 3}: 1 in X_2, 3 in X_3. Groups 2,3 consecutive. YES.
• {2, 4}: 2 in X_3, 4 in X_4. Groups 3,4 consecutive. YES.
• {0, 5}: 0 in X_1, 5 in X_2. Groups 1,2 consecutive. YES.
  Answer: YES

Instance 2 (NO instance):
alphabet_size = 6 (symbols: {0, 1, 2, 3, 4, 5})
Subsets: C = [{0, 1, 2}, {0, 3, 4}, {0, 5, 1}, {2, 3, 5}]

Each size-3 subset requires 3 consecutive groups with exactly one element per group. Symbol 0 appears in three subsets ({0,1,2}, {0,3,4}, {0,5,1}), so the group containing 0 must be part of three overlapping triples of consecutive groups. For k=3 (minimum for size-3 subsets), all subsets span all 3 groups. From {0,1,2}: one of 0,1,2 in each group. From {0,5,1}: one of 0,5,1 in each group. If 0 is in X_i, then from {0,1,2}: 1 and 2 go to the other two groups; from {0,5,1}: 5 and 1 go to the other two groups. This forces 2 and 5 into the same group. But {2,3,5} then needs 2 and 5 in different groups — contradiction. Exhaustive search over k=1..6 confirms no valid partition exists.
Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem generalizing consecutive sets to 2D arrangement
Non-trivial	✅ Pass	Distinct from ConsecutiveSets -- partition into groups with intersection constraints
Correctness	✅ Pass	Both Lipski 1977 references verified; examples appear correct
Well-written	⚠️ Warn	NO instance proof is informal; schema uses Vec; minor issues

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

TwoDimensionalConsecutiveSets does not exist in the codebase. The problem is a genuine generalization of ConsecutiveSets (#421) -- instead of constructing a string, it asks for a partition of the alphabet into ordered groups with intersection and consecutiveness constraints. It has an associated reduction rule (R113: Graph 3-Colorability -> 2-Dimensional Consecutive Sets) and applications in information retrieval. Pass.

Non-trivial

The problem is genuinely distinct from all existing problems, including ConsecutiveSets. The two-dimensional aspect (partition into groups + ordering of groups) with the intersection constraint (each group has at most one element from each subset) creates a structurally different problem. This is not a trivial variant of any existing model. Pass.

Correctness

• Lipski Jr. (1977a): Confirmed. "One more polynomial complete consecutive retrieval problem," Information Processing Letters 6(3):91-93. Found in DBLP index.
• Lipski Jr. (1977b): Confirmed. "Two NP-complete problems related to information retrieval," FCT 1977, LNCS 56, Springer. Found on SpringerLink (DOI: 10.1007/3-540-08442-8_115).
• NP-completeness via Graph 3-Colorability: Consistent with the Garey & Johnson entry.
• Example 1 (YES): Verified. The partition X_1={a,d}, X_2={b,e}, X_3={c,f} satisfies all four subset consecutiveness and intersection constraints.
• Example 2 (NO): The claim appears correct -- symbol 'a' appearing in three size-3 subsets forces all other symbols into groups adjacent to a's group, creating conflicting constraints. However, the proof is informal.

Well-written

Strengths:

• Mathematical definition is precise and faithful to Garey & Johnson
• Variables section correctly describes the partition decision
• Schema is clean (no bound parameter needed)
• Example 1 is fully verified with clear step-by-step checking
• Extra Remark includes the restricted cases (NP-complete for |Sigma_j| <= 5, polynomial for |Sigma_j| <= 2)

Minor issues:

• Example 2 (NO instance) proof is hand-wavy: "forces conflicting group orderings" and "No valid partition exists" without rigorous case analysis. A more detailed argument would strengthen the issue.
• Schema uses Vec<char> instead of numeric indices, inconsistent with codebase conventions (same issue as ConsecutiveSets [Model] ConsecutiveSets #421).
• No concrete declare_variants! complexity string proposed.
• The Garey & Johnson reference says "[Lipsky, 1977b]" but the issue uses "Lipski" -- the correct spelling is "Lipski" (with an 'i'), matching the actual publications.

Recommendations

• Provide a rigorous proof for the NO instance, or replace it with a simpler example that has a clearer impossibility argument.
• Consider using numeric alphabet indices instead of Vec.

[isPANN]

Fix-issue changelog

• Replaced alphabet: Vec<usize> with alphabet_size: usize (redundant field)
• Added size fields section: alphabet_size(), num_subsets()
• Added declare_variants! complexity string: "alphabet_size^alphabet_size"
• Fixed brute-force complexity description
• Fixed author name typo: Lipsky → Lipski
• Added note that k (number of groups) is a decision variable bounded by alphabet_size
• Rewrote examples with numeric indices
• Replaced trivial YES example (k=3, all subsets span all groups) with non-trivial instance requiring k=4, showing a k=3 near-miss that satisfies intersection but fails consecutiveness
• Improved NO instance proof with concrete case analysis (2 and 5 forced into same group, contradicting {2,3,5})

Applied by /fix-issue.