License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2020.23
URN: urn:nbn:de:0030-drops-133269
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13326/
Kowalik, Łukasz ;
Majewski, Konrad
The Asymmetric Travelling Salesman Problem In Sparse Digraphs
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 ?^*(2ⁿ) 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 ?^*(2^(n/3)) for digraphs with both out- and indegree bounded by 2, and ?^*(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 ?^*(μ(d)ⁿ) for a function μ(d) ≤ (⌈d⌉!)^(1/⌈d⌉). One can also observe that Directed Hamiltonicity can be solved in randomized time ?^*((2-2^(-d))ⁿ) and polynomial space, by adapting a recent result of Bjö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 ?(2^(0.441(d-1)n)) and polynomial space, and the second in exponential space with running time of ?^*(τ(d)^(n/2)) for a function τ(d) ≤ d.
BibTeX - Entry
@InProceedings{kowalik_et_al:LIPIcs:2020:13326,
author = {Łukasz Kowalik and Konrad Majewski},
title = {{The Asymmetric Travelling Salesman Problem In Sparse Digraphs}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {23:1--23:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-172-6},
ISSN = {1868-8969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13326},
URN = {urn:nbn:de:0030-drops-133269},
doi = {10.4230/LIPIcs.IPEC.2020.23},
annote = {Keywords: asymmetric traveling salesman problem, Hamiltonian cycle, sparse graphs, exponential algorithm}
}
|
Keywords: |
|
asymmetric traveling salesman problem, Hamiltonian cycle, sparse graphs, exponential algorithm |
|
Collection: |
|
15th International Symposium on Parameterized and Exact Computation (IPEC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
