A quasi-polynomial algorithm for well-spaced hyperbolic TSP: arxiv.org/abs/2002.05414

This new preprint by Sándor Kisfaludi-Bak (accepted to SoCG) just came out and caught my attention. TSP is NP-hard for Euclidean points or close-together hyperbolic points. This paper shows that it's much easier when the points are widely spaced in the hyperbolic plane. The idea is to separate the input by a short line segment that the solution crosses few times and apply dynamic programming.


This is the second time I read about a problem becoming easier in hyperbolic space. I forgot the other one, I'll have to hunt for it! I can see what's happening with TSP here - there must be more problems like this! Thanks for inspiring!


@RefurioAnachro I'm going to email my senators and representatives today. It's the 21st century! We need to get this country on a hyperbolic metric already!

@RefurioAnachro The other one that comes to mind for me is greedy embedding (en.wikipedia.org/wiki/Greedy_e) where every graph has one in the hyperbolic plane but not even a six-leaf star has one in the Euclidean plane.

Thanks, @11011110, that wasn't it, so there should be yet another one :) I'll make sure to tag you when I my collection grows.

Sign in to participate in the conversation

Everyone is welcome as long as you follow our code of conduct! Thank you. Mastodon.cloud is maintained by Sujitech, LLC.