Spanning Paths and Cycles: Structural Limitations of the Irrelevant Vertex Technique
The Irrelevant Vertex Technique is one of the cornerstones of algorithmic graph theory, underlying Robertson and Seymour's algorithm for \textsc{Disjoint Paths} and much of the algorithmic Graph Minors theory. We show that, in the setting of spanning routing, this technique exhibits an exact combinatorial limitation. Unlike classical routing problems, spanning routing is not governed by the number of distinguished vertices but by the way they are distributed throughout the graph. The input is a triple $(G,R,\mathcal{T})$ where $(G,R)$ is an annotated graph and $\mathcal{T}$ is a set of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.09342
curl -X POST /api/v1/records/arxiv/2607.09342/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09342/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'