The Papamanthou-Tollis Conjecture on Parameterized st-Orientations
On the basis of experiments up to 5000 nodes, Papamanthou and Tollis conjectured a relation between the longest paths produced by their MaxSTN and MinSTN algorithms for -orientations of biconnected graphs. A counterexample refutes it.
- Result
- Disproved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Construction
- Field
- Graph algorithms
- Posed by
- Charalampos Papamanthou, Ioannis G. Tollis
- Year posed
- 2008
- Years open
- 18y
- Solved
- 2026-06-12
- Model
- Claude Sonnet 4.6
- Vendor
- Anthropic
- Collaborators
- Charalampos Papamanthou
- Verification
- Site-confirmed
- Publication
- Preprint
- Significance
- 10 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The paper devotes a section to this and it is worth reading in full, because the headline line is the least of it. Claude Sonnet 4.6 read the earlier paper and wrote the Python st-orientation code quickly, and the authors say no code was written by a human. But the loop mattered: the authors caught and fed back three specific bugs, cut vertices being treated as eligible, the sink block not being excluded, and the timestamp overwrite rule implemented incorrectly. The model ran exhaustive tests for , declined as computationally infeasible, then later suggested a resource that would have made it possible. It also produced counterexamples that external validation confirmed were wrong, and drew conclusions the authors state they did not verify, including an exhaustive-search claim over the biconnected graphs on five and six vertices. The counterexample that survived is the model's; so is a quantity of discarded work. The author is one of the two who posed the conjecture, so this is someone refuting their own with a model.
Verification
The refutation is an explicit graph, so it reduces to running the two named algorithms on it, and that part stands on its own. The surrounding computational claims deserve less weight: in the same section the authors record that the model produced counterexamples later confirmed wrong, and that they did not verify its claim to have exhaustively searched the biconnected graphs on five and six vertices. arXiv note, not peer-reviewed.
Source
arXiv:2606.14539 - On a Conjecture for Parameterized st-Orientations