The Asymmetric Travelling Salesman Problem In Sparse Digraphs.

DOI10.4230/LIPICS.IPEC.2020.23MaRDI QIDQ6089670zbMATH OpenOpenAlexFDO

Authors Łukasz Kowalik, Konrad Majewski

Publication date 13 November 2023

Full work available at URL https://arxiv.org/abs/2007.12120

zbMATH Keywords

asymmetric traveling salesman problemexponential algorithmHamiltonian cyclesparse graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Abstract: Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algorithm running in time $O^{\ast }(2^n)$ developed almost 60 years ago by Bellman, Held and Karp, is still the state of the art for both of these problems. In this work we focus on sparse digraphs. First, we recall known approaches for Undirected Hamiltonicity and TSP in sparse graphs and we analyse their consequences for Directed Hamiltonicity and ATSP in sparse digraphs, either by adapting the algorithm, or by using reductions. In this way, we get a number of running time upper bounds for a few classes of sparse digraphs, including $O^{\ast }(2^{n/3})$ for digraphs with both out- and indegree bounded by 2, and $O^{\ast }(3^{n/2})$ for digraphs with outdegree bounded by 3. Our main results are focused on digraphs of bounded average outdegree $d$. The baseline for ATSP here is a simple enumeration of cycle covers which can be done in time bounded by $O^{\ast }(mu(d{)}^n)$ for a function $mu(d)le(lceildceil!{)}^{1/lceildceil}$. One can also observe that Directed Hamiltonicity can be solved in randomized time $O^{\ast }((2-2^{-d}{)}^n)$ and polynomial space, by adapting a recent result of Bj"{o}rklund [ISAAC 2018] stated originally for Undirected Hamiltonicity in sparse bipartite graphs. We present two new deterministic algorithms for ATSP: the first running in time $O(2^{0.441(d-1)n})$ and polynomial space, and the second in exponential space with running time of $O^{\ast }(au(d{)}^{n/2})$ for a function $au(d)led$.

Recommendations

• A note on the complexity of the asymmetric traveling salesman problem
• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• The asymmetric traveling salesman problem on graphs with bounded genus
• The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope on a Directed Graph
• scientific article; zbMATH DE number 4039668
• scientific article; zbMATH DE number 1893558
• Asymmetric traveling salesman path and directed latency problems
• Asymmetric traveling salesman path and directed latency problems
• The Graphical Asymmetric Traveling Salesman Polyhedron: Symmetric Inequalities

Cites work

• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• A polynomial-space exact algorithm for TSP in degree-6 graphs
• A Search Procedure for Hamilton Paths and Circuits
• A short proof of Minc's conjecture
• An improved exact algorithm for TSP in graphs of maximum degree 4
• Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication
• Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
• Determinant sums for undirected Hamiltonicity
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Directed Hamiltonicity and out-branchings via generalized Laplacians
• Dynamic programming meets the principle of inclusion and exclusion
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Expected Computation Time for Hamiltonian Path problem
• Exploiting sparsity for bipartite Hamiltonicity
• Faster exponential-time algorithms in graphs of bounded average degree
• Finding all the perfect matchings in bipartite graphs
• Finding and enumerating Hamilton cycles in 4-regular graphs
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• On the number of Hamilton cycles in bounded degree graphs
• On two techniques of combining branching and treewidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Spotting trees with few leaves
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The Traveling Salesman Problem for Cubic Graphs
• The traveling salesman problem in bounded degree graphs

Cited in

(1)

• An asymptotically fast polynomial space algorithm for Hamiltonicity detection in sparse directed graphs

This page was built for publication: The Asymmetric Travelling Salesman Problem In Sparse Digraphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6089670)