[Model] CyclicOrdering

[isPANN]

Motivation

CYCLIC ORDERING (MS2) from Garey & Johnson, A1.2. Given a set A and a collection of ordered triples, determine whether there is a one-to-one mapping f: A → {1,...,|A|} that respects all cyclic order constraints. NP-complete (Galil and Megiddo 1977). The problem captures cyclic sequencing constraints arising in scheduling on circular resources, DNA physical mapping, and circular genome assembly.

Associated rules:

• [Rule] 3-Satisfiability to Cyclic Ordering #918: 3-Satisfiability → CyclicOrdering (this model is the target; original NP-completeness proof)

Definition

Name: CyclicOrdering
Reference: Garey & Johnson, Computers and Intractability, A1.2 MS2; Galil and Megiddo 1977

Mathematical definition:

INSTANCE: Finite set A, collection C of ordered triples (a, b, c) of distinct elements from A.
QUESTION: Is there a one-to-one function f: A → {1, 2, ..., |A|} such that, for each ordered triple (a, b, c) ∈ C, we have either f(a) < f(b) < f(c), or f(b) < f(c) < f(a), or f(c) < f(a) < f(b)? (That is, a, b, c appear in this cyclic order under f.)

Variables

• Count: |A| (one per element)
• Per-variable domain: {1, 2, ..., |A|} (a permutation)
• Meaning: The position assigned to each element in the cyclic sequence. The assignment must be a permutation, and every ordered triple constraint must be satisfied cyclically.

Schema (data type)

Type name: CyclicOrdering
Variants: none (unique input structure)

Field	Type	Description
num_elements	usize	Number of elements
triples	Vec<(usize, usize, usize)>	Ordered triples (a, b, c) encoding cyclic order constraints

Getter methods: num_elements(), num_triples() (= triples.len())

Complexity

• Best known exact algorithm: The problem is NP-complete [Galil and Megiddo, 1977]. For the general case, no algorithm faster than brute-force permutation enumeration is known: enumerate all |A|! permutations and check each triple in O(|C|) time, giving O(|A|! · |C|) total. For special cases (e.g., when the constraint structure forms an interval graph on the cyclic order), polynomial algorithms exist.
• declare_variants! complexity string: "factorial(num_elements)"

Extra Remark

Full book text:

INSTANCE: Finite set A, collection C of ordered triples (a, b, c) of distinct elements from A.
QUESTION: Is there a one-to-one function f: A → {1, 2, ..., |A|} such that for each ordered triple (a, b, c) ∈ C, either f(a) < f(b) < f(c), or f(b) < f(c) < f(a), or f(c) < f(a) < f(b)?

Reference: [Galil and Megiddo, 1977]. Transformation from 3-SATISFIABILITY.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all |A|! permutations; check each triple constraint in O(|C|) time.)
• It can be solved by reducing to integer programming. (Binary ILP: x_{i,p} ∈ {0,1} indicating element i is at position p, with assignment and cyclic ordering constraints.)
• Other:

Example Instance

YES Instance:

A = {0, 1, 2, 3, 4} (5 elements, indexed 0..4).
Triples: C = {(0, 1, 2), (2, 3, 0), (1, 3, 4)}.

Expected Outcome: YES with f(0)=2, f(1)=4, f(2)=5, f(3)=1, f(4)=3.

Verification of each triple:

• (0, 1, 2): f(0)=2 < f(1)=4 < f(2)=5 [direct order] ✓
• (2, 3, 0): f(3)=1 < f(0)=2 < f(2)=5, i.e., f(b) < f(c) < f(a) [wrap-around] ✓
• (1, 3, 4): f(3)=1 < f(4)=3 < f(1)=4, i.e., f(b) < f(c) < f(a) [wrap-around] ✓

Note: The triple (2, 3, 0) forces a wrap-around condition — element 0 has a smaller position than element 2, so the cyclic order wraps past |A|. Out of 120 total permutations, exactly 10 satisfy all three constraints.

NO Instance:

A = {0, 1, 2, 3, 4} (5 elements).
Triples: C = {(0, 1, 2), (2, 1, 0), (1, 3, 4)}.

Expected Outcome: NO.

The triples (0, 1, 2) and (2, 1, 0) demand opposite cyclic orientations of elements 0, 1, 2: the first requires the cyclic order 0→1→2, while the second requires 2→1→0. These are contradictory regardless of the positions of elements 3 and 4. Brute-force confirms 0 out of 120 permutations satisfy all constraints.

Validation script

from itertools import permutations

def check_cyclic_order(f, a, b, c):
    fa, fb, fc = f[a], f[b], f[c]
    return (fa < fb < fc) or (fb < fc < fa) or (fc < fa < fb)

def solve(num_elements, triples):
    solutions = []
    for perm in permutations(range(num_elements)):
        f = {i: perm[i] + 1 for i in range(num_elements)}
        if all(check_cyclic_order(f, a, b, c) for a, b, c in triples):
            solutions.append(tuple(perm[i] + 1 for i in range(num_elements)))
    return solutions

# YES instance
sols = solve(5, [(0, 1, 2), (2, 3, 0), (1, 3, 4)])
assert len(sols) == 10
assert (2, 4, 5, 1, 3) in sols

# NO instance
sols_no = solve(5, [(0, 1, 2), (2, 1, 0), (1, 3, 4)])
assert len(sols_no) == 0

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction connecting CyclicOrdering to any existing problem
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	✅ Pass	Galil & Megiddo 1977 reference verified; NP-completeness claim correct
Well-written	❌ Fail	Missing Expected Outcome section; example too trivial

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

The issue does not mention any planned reduction rule connecting CyclicOrdering to or from an existing problem in the reduction graph. The "How to solve" section only checks brute-force, and there is no "Reduction Rule Crossref" section. Without at least one concrete reduction (e.g., CyclicOrdering from 3-SAT, as Galil & Megiddo's original proof uses), this problem would be an orphan node with no value in the reduction graph.

Required fix: Add at least one planned reduction to/from an existing problem. The original NP-completeness proof uses a transformation from 3-SATISFIABILITY, which would be a natural candidate.

Non-trivial

CyclicOrdering is a genuinely distinct problem. Its feasibility constraints involve cyclic ordering of triples over a permutation — this structure does not match any existing problem in the codebase. The problem is well-established in the literature (Garey & Johnson A1.2 MS2) and captures a fundamentally different combinatorial structure from linear ordering or graph problems already present.

Correctness

Reference verification:

• Galil and Megiddo 1977: Verified. "Cyclic Ordering is NP-Complete," Theoretical Computer Science, Vol. 5, No. 2, pp. 179–182, 1977. The paper proves NP-completeness via reduction from 3-SAT. Available at ScienceDirect and Stanford.
• Garey & Johnson A1.2 MS2: Consistent with the book's classification of Cyclic Ordering as NP-complete.

Complexity string: factorial(num_elements) is acceptable as a brute-force bound (enumerate all permutations). No known faster exact algorithm has been identified in the literature for the general case, so this is a reasonable default.

Definition correctness: The mathematical definition is well-formed. The cyclic order condition (three possible inequalities) correctly captures the standard definition.

Well-written

Failures:

1. Missing Expected Outcome section. The template requires a concrete valid/satisfying solution with justification for satisfaction problems. The YES example shows f = (1, 2, 3, 4) works, but there is no dedicated "Expected Outcome" section with structured presentation.

2. Example too trivial for round-trip testing. The YES example (A = {0,1,2,3}, C = {(0,1,2), (1,2,3)}, solution f = (1,2,3,4)) is the identity permutation applied to trivially ordered triples. Every triple is already in linear order, so the cyclic constraint is never exercised in its non-trivial form (i.e., the wrap-around cases f(b) < f(c) < f(a) or f(c) < f(a) < f(b) are never triggered). A better example should include triples that force the wrap-around condition, giving multiple feasible permutations with at least 2–3 additional non-optimal or invalid configurations to catch implementation bugs.

3. NO example uses only 3 elements. With |A| = 3 there are only 6 permutations — too small to meaningfully test. Consider a 5+ element instance with conflicting constraints.

Passes:

• All other template sections (Motivation, Definition, Variables, Schema, Complexity, How to solve) are present and substantive.
• Symbol usage is consistent between sections.
• The schema design (num_elements + triples) is reasonable and implementable.

Recommendations

• Add a planned [Rule] Satisfiability to CyclicOrdering or [Rule] KSatisfiability to CyclicOrdering issue reference, mirroring the original Galil & Megiddo reduction from 3-SAT.
• Improve the YES example to use 5+ elements with triples that exercise wrap-around cyclic ordering (e.g., a triple (c, d, a) where f(c) > f(d) but the assignment wraps cyclically).
• Add a dedicated Expected Outcome section: "YES with f = (...), verified by checking each triple."
• Consider whether an ILP formulation is feasible (binary assignment variables x_{i,p} with cyclic ordering constraints); if so, add a companion [Rule] CyclicOrdering to ILP issue.

[isPANN]

Changelog (fix-issue)

Fixes applied:

1. Usefulness — added rule crossref: Linked [Rule] 3-Satisfiability to Cyclic Ordering #918 (3-Satisfiability → CyclicOrdering) in a new "Associated rules" section, matching the original Galil & Megiddo NP-completeness proof.

2. Well-written — improved example to 5 elements with wrap-around: Replaced the trivial 4-element identity-permutation example with a 5-element instance (A = {0..4}, C = {(0,1,2), (2,3,0), (1,3,4)}) where two out of three triples exercise the wrap-around cyclic ordering condition (f(b) < f(c) < f(a)). Exactly 10 of 120 permutations are valid — enough non-trivial structure to catch implementation bugs.

3. Well-written — added Expected Outcome section: Both YES and NO instances now have explicit expected outcomes with step-by-step verification of each triple.

4. Well-written — upgraded NO instance to 5 elements: Replaced the 3-element NO example with a 5-element instance using contradictory triples (0,1,2) and (2,1,0) plus a third triple (1,3,4). Brute-force confirms 0/120 permutations satisfy all constraints.

5. Schema — added getter methods: Added num_elements() and num_triples() getter documentation.

6. Complexity — clarified declare_variants! string: Made the declare_variants! complexity string explicit: "factorial(num_elements)".

7. Validation — added Python script: Embedded a validation script confirming both YES (10 solutions) and NO (0 solutions) instances.

All examples verified with Python brute-force enumeration.