# P2604: Largest subtour-LP gap among eight-vertex graph metrics

- ID: `P2604`
- Reference: `graph-metric-subtour-gap-eight`
- Page: https://theoremdb.org/statements/P2604
- Record maturity: Reviewed problem with recorded work

## Problem

For each connected simple graph \(H\) on eight labeled vertices, give the complete graph the shortest-path metric of \(H\). What is the maximum ratio between the optimal traveling-salesperson tour and the subtour-elimination LP optimum over all such \(H\)?

### Remarks

- **Remark.** The tour is a minimum Hamilton cycle in the metric completion.
- **Remark.** The subtour LP has degree equations x(delta(v))=2, cut inequalities x(delta(S))>=2, and x_e>=0.

### What counts as a solution

- Give a graph attaining the maximum ratio and certify the universal upper bound over all connected eight-vertex graphs.

## Status

The exact eight-vertex maximum remains open in this record; current certificates give 1 <= gamma_8 < 3/2 - 10^-36. [1](#reference-1)

## Work

### Evidence for the current status

**Proposition 1 (The certified interval is 1 to slightly below 3/2).** The exact eight-vertex maximum remains open in this record; current certificates give 1 <= gamma_8 < 3/2 - 10^-36.

Let
\[
\gamma_8=\max_H\frac{\operatorname{TSP}(d_H)}{\operatorname{SUBT}(d_H)},
\]
where \(H\) runs through connected simple eight-vertex graphs and \(d_H\) is its shortest-path metric. The current certified interval is
\[
\boxed{1\leq\gamma_8<\frac32-10^{-36}}.
\]
The lower endpoint is attained by \(H=C_8\). Its metric tour optimum and subtour optimum are both 8, as checked by `gmstg8-artifact-cycle-eight-certificate`.

Karlin, Klein, and Oveis Gharan prove that there is an \(\epsilon>10^{-36}\) such that every metric TSP instance has a tour of expected cost at most \((3/2-\epsilon)\) times the subtour-LP optimum. Every graph metric in this finite family is a metric TSP instance, so their theorem gives the displayed strict upper bound.

This interval is deliberately conservative. It records only bounds whose hypotheses and certificates have been checked. The exact maximum requires the isomorph-free LP sweep described below.

### Background and intake notes

The generic metric subtour bounds give an initial interval between 1 and 3/2. Exact enumeration should replace it with a rational value.

- Original intake status: Status unknown. Small-order subtour-gap instances may have been enumerated.
- Canonicalize connected graphs before solving either optimization problem. Cache each unlabeled graph's distance matrix and LP dual certificate.
- Every new incumbent is a rational number with a graph, tour, primal LP point, and dual LP solution. These objects make progress reusable.

- Recorded example: For H=C_8, the Hamilton cycle and its incidence vector both have cost 8, so the tour and subtour-LP optima agree.

### Other known results

- **Proposition 2** (supported): A published exhaustive computation for all eight-city 1,2-TSP instances gives a useful exact pruning bound for this subclass. [2](#reference-2)

### Prior approaches

- **Route 1** (supported): The sources define the relaxation, supply the general upper bound, and settle the eight-city 1,2 subclass; none reports this graph-metric maximum. [3](#reference-3) [1](#reference-1) [2](#reference-2) [4](#reference-4)

### Open directions

- **Route 2** (reported): The corpus is fixed and the certificate format is specified; no universal LP sweep is claimed in this version. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python checks every tour and every cut of the cycle incidence vector; a one-line degree identity proves LP optimality.
- **Artifact 2** (reproduced): nauty geng 2.6r6 produced 11,117 graph6 records, matching the official nauty data table. [4](#reference-4)

### Computational notes

- Direct enumeration of all Hamilton cycles in the C_8 metric found tour optimum 8. The subtour LP also has optimum 8: its degree equations force sum_e x_e=8 because every nonzero metric distance is at least one, and the cycle incidence vector attains that value.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `graph-metric-subtour-gap-eight`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Anna Karlin, Nathan Klein, and Shayan Oveis Gharan, “A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP”. arXiv:2105.10043 (2021). Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan, A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP, abstract and main theorem; lower endpoint certificate in this dataset https://arxiv.org/abs/2105.10043
   - Also cited at Abstract and main theorem
   - Also cited at Finite computation plan prepared on 2026-07-25
   - preprint; reference source; arXiv:2105.10043, checked 2026-08-01; checked 2026-07-25
   - Source use: citation_only
   - For Largest subtour-LP gap among eight-vertex graph metrics: The exact eight-vertex maximum remains open in this record; current certificates give 1 <= gamma_8 < 3/2 - 10^-36.
   - Source named by the research packet.
2. <a id="reference-2"></a>Jiawei Qian, Frans Schalekamp, David P. Williamson, and Anke van Zuylen, “On the Integrality Gap of the Subtour LP for the 1,2-TSP”. Lecture Notes in Computer Science (2012), 606-617. DOI 10.1007/978-3-642-29344-3_51. Jiawei Qian, Frans Schalekamp, David P. Williamson, and Anke van Zuylen, On the Integrality Gap of the Subtour LP for the 1,2-TSP, Section 5 and Table 1 https://doi.org/10.1007/978-3-642-29344-3_51
   - Also cited at Section 5 and Table 1
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - For Largest subtour-LP gap among eight-vertex graph metrics: Supports the statement, selected result, computational method, or current boundary recorded in the reviewed packet.
3. <a id="reference-3"></a>Michael Held and Richard M. Karp, “The Traveling-Salesman Problem and Minimum Spanning Trees”. Operations Research 18(6) (1970), 1138-1162. DOI 10.1287/opre.18.6.1138. Michael Held and Richard M. Karp, The Traveling-Salesman Problem and Minimum Spanning Trees, Operations Research 18(6), 1970; related sources listed in metadata https://doi.org/10.1287/opre.18.6.1138
   - Also cited at Operations Research 18(6), 1138-1162, 1970
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - For Largest subtour-LP gap among eight-vertex graph metrics: The sources define the relaxation, supply the general upper bound, and settle the eight-city 1,2 subclass; none reports this graph-metric maximum.
4. <a id="reference-4"></a>Brendan D. McKay, “Graphs,” Combinatorial Data, Australian National University, maintained graph collections, checked 2026-08-01. Simple Graphs table; 11,117 unlabeled eight-vertex graph6 records https://users.cecs.anu.edu.au/~bdm/data/graphs.html
   - Also cited at Simple graphs table, eight vertices
   - Also cited at Brendan McKay, Combinatorial Data, Simple graphs table; locally reproduced with nauty geng 2.6r6 on 2026-07-25
   - website; reference source; checked 2026-07-25
   - Source use: citation_only
   - Reused material: Simple Graphs table; 11,117 unlabeled eight-vertex graph6 records
   - Reuse basis: fair_use_reviewed; rights holder: Brendan D. McKay; checked 2026-08-01; by Philip Weiss, TheoremDB staff
   - Required attribution: Brendan D. McKay, “Graphs,” Combinatorial Data, Australian National University, maintained graph collections, checked 2026-08-01.
   - For Largest subtour-LP gap among eight-vertex graph metrics, this source pins the complete graph corpus used by the packet's finite replay.