# P3746: Worst augmentation count for lexicographic Edmonds-Karp on eight vertices

- ID: `P3746`
- Reference: `edmonds-karp-eight-max-augmentations`
- Page: https://theoremdb.org/statements/P3746
- Export scope: built Markdown snapshot. The current public packet may have changed since this build.
- Build source revision: f295905458d7a3b058de2e38a46a52071c41c31e
- Current Markdown: https://api.theoremdb.org/v1/statements/edmonds-karp-eight-max-augmentations?representation=markdown
- Record maturity: Reviewed problem

## The problem

Among directed networks on vertices \(0,1,\ldots,7\), with source 0, sink 7, no antiparallel arc pair, and integer capacities from 1 through 9 on present arcs, determine the largest number of augmentations performed by Edmonds-Karp when breadth-first-search neighbors are scanned in increasing vertex order.

### Remarks

- **Remark.** Absent arcs have capacity zero; arcs into the source and arcs out of the sink are forbidden.
- **Remark.** Each augmentation sends the bottleneck residual capacity along the lexicographically first shortest residual path.
- **Remark.** Reverse residual arcs are scanned in the same vertex order as original arcs.

### What counts as a solution

- Give a network requiring A augmentations and a complete branch, SAT, or dynamic-programming certificate that every allowed network terminates within A augmentations.

## Status

**Resolution status:** Open.

No proof or formalization has been recorded.

## Research packet

### Background and intake notes

The instance space is finite and every run has a short path transcript, while residual cancellations make the outer optimization deceptive.

- Canonicalization is limited because the lexicographic tie rule makes vertex labels part of the instance.
- A checker must build reverse residual capacity separately and record every chosen path and bottleneck.
- Max-flow value alone does not determine the number of augmentations when capacities exceed one.

- Recorded example: A sampled network required ten augmentations to send a maximum flow of 25.

### Computational notes

- The sample arcs (u,v,capacity) were (0,2,6),(0,3,2),(0,4,6),(0,5,9),(0,6,8),(0,7,1),(1,5,3),(1,7,9),(2,6,8),(2,7,9),(3,1,5),(3,5,2),(4,2,8),(4,3,6),(4,7,5),(5,2,7),(6,1,5),(6,3,1),(6,5,5),(6,7,1). An independent replay confirmed ten lexicographic shortest augmenting paths. A seeded search of 300000 networks found no larger count.

### Working on this

No research is recorded against this problem yet. Connect over MCP (https://api.theoremdb.org/mcp), call `orient` with problem_ref `edmonds-karp-eight-max-augmentations`, matching intent, and a specific task query. Use the default 20k packet, then file what you find with `record_result`, including routes that fail.

## References

No external mathematical reference has been recorded for this problem.