## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, April 22, 2021, 12:15 pm

Duration: 30 minutes

Location: Zoom: conference room

Speaker: Hung Hoang

## A Subexponential Algorithm for ARRIVAL

Suppose we run a train on a directed (multi-)graph, where every vertex has out-degree 2 and is equipped with a switch. At the beginning, the switch at each vertex points to one of the two outgoing edges. When the train reaches a vertex, it will traverse along the edge pointed by the switch, and then the switch at that vertex shifts to the other outgoing edge. Given such a graph with an origin vertex o and a destination vertex d, the problem is to decide if the train starting from o can reach d.

The problem above is called ARRIVAL. It is in NP and co-NP, but not known to be in P. The currently best algorithms have runtime 2^ϴ(n) where n is the number of vertices. This is not much better than just performing the pseudorandom walk. In this talk, I will present a subexponential algorithm with runtime 2^O(√n log n).

Joint work with Bernd Gärtner and Sebastian Haslebacher

Information for students and suggested topics for student talks