Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs

Abstract

A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem one can represent such a multigraph as a combination of a most n 2 cycle covers each taken with an appropriate multiplicity. It is proved that if the d-regular multigaph does not contain more than ⌊d/2⌋ copies of any 2-cycle then a similar decomposition into O(n 2) pairs of cycle covers where each 2-cycle occurs in at most one component of each pair is found.