Description
EGERVÁRY SZEMINÁRIUM
Abstract: 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.