Euler Tour Lock-In Problem in the Rotor-Router Model

The

rotor-router model

, also called the

Propp machine

, was first considered as a deterministic alternative to the random walk. It is known that the route in an undirected graph

G

 = (

V

,

E

), where |

V

| = 

n

and |

E

| = 

m

, adopted by an agent controlled by the rotor-router mechanism forms eventually an Euler tour based on arcs obtained via replacing each edge in

G

by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the

lock-in problem

. In recent work [11] Yanovski et al. proved that independently of the initial configuration of the rotor-router mechanism in

G

the agent locks-in in time bounded by 2

mD

, where

D

is the diameter of

G

.

In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. The case study is performed in the form of a game between a player

$\cal P$

intending to lock-in the agent in an Euler tour as quickly as possible and its adversary

$\cal A$

with the counter objective. First, we observe that in certain (easy) cases the lock-in can be achieved in time

O

(

m

). On the other hand we show that if adversary

$\cal A$

is solely responsible for the assignment of ports and pointers, the lock-in time Ω(

m

·

D

) can be enforced in any graph with

m

edges and diameter

D

. Furthermore, we show that if

$\cal A$

provides its own port numbering after the initial setup of pointers by

$\cal P$

, the complexity of the lock-in problem is bounded by

O

(

m

· min {log

m

,

D

}). We also propose a class of graphs in which the lock-in requires time Ω(

m

·log

m

). In the remaining two cases we show that the lock-in requires time Ω(

m

·

D

) in graphs with the worst-case topology. In addition, however, we present non-trivial classes of graphs with a large diameter in which the lock-in time is

O

(

m

).