A Structural Equivalence of Symmetric TSP to a Constrained Group Steiner Tree Problem
We present a brief structural equivalence between the symmetric TSP and a constrained Group Steiner Tree Problem (cGSTP) defined on a simplicial incidence graph. Given the complete weighted graph on the city set V, we form the bipartite incidence graph between triangles and edges. Selecting an admissible, disk-like set of triangles induces a unique boundary cycle. With global connectivity and local regularity constraints, maximizing net weight in the cGSTP is exactly equivalent to minimizing the TSP tour length.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.05773
curl -X POST /api/v1/records/arxiv/2602.05773/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.05773/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'