Complementary To Yannakakits’ Theorem

Journal of Combinatorial Mathematics and Combinatorial Computing

The ATSP polytope can be expressed by an asymmetric polynomial-size linear program.

Keywords: Graphs, Digraphs, Computational complexity, Algorithms, DHC, Directed Hamiltonian Cycle, ATSP, Asymmetric Traveling Salesman Problem.