A subexponential algorithm for ARRIVAL

Speaker: Phuc Hung Hoang
Room 3.517 (EGRES seminar)

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 previously best algorithms have runtime 2^\Theta(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(\sqrt{n} log n).

Joint work with Bernd Gärtner and Sebastian Haslebacher.