[Model] BottleneckTravelingSalesman

[isPANN]

---

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

Motivation

BOTTLENECK TRAVELING SALESMAN (P100) from Garey & Johnson, A2 ND24. A variant of the classical Traveling Salesman Problem where the objective is to minimize the maximum (bottleneck) edge weight in a Hamiltonian tour rather than minimizing total tour length. NP-complete even when distances are restricted to {1, 2}. It is a target in the reduction from HAMILTONIAN CIRCUIT.

Associated rules:

• HamiltonianCircuit → BottleneckTravelingSalesman (incoming, issue [Rule] HAMILTONIAN CIRCUIT to BOTTLENECK TSP #259)

Definition

Name: BottleneckTravelingSalesman
Canonical name: BOTTLENECK TRAVELING SALESMAN
Reference: Garey & Johnson, Computers and Intractability, A2 ND24

Mathematical definition:

INSTANCE: A weighted graph G = (V, E) with edge weights w: E → ℤ⁺.
OBJECTIVE: Find a Hamiltonian cycle H in G that minimizes the bottleneck (maximum edge weight), i.e., minimize max_{e ∈ H} w(e).

A configuration is a subset S ⊆ E. A configuration is feasible if S forms a Hamiltonian cycle (every vertex has degree exactly 2 in S, and S is connected). The objective value is max_{e ∈ S} w(e) for feasible configurations, and Invalid otherwise.

Variables

• Count: |E| variables (one per edge in the graph).
• Per-variable domain: {0, 1} — 1 if the edge is included in the tour, 0 otherwise.
• Meaning: A feasible assignment selects exactly |V| edges forming a Hamiltonian cycle. The objective value is the maximum weight among the selected edges.

Dims

[2; num_edges] — one binary variable per edge.

Schema (data type)

Type name: BottleneckTravelingSalesman
Variants: none

Field	Type	Description
graph	SimpleGraph	The underlying graph G = (V, E)
edge_weights	Vec<i32>	Edge weights w: E → ℤ⁺

Notes:

• This is an optimization problem: Metric = SolutionSize<i32>, Direction::Minimize.
• The objective is max(selected edge weights), not sum — this is what distinguishes it from TravelingSalesman.
• No type parameters. Graph type and weight type are fixed to SimpleGraph and i32. Variants can be added later if a concrete need arises.

Size fields

Getter	Meaning
num_vertices	Number of vertices
num_edges	Number of edges

Complexity

• Best known exact algorithm: O(m² · 2^m) via the Held-Karp dynamic programming algorithm (Held & Karp, 1962), adapted for the bottleneck objective by replacing sum with max. Here m = |V| is the number of vertices.
• Complexity string: "num_vertices^2 * 2^num_vertices"
• NP-completeness: NP-complete by reduction from HAMILTONIAN CIRCUIT (Garey & Johnson ND24). Remains NP-complete even when all edge weights are in {1, 2}.
• References:
  • M. Held and R.M. Karp (1962). "A dynamic programming approach to sequencing problems." Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210.
  • P.C. Gilmore and R.E. Gomory (1964). "Sequencing a one state-variable machine: a solvable case of the traveling salesman problem." Operations Research 12, pp. 655–679. (Polynomial special case.)

Extra Remark

Full book text:

INSTANCE: Set C of m cities, distance d(ci,cj) ∈ Z+ for each pair of cities ci,cj ∈ C, positive integer B.
QUESTION: Is there a tour of C whose longest edge is no longer than B, i.e., a permutation <cπ(1),cπ(2),...,cπ(m)> of C such that d(cπ(i),cπ(i+1)) ≤ B for 1 ≤ i < m and such that d(cπ(m),cπ(1)) ≤ B?

Reference: Transformation from HAMILTONIAN CIRCUIT.
Comment: Remains NP-complete even if d(ci,cj) ∈ {1,2} for all ci,cj ∈ C. An important special case that is solvable in polynomial time can be found in [Gilmore and Gomory, 1964].

Note: Garey & Johnson state the decision version. We implement the optimization version (minimize bottleneck), which subsumes the decision problem: a tour with bottleneck ≤ B exists iff the optimal bottleneck is ≤ B.

How to solve

• It can be solved by (existing) bruteforce — enumerate all subsets of edges, check for valid Hamiltonian cycles, return the one with minimum bottleneck (max edge weight).
• It can be solved by reducing to integer programming.
• Other: Held-Karp DP in O(m² · 2^m) time, adapted for bottleneck objective.

Example Instance

Complete graph K₅ on 5 vertices with edge weights:

     0  1  2  3  4
  0: -  5  4  4  5
  1: 5  -  4  1  2
  2: 4  4  -  1  5
  3: 4  1  1  -  4
  4: 5  2  5  4  -

Edge list with weights (lexicographic order):

Edge	Weight
(0,1)	5
(0,2)	4
(0,3)	4
(0,4)	5
(1,2)	4
(1,3)	1
(1,4)	2
(2,3)	1
(2,4)	5
(3,4)	4

Search space: 2¹⁰ = 1024 binary configurations, 12 of which are valid Hamiltonian cycles.

Expected Outcome

Optimal tour: 0 → 2 → 1 → 4 → 3 → 0
Selected edges: {(0,2), (0,3), (1,2), (1,4), (3,4)} with weights [4, 4, 4, 2, 4]
Bottleneck (max edge weight): 4
Total weight: 18

This is the unique optimal solution — all 11 other Hamiltonian cycles have bottleneck = 5.

Contrast with standard TSP: The minimum total weight tour is 0 → 2 → 3 → 1 → 4 → 0 with total weight 13 but bottleneck = 5. The BTSP optimal tour "pays" a higher total weight (18 vs 13) to avoid all weight-5 edges, demonstrating the fundamental difference between minimizing the sum vs the maximum.

Bottleneck distribution across all 12 feasible tours:

• Bottleneck = 4: 1 tour (optimal)
• Bottleneck = 5: 11 tours (suboptimal)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in codebase; distinct from existing TravelingSalesman
Non-trivial	✅ Pass	Different objective (bottleneck vs total weight) yields distinct feasibility constraints
Correctness	⚠️ Warn	Held-Karp complexity claim correct; Gilmore-Gomory reference verified but is about a polynomial special case, not this problem directly
Well-written	❌ Fail	Example Instance 2 is self-contradictory; variable encoding is problematic; decision vs optimization ambiguity; missing naming convention compliance

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. BottleneckTravelingSalesman does not exist in the codebase. The 24 currently implemented problems do not include it. The problem is a well-known variant from Garey & Johnson (A2 ND24) with a natural incoming reduction from Hamiltonian Circuit. It adds a new node to the reduction graph and is distinct from the existing TravelingSalesman (which minimizes total tour weight, not the bottleneck edge).

Non-trivial

Pass. The Bottleneck TSP has a fundamentally different objective from the standard TSP: minimize the maximum edge weight in the tour rather than the sum. This changes the feasibility constraint structure — a configuration that is optimal for standard TSP may be suboptimal for bottleneck TSP and vice versa. The existing TravelingSalesman uses OptimizationProblem with SolutionSize<W> and Direction::Minimize on total weight; BottleneckTravelingSalesman would be a SatisfactionProblem (decision version) or an optimization problem with a completely different objective aggregation (max instead of sum). This is not a variant that can be handled by a type parameter change to the existing model.

Correctness

Warn — minor issues, no fatal errors.

1. Held & Karp (1962): Verified. The paper "A Dynamic Programming Approach to Sequencing Problems" is in references.bib as heldkarp1962. The O(m^2 * 2^m) bound is correct for the standard TSP Held-Karp DP, and the adaptation to bottleneck TSP (replacing sum with max) is straightforward and well-established.

2. Gilmore & Gomory (1964): Verified. "Sequencing a one state-variable machine: A solvable case of the traveling salesman problem" was published in Operations Research, Vol. 12, pp. 655–679. However, this paper concerns a polynomial-time solvable special case of TSP (not of Bottleneck TSP specifically). The issue's Extra Remark section correctly quotes Garey & Johnson's comment that "An important special case that is solvable in polynomial time can be found in [Gilmore and Gomory, 1964]," but the issue should clarify that this reference is for context on the standard TSP, not a solver for Bottleneck TSP.

3. NP-completeness claim: Correct per Garey & Johnson. The reduction from Hamiltonian Circuit is standard: given a graph G, set d(u,v) = 1 if (u,v) is an edge, 2 otherwise, and set B = 1. A Hamiltonian cycle exists in G iff the bottleneck TSP instance has a tour with bottleneck ≤ 1.

4. Complexity string for declare_variants!: The issue mentions O(m^2 * 2^m) but does not provide the exact complexity string in the required format. The existing TravelingSalesman uses "2^num_vertices" — the bottleneck version should use something like "num_cities^2 * 2^num_cities" (assuming num_cities is a getter method).

Well-written

Fail — several issues need fixing.

4a: Information Completeness

All template sections are present. However:

• Motivation mentions "R45: HAMILTONIAN CIRCUIT -> BOTTLENECK TRAVELING SALESMAN" but Hamiltonian Circuit is not yet implemented in the codebase, so the incoming reduction cannot be implemented immediately. This is acceptable as a future plan but should be noted.

4b: Definition Completeness

• Decision vs Optimization ambiguity: The Schema Notes section says "This is a satisfaction (decision) problem: Metric = bool" but then adds "Alternatively, could be formulated as an optimization problem minimizing the bottleneck." The issue must commit to one formulation. Given the Garey & Johnson definition is a decision problem, SatisfactionProblem is the right choice, but the issue should remove the ambiguity and state this definitively.

4c: Variable Encoding Issues

• Permutation encoding is problematic. The Variables section proposes m variables with domain {0, 1, ..., m-1} representing city positions. This does NOT match the project's conventions. The existing TravelingSalesman uses binary edge variables (one per edge, 0 or 1), not permutation variables. Using permutation variables with domain size m means dims() returns [m, m, ..., m] (m copies), and brute-force enumeration explores m^m configurations instead of the valid m! permutations — extremely wasteful.
• Recommendation: Either (a) use binary edge variables like TravelingSalesman (one variable per city pair, 0/1, with degree-2 and connectivity constraints), or (b) if using a distance-matrix-based schema without an explicit graph, clearly justify the encoding choice and ensure evaluate() handles the permutation validity check.

4d: Example Quality — FAIL

• Instance 2 is self-contradictory. It is introduced as "Instance 2 (NO — no tour with bottleneck ≤ B)" with B=1, but the analysis concludes "The only Hamiltonian tour using only distance-1 edges is this cycle: 0→1→2→3→4→5→0, bottleneck = 1 ≤ B = 1. Answer: YES". The header says NO but the conclusion says YES. This is a clear error.
• The issue then changes B to 0 to get a NO instance, but this is trivial (all distances are ≥ 1, so B=0 always fails). A proper NO instance should have B ≥ 1 but with a graph structure that prevents a Hamiltonian tour within the bottleneck bound.
• Instance 1 is too easy. All edges in the tour have weight 1, so the bottleneck is trivially satisfied. A better example would have a tour where the bottleneck edge is close to B, demonstrating the tension between the bound and the tour structure.

4e: Symbol Consistency

• The issue uses m for the number of cities throughout, which is fine. However, the Schema uses num_cities as the field name — should verify this will be the getter method name used in complexity/overhead expressions.

Recommendations

• Fix Instance 2: either correct the header to say YES, or construct a genuine NO instance where no Hamiltonian tour has all edges ≤ B (e.g., a graph where one vertex has only high-weight edges).
• Commit definitively to SatisfactionProblem formulation and remove the optimization alternative discussion, or choose the optimization formulation.
• Reconsider the variable encoding: binary edge variables (matching TravelingSalesman style) would be more consistent with the codebase.
• Add a concrete complexity string for declare_variants! (e.g., "num_cities^2 * 2^num_cities").

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	Pass	Novel problem; concrete incoming reduction from HamiltonianCircuit
Non-trivial	Pass	Different objective (bottleneck max vs sum) from existing TravelingSalesman
Correctness	Pass	References verified; complexity claims correct
Well-written	Fail	Self-contradictory example, missing required sections, ambiguous formulation

Overall: 3 passed, 0 warnings, 1 failed

---

Usefulness

Pass. BottleneckTravelingSalesman does not exist in the codebase (pred show confirms). The issue identifies a concrete incoming reduction from HamiltonianCircuit (which is implemented as HamiltonianCircuit/SimpleGraph). The problem is a well-known variant from Garey & Johnson (A2 ND24) and would add a new node to the reduction graph. It is clearly distinct from the existing TravelingSalesman (which minimizes total tour weight, not the bottleneck edge).

Non-trivial

Pass. The Bottleneck TSP has a fundamentally different objective from the standard TSP: minimize the maximum edge weight in the tour rather than the sum. This changes the feasibility constraint structure — a configuration that is optimal for standard TSP may be suboptimal for bottleneck TSP and vice versa. The existing TravelingSalesman uses OptimizationProblem with SolutionSize<W> and Direction::Minimize on total weight. BottleneckTravelingSalesman as a decision problem (SatisfactionProblem) has entirely different evaluation semantics. This is not a variant achievable by adding a type parameter to the existing model.

Correctness

Pass.

1. Held & Karp (1962): Verified. Present in references.bib as heldkarp1962. The O(m² · 2^m) bound is correct for the Held-Karp DP, and adaptation to bottleneck TSP (replacing sum with max) is standard.

2. Gilmore & Gomory (1964): Verified externally. "Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem" published in Operations Research, Vol. 12(5), pp. 655–679. The issue correctly attributes it as a polynomial-time solvable special case per G&J's comment. Not currently in references.bib — should be added if this problem is implemented.

3. NP-completeness claim: Correct per Garey & Johnson ND24. Reduction from Hamiltonian Circuit is standard (set d(u,v)=1 if edge exists, 2 otherwise, B=1).

4. Complexity expression: O(m² · 2^m) is correct. For declare_variants!, should use a concrete string like "num_cities^2 * 2^num_cities".

Well-written

Fail — 6 issues.

4a: Missing required sections

The following required sections for [Model] issues are absent:

• Dims: No explicit dims specification. Should state the config space per variable (e.g., [m; m] for permutation encoding, or [2; m*(m-1)/2] for binary edge encoding).
• Size fields: No section listing getter names and meanings (e.g., num_cities → number of cities m, num_distances → number of pairwise distances).
• Expected Outcome: Missing for both examples. Satisfaction problems require: valid solution + why it satisfies the constraints.

4b: Decision vs optimization ambiguity

The Schema Notes section says "This is a satisfaction (decision) problem: Metric = bool" but then adds "Alternatively, could be formulated as an optimization problem minimizing the bottleneck." The issue must commit to one formulation. Given G&J's definition is a decision problem, SatisfactionProblem is appropriate — but the alternative discussion must be removed.

4c: Variable encoding is problematic

The Variables section proposes m variables with domain {0, 1, …, m−1} (permutation encoding). This means dims() returns [m, m, …, m] and brute-force explores m^m configurations instead of the valid m! permutations — extremely wasteful. The existing TravelingSalesman uses binary edge variables. The issue should either adopt binary edge encoding for consistency, or clearly justify the permutation approach and document how evaluate() handles invalid (non-permutation) configurations.

4d: Example Instance 2 is self-contradictory

The header says "Instance 2 (NO — no tour with bottleneck ≤ B)" with B=1, but the analysis concludes: "The only Hamiltonian tour using only distance-1 edges is this cycle: 0→1→2→3→4→5→0, bottleneck = 1 ≤ B = 1. Answer: YES." Brute-force verification confirms the answer is YES — there are exactly 2 tours (cyclic and reverse) with bottleneck = 1 out of 120 distinct tours.

The issue then changes to B=0 for a NO instance, which is trivial (all distances ≥ 1).

4e: Instance 1 has a loose bound

Instance 1 uses B=2, but the optimal bottleneck is 1 (the claimed tour 0→1→2→3→4→5→0 achieves it). A better example would use a tighter bound where the feasibility is non-trivial — e.g., an instance where the optimal bottleneck equals B exactly, demonstrating the tension between the bound and tour structure.

4f: Both instances share the same ring structure

Both distance matrices have the same "ring" structure where consecutive cities have distance 1, producing the same optimal tours. A more informative pair of examples would use different graph structures to demonstrate the problem's characteristics.

Recommendations

1. Add missing Dims, Size fields, and Expected Outcome sections.
2. Remove the optimization alternative — commit to SatisfactionProblem.
3. Reconsider variable encoding: binary edge variables (like TravelingSalesman) or clearly justify permutation encoding with Invalid handling for non-permutations.
4. Fix Instance 2: correct the NO/YES contradiction. Construct a genuine NO instance (e.g., a graph where one vertex has only high-weight edges, making any tour through it exceed B).
5. Tighten Instance 1: use a bound B that equals the optimal bottleneck.
6. Add a concrete complexity string: "num_cities^2 * 2^num_cities".
7. Add Gilmore & Gomory (1964) to references.bib if implementing this problem.

[isPANN]

Fix-issue changelog

• Switched from decision (SatisfactionProblem) to optimization (OptimizationProblem, Direction::Minimize) — objective is minimize max edge weight
• Changed variable encoding from permutation (m variables, domain {0..m-1}) to binary edge variables (one 0/1 per edge), matching TravelingSalesman
• Removed bound field from schema; schema now matches TravelingSalesman<G, W> (graph + edge_weights)
• Added missing Dims section: [2; num_edges]
• Added missing Size fields section: num_vertices, num_edges
• Added concrete complexity string: "num_vertices^2 * 2^num_vertices"
• Replaced both examples with a single K₅ instance (2¹⁰ = 1024 configs, 12 feasible tours) where BTSP optimum (bottleneck=4, total=18) differs from TSP optimum (bottleneck=5, total=13)
• Added Expected Outcome section with verified optimal tour and bottleneck distribution
• Removed decision vs optimization ambiguity — committed to optimization with explicit note about G&J's decision formulation
• Fixed self-contradictory Instance 2 (header said NO, analysis said YES)

Applied by /fix-issue.