A complete directed network G  (V,A) is a directed graph such that for every pair of vertices u, v ∈ V , there are arcs u → v and v → u in A with nonnegative arc lengths d(u, v) and d(v, u), respectively. The networkG  (V,A)

satisfies the triangle inequality if for all u, v,w ∈ V , d(u, v)+d(v,w) ≥ d(u,w).

A directed cycle is a sequence of vertices v1 → v2 →· · ·→v( → v1 without any repeated vertex other than the first and last ones. If the cycle contains all the vertices in G, then it is said to be a directed Hamiltonian cycle. To keep notation simple, let dij

.

d(vi, vj ).

A directed cycle containing exactly k vertices is called a k-cycle. The length of a cycle is defined as the sum of arc lengths used in the cycle. A directed network G  (V,A) with |V| ≥ k is said to be k-symmetric if for every k-cycle v1 →

v2 →· · ·→vk → v1 in G, d12 + d23 +· · ·+dk−1,k + dk1  d1k + dk,k−1 +· · ·+d32 + d21.

In other words, a k-symmetric network is a directed network in which the length of every k-cycle remains unchanged if its orientation is reversed.

(a) Show that the asymmetric Traveling Salesman Problem on a |V |-symmetric network (satisfying the triangle inequality) can be solved via solving a corresponding symmetric Traveling Salesman Problem. In particular, show that any heuristic with fixedworst-case bound for the symmetric Traveling Salesman Problem can be used for the asymmetric Traveling Salesman Problem on a |V |-symmetric network to obtain a result with the same worst-case bound.

(b) Prove that any 3-symmetric network is k-symmetric for k  4, 5, . . . , |V |.

Thus part

(a) can be used if we have a 3-symmetric network. Argue that a 3-

symmetric network can be identified in polynomial time.