[Model] Betweenness

[isPANN]

Motivation

BETWEENNESS (P313) from Garey & Johnson, A12 MS1. A classical NP-complete problem in order theory, asking whether a set of elements can be linearly ordered so that specified betweenness constraints are satisfied. Has applications in computational biology (gene mapping).

Associated rules:

• [Rule] SET SPLITTING to BETWEENNESS #842: SetSplitting → Betweenness (NP-completeness proof, Opatrný 1979)

Definition

Name: Betweenness
Reference: Garey & Johnson, Computers and Intractability, A12 MS1

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 (a,b,c) ∈ C, we have either f(a) < f(b) < f(c) or f(c) < f(b) < f(a)?

Variables

• Count: |A| (one variable per element, representing its position in the linear order)
• Per-variable domain: {0, 1, ..., |A|-1} — a permutation of positions
• Meaning: x_i = k means element a_i is placed at position k in the linear order. The assignment must be a permutation (all positions distinct). For each triple (a, b, c) ∈ C, element b must appear between a and c in the ordering.

Schema (data type)

Type name: Betweenness
Variants: none

Field	Type	Description
num_elements	usize	Number of elements in the finite set A
triples	Vec<(usize, usize, usize)>	Collection C of ordered triples (a, b, c) where b must be between a and c; elements are 0-based indices

Notes:

• This is a feasibility (decision) problem: Value = Or.
• Key getter methods: num_elements() (= |A|), num_triples() (= |C|).

Complexity

• Decision complexity: NP-complete (Opatrný, 1979; transformation from SET SPLITTING). The related optimization problem (maximize satisfied triples) is MAX-SNP-hard (Chor & Sudan, 1998).
• Best known exact algorithm: As a Permutation CSP of arity 3, solvable by Held-Karp style DP in O*(2^n) time and space. Naive approach: O(n!) by enumerating all permutations.
• Concrete complexity expression: "2^num_elements" (for declare_variants!)
• References:
  • J. Opatrný (1979). "Total Ordering Problem." SIAM J. Comput. 8(1), pp. 111-114.
  • B. Chor, M. Sudan (1998). "A Geometric Approach to Betweenness." SIAM J. Discrete Math. 11(4), pp. 511-523.

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 (a,b,c) ∈ C, we have either f(a) < f(b) < f(c) or f(c) < f(b) < f(a)?
Reference: [Opatrný, 1978]. Transformation from SET SPLITTING.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all |A|! permutations; for each, check that all betweenness triples are satisfied.)
• It can be solved by reducing to integer programming. (Integer variables p_i ∈ {1,...,n} for positions, all-different constraints, and for each triple (a,b,c): introduce binary indicator to select between f(a)<f(b)<f(c) or f(c)<f(b)<f(a). Companion rule issue to be filed separately.)
• Other:

Example Instance

Input:
A = {0, 1, 2, 3, 4} (5 elements)
C = {(0,1,2), (2,3,4), (0,2,4), (1,3,4)} — "b is between a and c"

Satisfying ordering: f = [0→0, 1→1, 2→2, 3→3, 4→4] (identity permutation):

• (0,1,2): f(0)=0 < f(1)=1 < f(2)=2 ✓
• (2,3,4): f(2)=2 < f(3)=3 < f(4)=4 ✓
• (0,2,4): f(0)=0 < f(2)=2 < f(4)=4 ✓
• (1,3,4): f(1)=1 < f(3)=3 < f(4)=4 ✓

Answer: YES — 2 valid orderings out of 120 (identity and reverse).

Non-satisfying ordering: f = [0→0, 1→2, 2→1, 3→3, 4→4]:

• (0,1,2): f(0)=0 < f(1)=2 > f(2)=1, but f(2)=1 < f(1)=2 < f(0)=0 is false → 1 not between 0 and 2 ✗

Python validation script

from itertools import permutations

triples = [(0,1,2), (2,3,4), (0,2,4), (1,3,4)]
count = 0
for perm in permutations(range(5)):
    f = {i: perm[i] for i in range(5)}
    if all((f[a]<f[b]<f[c]) or (f[c]<f[b]<f[a]) for a,b,c in triples):
        count += 1

assert count == 2  # identity and reverse
print(f"Valid orderings: {count}/120")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; planned reduction from SetSplitting
Non-trivial	✅ Pass	Distinct feasibility constraints (betweenness triples on permutations)
Correctness	⚠️ Warn	Year inconsistency for Opatrný reference; complexity attribution is vague
Well-written	⚠️ Warn	Missing concrete complexity expression; ILP companion issue not linked

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. The problem Betweenness does not exist in the codebase (pred show Betweenness fails). The issue identifies a planned reduction path: "As target: R229 (SetSplitting →)", providing a concrete connection to the reduction graph. The motivation references Garey & Johnson A12 MS1 and mentions applications in computational biology (gene mapping). Note that SetSplitting also does not yet exist in the codebase, so both the source model and the reduction rule would need to be implemented for this problem to become connected.

The issue checks both brute-force and ILP as solver methods, which is good. However, since ILP solving is claimed, a companion [Rule] Betweenness to ILP issue should be linked (see Well-written check below).

Non-trivial

Pass. Betweenness has a genuinely distinct feasibility constraint: finding a permutation (total ordering) of elements such that specified betweenness triples are all satisfied. This is not isomorphic to any existing problem in the codebase. The closest existing problem is PartiallyOrderedKnapsack, which has a fundamentally different structure (optimization over a partial order, not feasibility of betweenness constraints).

Correctness

Warn — year inconsistency and vague complexity attribution.

References verified:

• Opatrný (1979): The paper "Total ordering problem" by Jaroslav Opatrný does exist and establishes NP-completeness of the Betweenness problem. However, the issue is inconsistent: the Complexity section says "Opatrný, 1979" while the "Full book text" section says "Opatrný, 1978". Garey & Johnson cite it as 1979. This should be made consistent.
• Chor & Sudan (1998): Verified. "A geometric approach to betweenness" appeared in SIAM Journal on Discrete Mathematics, vol. 11, no. 4, pp. 511–523, 1998. The MAX-SNP-hardness claim is correct.
• Held-Karp style O*(2^n) DP: Verified. Betweenness is a Permutation CSP of arity 3, and arity ≤ 3 Permutation CSPs can be solved in O*(2^n) time via Held-Karp-type dynamic programming. This was established by Koivisto & Parviainen (2012), "On Exact Algorithms for Permutation CSP" (Theoretical Computer Science, vol. 511, pp. 37–55, 2013). The issue vaguely attributes this to "Opatrný, 1979; see also Permutation CSP results" — Opatrný's paper proves NP-completeness, not the O*(2^n) algorithm. The attribution should be corrected to cite the actual Permutation CSP DP result.

Definition correctness: The formal definition is mathematically well-formed and matches the standard Betweenness problem from Garey & Johnson.

Example verification: I verified the example instance by exhaustive enumeration. The instance with A = {0,1,2,3,4} and 4 triples has exactly 2 satisfying permutations out of 120: the identity ordering (0,1,2,3,4) and its reverse (4,3,2,1,0). The claimed solution is correct. The example has good test properties: 2 satisfying vs 118 non-satisfying configurations.

Well-written

Warn — two issues to address.

4a — Information Completeness:

• ✅ Motivation: Present and substantive
• ✅ Name: Betweenness — valid name for a feasibility problem (no Maximum/Minimum prefix needed)
• ✅ Reference: Garey & Johnson A12 MS1 cited
• ✅ Definition: Well-formed with INSTANCE/QUESTION format
• ✅ Variables: Count, domain, and meaning all specified
• ✅ Schema: Type name, fields, and types specified
• ⚠️ Complexity: The section discusses algorithms in prose but does not provide a concrete complexity expression in terms of problem parameters (e.g., "2^num_elements" or "num_elements^2 * 2^num_elements"). The declare_variants! macro requires a concrete string like "2^num_elements". This should be added.
• ⚠️ How to solve: ILP is checked but no companion [Rule] Betweenness to ILP issue is linked. Per the template requirements, if direct ILP solving is claimed, a companion issue must be linked in a "Reduction Rule Crossref" section.
• ✅ Example Instance: Present with concrete input and solution

4b — Definition Completeness: The definition is precise and implementable. Input (finite set A, collection C of ordered triples), feasibility constraint (existence of one-to-one function f satisfying betweenness), and all quantifiers are explicit.

4c — Symbol and Notation Consistency: Symbols are consistent across sections. The schema uses num_elements for |A| and triples for C, matching the definition.

4d — Example Quality:

• ✅ Non-trivial: 5 elements, 4 triples — sufficient to exercise the problem
• ✅ Exercises core structure: Multiple betweenness triples that constrain the ordering
• ✅ Expected outcome: Satisfying ordering provided with step-by-step verification
• ✅ Round-trip testable: 2 satisfying vs 118 non-satisfying permutations — good discrimination
• ✅ Non-trivial note about symmetry (reverse ordering also satisfies) and a failing ordering is shown

Recommendations

• Fix the year inconsistency: use "Opatrný, 1979" consistently (matching Garey & Johnson's citation)
• Correct the complexity attribution: the O*(2^n) Held-Karp DP result should cite Koivisto & Parviainen (2012/2013), not Opatrný
• Add a concrete complexity expression for declare_variants!, e.g., "num_elements^2 * 2^num_elements" (the n^2 factor comes from the DP state transitions)
• Link or create a companion [Rule] Betweenness to ILP issue if ILP solving is intended
• Note: the example uses 1-based positions [1,2,3,4,5] — implementation will use 0-based indices [0,1,2,3,4]; consider clarifying this in the example

[isPANN]

Fix-issue changelog

• Associated rules: Linked [Rule] SET SPLITTING to BETWEENNESS #842 (SetSplitting → Betweenness).
• Complexity: Fixed Opatrný year; added concrete expression "2^num_elements". Separated DP attribution from NP-completeness reference.
• Schema notes: Added Value = Or and getter methods.
• ILP: Added companion rule note.
• Example: Added exact count (2/120 valid orderings) and non-satisfying example.
• Added Python validation script.

Applied by /fix-issue.

[isPANN]

Please kindly check the following items (PR #960):

• Paper (PDF): check definition, proof sketch, example figure, and reproducible pred commands
• Implementation (Optional): spot-check the source files changed in this PR for correctness

💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.