[Model] OptimalLinearArrangement

[isPANN]

Motivation

OPTIMAL LINEAR ARRANGEMENT from Garey & Johnson, A1.3 GT42. A classical NP-complete graph optimization problem that asks for a vertex ordering on a line that minimizes the total edge length. It is a fundamental problem in VLSI design, graph drawing, and sparse matrix computations. It serves as a source problem for reductions to CONSECUTIVE ONES MATRIX AUGMENTATION (R110) and SEQUENCING TO MINIMIZE WEIGHTED COMPLETION TIME (R134), and is itself a target of a reduction from SIMPLE MAX CUT (R278).

Associated rules:

• R110: Optimal Linear Arrangement -> Consecutive Ones Matrix Augmentation (as source)
• R134: Optimal Linear Arrangement -> Sequencing to Minimize Weighted Completion Time (as source)
• R278: Simple Max Cut -> Optimal Linear Arrangement (as target)

Prerequisite note: The source rule R278 requires MaxCut which already exists in the codebase.

Definition

Name: OptimalLinearArrangement
Canonical name: OPTIMAL LINEAR ARRANGEMENT
Reference: Garey & Johnson, Computers and Intractability, A1.3 GT42

Mathematical definition:

INSTANCE: Graph G = (V, E), positive integer K.
QUESTION: Is there a one-to-one function f: V -> {1, 2, ..., |V|} such that sum_{{u,v} in E} |f(u) - f(v)| <= K?

Variables

• Count: n = |V| variables, one per vertex, representing the position in the linear ordering.
• Per-variable domain: Each variable takes a value in {1, 2, ..., n}, subject to the constraint that all values are distinct (i.e., the assignment is a permutation).
• Meaning: Variable x_v = f(v) gives the position of vertex v on the line. A satisfying assignment is a permutation f such that sum_{{u,v} in E} |f(u) - f(v)| <= K.
• dims() specification: vec![n; n] where n = |V|. Each variable ranges over n positions. Note: only n! out of n^n configurations are valid permutations; evaluate must return false for non-permutation configurations.

Schema (data type)

Type name: OptimalLinearArrangement
Variants: graph topology (graph type parameter G)

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E)
bound	usize	The positive integer K (upper bound on total edge length)

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

• num_vertices() — returns |V|
• num_edges() — returns |E|

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• No weight type is needed; edges are unweighted and the objective is purely a function of vertex positions.
• The optimization variant (minimize sum of |f(u)-f(v)|) could alternatively be modeled as an OptimizationProblem with Direction::Minimize.
• Naming note: The name OptimalLinearArrangement follows the Garey & Johnson canonical name. Since the G&J definition is a decision problem (satisfaction), this naming is acceptable. If implemented as optimization, consider MinimumLinearArrangement.

Complexity

• Best known exact algorithm: O*(2^n) time and O*(2^n) space using dynamic programming over subsets (analogous to Held-Karp for TSP), where n = |V|. Can also be solved in O*(4^n) time with polynomial space.
• NP-completeness: NP-complete [Garey, Johnson, and Stockmeyer, 1976]. Remains NP-complete if G is bipartite [Even and Shiloach, 1975].
• Polynomial-time special cases: Solvable in polynomial time if G is a tree [Shiloach, 1979]. The tree algorithm runs in O(n^{2.2}) time.
• Approximation: O(log n)-approximation via balanced separators. O(sqrt(log n) * log log n)-approximation for general graphs [Feige and Lee, 2007].
• declare_variants! complexity string: "2 ^ num_vertices" (subset DP, analogous to Held-Karp).
• References:
  • M. R. Garey, D. S. Johnson, and L. Stockmeyer (1976). "Some simplified NP-complete graph problems." Theoretical Computer Science, 1(3):237-267.
  • S. Even and Y. Shiloach (1975). "NP-completeness of several arrangement problems." Dept. of Computer Science, Technion.
  • Y. Shiloach (1979). "A minimum linear arrangement algorithm for undirected trees." SIAM Journal on Computing, 8(1):15-32.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K.
QUESTION: Is there a one-to-one function f: V -> {1,2,...,|V|} such that sum_{{u,v} in E} |f(u)-f(v)| <= K?

Reference: [Garey, Johnson, and Stockmeyer, 1976]. Transformation from SIMPLE MAX CUT.
Comment: Remains NP-complete if G is bipartite [Even and Shiloach, 1975]. Solvable in polynomial time if G is a tree [Shiloach, 1976], [Gol'dberg and Klipker, 1976].

How to solve

• It can be solved by (existing) bruteforce -- enumerate all n! permutations of vertices and compute the total edge length for each.
• It can be solved by reducing to integer programming -- formulate as an ILP with binary variables x_{v,p} indicating vertex v is at position p, and minimize sum of |f(u)-f(v)| over edges.
• Other: Held-Karp-style DP in O*(2^n) time; branch-and-bound with cutting planes for moderate-size instances; O(log n)-approximation via balanced separators.

Example Instance

Instance 1 (YES instance, non-trivial):
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,3}, {2,5}
• Bound K = 11
• Arrangement: f(0)=1, f(1)=2, f(2)=3, f(3)=4, f(4)=5, f(5)=6
• Cost: |1-2| + |2-3| + |3-4| + |4-5| + |5-6| + |1-4| + |3-6| = 1+1+1+1+1+3+3 = 11 <= 11
• Answer: YES

Instance 2 (NO instance):
Same graph as Instance 1, but K = 9:

• The optimal arrangement for this graph has cost 11. Since 11 > 9, no arrangement achieves cost <= 9.
• Answer: NO

Instance 3 (path graph, polynomial case):
Graph G with 6 vertices, path 0-1-2-3-4-5 (5 edges):

• K = 5
• Identity arrangement: cost = 5 (each edge has length 1)
• Answer: YES (this is optimal for a path)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel NP-complete graph problem with 3 planned reduction rules; connects to MaxCut
Non-trivial	✅ Pass	Distinct from all existing problems — permutation-based with edge-length objective
Correctness	⚠️ Warn	G&J reference verified; O*(2^n) DP claim not independently verified for OLA specifically
Well-written	⚠️ Warn	Minor naming concern and satisfaction/optimization framing ambiguity

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The problem does not exist in the codebase. OptimalLinearArrangement is a well-known NP-complete problem (GT42 in Garey & Johnson) with practical applications in VLSI design and graph drawing. Three reduction rules are planned (R110, R134 as source; R278 from MaxCut as target), which would meaningfully extend the reduction graph. The connection to MaxCut (which already exists in the codebase) is particularly valuable.

Non-trivial

This is genuinely distinct from all existing problems. The feasibility constraint involves a permutation (bijection to {1,...,n}) rather than binary selection or bin assignment, and the objective involves absolute differences of positions — a structure not present in any current problem. While BinPacking uses a similar vec![n; n] dims pattern, the constraint semantics are completely different.

Correctness

Garey, Johnson & Stockmeyer (1976): ✅ Confirmed. "Some Simplified NP-Complete Graph Problems," Theoretical Computer Science 1(3):237–267. ScienceDirect. The paper proves NP-completeness of Optimal Linear Arrangement via reduction from Simple Max Cut, matching the issue's claim.

Even & Shiloach (1975): Referenced in G&J commentary. Not independently verified as a formal publication (appears to be a tech report from Technion), but the claim that OLA remains NP-complete on bipartite graphs is well-established in the literature.

Shiloach (1979): ✅ The SIAM J. Computing paper on minimum linear arrangement for trees exists: SIAM. Note: the issue says "1976" but the actual SIAM publication is 1979 (vol. 8, no. 1, pp. 15-32). The issue should correct this date.

O(2^n) DP claim:* ⚠️ The issue claims a Held-Karp-style O*(2^n) DP algorithm exists for OLA. I could not find a specific reference for this bound applied to OLA (as distinct from TSP). While it is plausible that subset-based DP can solve OLA in O*(2^n) time (by tracking which vertices have been placed), a citation should be provided to support this claim. The declare_variants! complexity string will need a verified bound.

Example verification:

• Instance 1: Identity arrangement on the given graph with edges {0,1},{1,2},{2,3},{3,4},{4,5},{0,3},{2,5} gives cost 1+1+1+1+1+3+3 = 11 ≤ K=11. ✅
• Instance 2: Two alternative arrangements both give cost 11 > 9, supporting the NO answer. The claim that 11 is optimal seems plausible but is not proved in the issue. ⚠️
• Instance 3: Path graph identity arrangement gives cost 5, which is indeed optimal. ✅

Well-written

Strengths:

• All template sections present and substantive
• Mathematical definition matches G&J precisely
• Three distinct examples covering YES, NO, and polynomial special case
• Correctly identifies the BinPacking-style vec![n; n] dims pattern

Issues:

1. Naming convention: The name OptimalLinearArrangement uses "Optimal" as a prefix, which is non-standard in the project. Project conventions use Maximum/Minimum for optimization or no prefix for satisfaction. Since this is proposed as a satisfaction problem with a bound K, the name should either be LinearArrangement (satisfaction, no prefix) or MinimumLinearArrangement (optimization variant). The issue mentions both variants but doesn't commit to one.

2. Satisfaction vs. optimization framing: The Schema notes say "This is a satisfaction (decision) problem" but also mention "The optimization variant (minimize sum) is an OptimizationProblem." The issue should pick one formulation for implementation. Given that the G&J definition is a decision problem, satisfaction seems appropriate, but the name "Optimal" contradicts this.

3. Shiloach date: Issue says 1976, actual SIAM publication is 1979.

4. Missing declare_variants! complexity string: The Complexity section is prose-based. For implementation, a concrete bound string is needed. If O*(2^n) is adopted (pending citation), the string would be "2^num_vertices".

5. Permutation constraint not addressed in dims discussion: The dims() return vec![n; n] creates an n^n search space, but only n! permutations are valid. The issue should note that evaluate must return Invalid/false for non-permutation configs, which significantly impacts brute-force performance.

Recommendations

• Rename to LinearArrangement (satisfaction) or MinimumLinearArrangement (optimization)
• Provide a specific citation for the O*(2^n) exact algorithm claim
• Correct Shiloach publication year from 1976 to 1979
• Add a note about permutation validation in evaluate