Universal Metric Expansions for TSP: A Katětov–Urysohn and Dual-Constraint Lifting Approach

This brief work presents a partial-distance encoding of the Traveling Salesman Problem through a combination of Katětov–Urysohn expansions and Dual-Constraint Lifting (DCL). By assigning interval-based distances between “in” and “out” points for each city—plus a global pivot to capture total cost—our method embeds TSP constraints into a single difference-constraint framework. Repeated local expansions, reminiscent of Floyd–Warshall, replace any need for BFS or enumerations. Tests on small- to moderate-scale TSP instances (both random and Euclidean) highlight polynomial-style performance in practice, suggesting the partial-distance DCL technique may merit deeper investigation for NP-complete decision problems.