[Model] MinimumStackerCrane

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] MinimumStackerCrane"
labels: model
assignees: ''

Motivation

STACKER-CRANE (P102) from Garey & Johnson, A2 ND26. A classical NP-hard problem on mixed graphs (containing both directed arcs and undirected edges). It generalizes the Traveling Salesman Problem to settings where certain traversals must follow a prescribed direction, modeling pickup-and-delivery routing scenarios. The problem is a target of the following reduction:

• R47: HAMILTONIAN CIRCUIT → MINIMUM STACKER-CRANE (ND26, Frederickson, Hecht, and Kim, 1978)

Definition

Name: MinimumStackerCrane
Canonical name: STACKER-CRANE (also: Stacker Crane Problem, SCP)
Reference: Garey & Johnson, Computers and Intractability, A2 ND26

Mathematical definition:

INSTANCE: Mixed graph G = (V, A, E), length l(e) ∈ Z₀⁺ for each e ∈ A ∪ E.
OBJECTIVE: Find a closed walk in G that includes each directed arc in A at least once, traversing such arcs only in the specified direction, and that has minimum total length.

Variables

• Count: The solution is encoded as a walk sequence of length L = |A| + |E|. Each variable selects the next vertex to visit from the current position.
• Per-variable domain: Each variable ranges over {0, 1, ..., |V| − 1}, selecting the next vertex in the walk.
• Dims: [num_vertices; num_arcs + num_edges]
• Meaning: The variable assignment encodes a closed walk (cycle) in the mixed graph. A valid walk (1) traverses every directed arc in A at least once, respecting arc directions, (2) uses only existing edges/arcs between consecutive vertices, and (3) returns to the starting vertex. The objective is to minimize the total traversal length.
• evaluate(): For a given vertex sequence, check that each consecutive pair is connected by an edge or arc (respecting arc direction), all directed arcs are covered, and the walk is closed. If valid, return SolutionSize::Valid(total_length). If invalid (missing connection, uncovered arc, or not closed), return SolutionSize::Invalid.

Schema (data type)

Type name: MinimumStackerCrane
Variants: variant_params![] (no type parameters — mixed graph is a unique input structure)

Field	Type	Description
vertices	usize	Number of vertices |V|
arcs	Vec<(usize, usize)>	Directed arcs A: list of (from, to) pairs
edges	Vec<(usize, usize)>	Undirected edges E: list of {u, v} pairs
arc_lengths	Vec<i32>	Length of each directed arc (non-negative)
edge_lengths	Vec<i32>	Length of each undirected edge (non-negative)

Size fields:

• num_vertices → number of vertices |V|
• num_arcs → number of directed arcs |A|
• num_edges → number of undirected edges |E|

Notes:

• This is an optimization problem: Metric = SolutionSize<i32>, Direction = Minimize, implementing OptimizationProblem.
• The mixed graph structure distinguishes it from pure undirected (TSP, Chinese Postman) or pure directed problems.
• Specializations: remains NP-complete even with all edge lengths equal to 1 (GJ comment). Also NP-hard on trees (Frederickson and Guan, 1993).

Complexity

• Best known exact algorithm: Held-Karp-style dynamic programming tracking (current vertex, set of arcs covered so far). The DP state space depends on |A|: O(|V| · 2^|A|) states, each taking O(|V|) time, giving O(|V|² · 2^|A|) total time and O(|V| · 2^|A|) space. When |A| ≈ |V|, this is O(num_vertices² · 2^num_arcs).
• Complexity expression: num_vertices^2 * 2^num_arcs
• NP-completeness: NP-complete (Frederickson, Hecht, and Kim, 1978, via transformation from Hamiltonian Circuit).
• Approximation: 9/5-approximation algorithm based on the Christofides algorithm (Frederickson, Hecht, and Kim, 1978).
• Special cases: Polynomial-time solvable when the underlying graph is a path. NP-hard on trees (Frederickson and Guan, 1993).
• References:
  • G. N. Frederickson, M. S. Hecht, C. E. Kim (1978). "Approximation algorithms for some routing problems." SIAM Journal on Computing 7(2):178–193.
  • G. N. Frederickson (1979). "Approximation algorithms for some postman problems." JACM 26(3):538–554.
  • G. N. Frederickson, D. J. Guan (1993). "Nonpreemptive ensemble motion planning on a tree." Journal of Algorithms 15(1):29–60.

Extra Remark

Full book text:

INSTANCE: Mixed graph G = (V,A,E), length l(e) ∈ Z_0^+ for each e ∈ A ∪ E, bound B ∈ Z^+.
QUESTION: Is there a cycle in G that includes each directed edge in A at least once, traversing such edges only in the specified direction, and that has total length no more than B?
Reference: [Frederickson, Hecht, and Kim, 1978]. Transformation from HAMILTONIAN CIRCUIT.
Comment: Remains NP-complete even if all edge lengths equal 1. The analogous path problem (with or without specified endpoints) is also NP-complete.

Note: The original G&J formulation is a decision problem with bound B. This codebase models the optimization version (minimize total cycle length) since the optimization formulation subsumes the decision version and is more natural for reductions.

How to solve

• It can be solved by (existing) bruteforce — enumerate all walk sequences and check feasibility + total length.
• It can be solved by reducing to integer programming.
• Other: Held-Karp-style DP in O(|V|² · 2^|A|) time tracking (current vertex, covered arcs). The 9/5-approximation of Frederickson et al. is practical for larger instances. The standard ILP formulation uses edge/arc multiplicity variables with flow-conservation constraints.

Example Instance

Instance (5 vertices, 3 arcs, 4 edges):

Mixed graph G with 5 vertices {0, 1, 2, 3, 4}:

• Directed arcs A: (0→1) len=2, (3→2) len=3, (4→0) len=1
• Undirected edges E: {1,2} len=1, {1,3} len=4, {2,4} len=2, {0,3} len=5

    arc(0→1, len=2)    edge{1,3, len=4}
  0 ─────────→ 1 ─────────── 3
  ↑                          │
  │ arc(4→0, len=1)    arc(3→2, len=3)
  │                          ↓
  4 ──────────────────────── 2
       edge{2,4, len=2}

  (also: edge{1,2, len=1} and edge{0,3, len=5})

Dims: [5; 7] — walk sequences of length 7, each step choosing from 5 vertices.
BF search space: 5⁷ = 78,125 configurations.

Optimal walk (length 12):

• Config: [0, 1, 3, 2, 4, 0, 0]
• Walk: 0 →(arc,2)→ 1 →(edge,4)→ 3 →(arc,3)→ 2 →(edge,2)→ 4 →(arc,1)→ 0
• Total length: 2 + 4 + 3 + 2 + 1 = 12
• All 3 directed arcs traversed in correct direction ✓
• Closed walk (returns to vertex 0) ✓

Suboptimal walk (length 17):

• Walk: 0 →(arc,2)→ 1 →(edge,1)→ 2 →(edge,2)→ 4 →(arc,1)→ 0 →(edge,5)→ 3 →(arc,3)→ 2 →(edge,2)→ 4 →(arc,1)→ 0
• Total length: 2 + 1 + 2 + 1 + 5 + 3 + 2 + 1 = 17
• The detour through edge {0,3} (len=5) to reach vertex 3 costs much more than the direct edge {1,3} (len=4) from vertex 1.

Key insight: At vertex 1, there is a routing choice — go directly to vertex 3 via edge {1,3} (len=4), or go through vertex 2 first via edge {1,2} (len=1), which forces a costly detour through edge {0,3} (len=5) to eventually reach the mandatory arc (3→2). The optimal route takes the direct path to vertex 3.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but no concrete reductions planned beyond unimplemented R47
Non-trivial	✅ Pass	Distinct from TravelingSalesman — mixed graph with mandatory directed arc traversal
Correctness	⚠️ Warn	Minor reference errors (year, journal details); core claims are correct
Well-written	❌ Fail	Variable encoding unclear; schema lacks variant params; naming convention violation

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The StackerCrane problem does not yet exist in the codebase (confirmed via pred show). It is a legitimate classical NP-complete problem (Garey & Johnson ND26) with practical applications in pickup-and-delivery routing. However, the motivation section only mentions a single incoming reduction (R47: Hamiltonian Circuit → Stacker Crane), and Hamiltonian Circuit itself is not yet implemented either. This means the problem would be an orphan node in the reduction graph with no connections to existing problems.

Recommendation: Add a concrete plan for connecting StackerCrane to existing problems (e.g., a reduction from/to TravelingSalesman, or implement Hamiltonian Circuit first).

Non-trivial

StackerCrane is genuinely distinct from all existing problems. While it generalizes TravelingSalesman, it has fundamentally different structure:

• It operates on a mixed graph (directed arcs + undirected edges), unlike TSP which uses a purely undirected graph.
• The feasibility constraint requires traversing all directed arcs in their specified direction, not visiting all vertices exactly once.
• The objective is a bounded-length cycle covering all arcs, not a minimum-weight Hamiltonian cycle.

This is clearly a distinct problem, not a variant of any existing model. Pass.

Correctness

3a: Reference verification

1. Frederickson, Hecht, Kim (1978) — "Approximation algorithms for some routing problems," SIAM J. Comput. 7(2):178–193. Verified. This paper exists and introduces the Stacker Crane problem with a 9/5-approximation algorithm. The NP-completeness proof via transformation from Hamiltonian Circuit is confirmed.

2. Frederickson (1991) — The issue cites: "Approximation algorithms for some postman problems," JACM 26:538–554. Year is wrong. The actual publication year is 1979, not 1991. Volume 26, pages 538–554 are correct, but the journal is JACM (1979). The issue also cites the wrong year in the Complexity section: "Frederickson and Guan, 1991" — this appears to conflate Frederickson's 1979 JACM paper with later work. The author "Guan" is not on the 1979 JACM paper; Frederickson is the sole author.

3. Garey & Johnson ND26 — The issue says "P102" and "A2 ND26." The ND26 designation is consistent with known G&J numbering for network design problems.

3b: Complexity claims

• The claim of O(n^2 * 2^n) via Held-Karp-style DP is reasonable but imprecise. The DP state space depends on |A| (number of arcs to cover), not just |V|. If |A| << |V|, the complexity would be closer to O(n * 2^|A|). The issue does not make this distinction.

• The 9/5-approximation claim is verified (Frederickson, Hecht, Kim 1978).

• The claim "polynomial-time solvable when the underlying graph is a path" is plausible but not verified from the cited references.

Well-written

4a: Information completeness — All template sections are present.

4b: Definition completeness — The mathematical definition is directly from Garey & Johnson and is well-formed. Pass.

4c: Symbol and notation consistency

• The Variables section is vague and confusing. It describes "a sequence of at most n + a + m edge traversals" and "O(n * 2^n) states" but does not clearly define what the per-variable domain is. For a satisfaction problem, the dims() function must return a concrete vector. The issue does not specify how the solution is encoded as a fixed-length configuration vector — this is critical for implementation.
• The Schema section does not follow the project's variant/type parameter conventions. Existing problems use type parameters like G (graph type) and W (weight type) with variant_params!. The proposed schema uses concrete fields (vertices, arcs, edges, etc.) without any variant parameterization. Since this is a mixed graph problem that doesn't fit existing graph types (SimpleGraph, etc.), the schema needs to explain how it will integrate with the type system.

4d: Naming convention violation

• The issue proposes the name StackerCrane. Per the project's naming conventions, satisfaction/decision problems do not use optimization prefixes, which is correct. However, looking at the problem definition more carefully: the problem asks for a cycle of total length "no more than B" — this is a decision problem with Metric = bool. The name StackerCrane is acceptable for a decision problem. No issue here.

4d: Example quality

• Instance 1 is reasonable and fully worked. However, it is quite simple (a single cycle through all vertices) and does not exercise the interesting case where the cycle must include extra edges beyond the mandatory arcs. A better example would have a graph where the optimal cycle must use undirected edges to connect disjoint groups of arcs.
• Instance 2 is fine as a negative example.

Items to fix:

1. Fix Frederickson reference year: Change "1991" to "1979" for the JACM paper. Remove "Guan" co-author attribution or provide the correct reference for Frederickson-Guan work.
2. Clarify variable encoding: Specify how the solution is encoded as a fixed-length vector for dims() and evaluate(). For example: one binary variable per edge/arc indicating inclusion in the cycle, or a permutation encoding.
3. Add variant parameters to schema: Explain how this integrates with the type system (new graph type? no variants?). Add variant_params![] if no type parameters.
4. Improve complexity description: Clarify that the DP complexity depends on |A| (arcs to cover), not just |V|.

Recommendations

• The Frederickson & Guan reference likely refers to: G.N. Frederickson, "Approximation algorithms for some postman problems," JACM 26(3):538–554, 1979 (sole author, no Guan). There may be a separate Frederickson-Guan paper on tree instances — if so, provide the full citation.
• Consider implementing this as an optimization problem (minimize total cycle length) rather than a decision problem (is length <= B?), since the optimization version is more natural for reductions and the bound B can always be checked after solving.
• A recent paper on the Stacker Crane problem on fixed topologies (2024, arXiv:2410.06764) may contain improved algorithms worth citing.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; concrete reduction from existing HamiltonianCircuit mentioned
Non-trivial	✅ Pass	Mixed-graph arc-covering is structurally distinct from TSP and Chinese Postman
Correctness	❌ Fail	Reference year/author errors; complexity description imprecise
Well-written	❌ Fail	Missing Dims/Size fields sections; variable encoding unclear; example too simple

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

StackerCrane does not exist in the codebase (pred show confirms). The issue mentions a concrete incoming reduction R47: HamiltonianCircuit → StackerCrane, and HamiltonianCircuit is already implemented (though it currently has no reductions). TravelingSalesman also exists and is structurally related, providing another potential connection point.

Pass.

Non-trivial

StackerCrane is genuinely distinct from all existing problems:

• Operates on a mixed graph (directed arcs + undirected edges), unlike TSP (complete undirected) or HamiltonianCircuit (undirected only).
• Feasibility requires covering all directed arcs in their specified direction — not visiting all vertices (TSP/HC) or traversing all edges (Chinese Postman).
• The combination of mandatory directed traversal + optional undirected edges creates unique routing structure.

Not a re-skin, variant, or isomorphism of any existing model. Pass.

Correctness

3a–3b: Reference verification

1. Frederickson, Hecht, Kim (1978) — "Approximation algorithms for some routing problems," SIAM J. Comput. 7(2):178–193. Verified. Paper exists, introduces Stacker Crane, proves NP-completeness via Hamiltonian Circuit, gives 9/5-approximation.

2. Frederickson (cited as 1991) — Wrong year and wrong co-author. The bibliography (references.bib) has this as frederickson1979: sole author Greg N. Frederickson, JACM 26(3):538–554, 1979 (not 1991). The issue incorrectly attributes "Guan" as a co-author. The "NP-hard on trees" result attributed to "Frederickson and Guan, 1991" appears to be from a different paper: Frederickson and Guan, "Nonpreemptive Ensemble Motion Planning on a Tree," J. Algorithms 15:29–60, 1993.

3. Garey & Johnson ND26 — Quoted book text is internally consistent and matches G&J format. Plausible.

3c: Complexity claims

• O(n² · 2ⁿ) via Held-Karp DP is imprecise: the DP state depends on |A| (arcs to cover), not just |V|. If |A| ≪ |V|, complexity is closer to O(n · 2^|A|). The issue conflates these.
• 9/5-approximation: verified (Frederickson et al. 1978).

Fail — reference year/author errors are factual mistakes.

Well-written

4a: Required sections

Section	Status
Name	✅ Present
Motivation	✅ Present
Reference	✅ Present
Definition	✅ Present (well-formed G&J format)
Variables	⚠️ Vague — does not specify how to encode as fixed-length config vector for dims()/evaluate()
Schema	⚠️ Missing variant params (variant_params![]), no integration with type system
Dims	❌ Missing — no explicit dims specification (e.g., [2; n+a+m] or similar)
Size fields	❌ Missing — no getter names like num_vertices, num_arcs, num_edges
Complexity	⚠️ Present but expression format unclear — should be concrete like "num_vertices^2 * 2^num_vertices"
How to solve	✅ Present
Example	⚠️ Present but weak (see below)
Expected Outcome	⚠️ Only YES/NO — should specify what a "satisfying" configuration looks like concretely

4b: Definition completeness — The G&J definition is well-formed. However, the Variables section does not explain how to implement dims() and evaluate(). For a satisfaction problem, the encoding needs to be explicit: what is each variable, what is its domain, and how does evaluate() check feasibility?

4c: Symbol consistency — The Schema uses vertices: usize but the Definition uses |V|. No size_fields section to bridge notation.

4d: Example quality

Verified via Python enumeration:

• Instance 1 is correct (cycle length = 9, all arcs covered).
• Instance 2 is correct (no feasible cycle — vertex 5 is a dead end).
• However, the example is too simple: the 6-vertex ring has degree 2 everywhere, so there is only one structurally distinct feasible cycle. The 34 "suboptimal" solutions are just the same cycle with redundant back-and-forth edge traversals, not genuinely different routes. A good example should have vertices with degree > 2, creating real routing choices.

Fail — missing Dims and Size fields sections; variable encoding unspecified; example lacks structural complexity.

Recommendations

• Fix Frederickson reference: 1979 (sole author), not 1991. Cite the trees result separately as Frederickson & Guan 1993.
• Add explicit Dims section: e.g., for a walk-sequence encoding of max length L, dims = [num_edges + num_arcs; L].
• Add Size fields: num_vertices, num_arcs, num_edges, bound.
• Clarify variable encoding for evaluate(): how is a configuration (walk sequence) validated?
• Improve example: add edges like {0,3} or {2,5} to create branching and multiple structurally distinct feasible routes.
• Correct complexity expression to reference num_arcs (not just num_vertices) since the DP state is (vertex, covered_arcs_bitmask).