  Patrolling is one of the central problems in operational security. Formally,
a patrolling problem is specified by a set $U$ of nodes (admissible defender's
positions), a set $T \subseteq U$ of vulnerable targets, an admissible
defender's moves over $U$, and a function which to every target assigns the
time needed to complete an intrusion at it. The goal is to design an optimal
strategy for a defender who is moving from node to node and aims at detecting
possible intrusions at the targets. The goal of the attacker is to maximize the
probability of a successful attack. We assume that the attacker is adversarial,
i.e., he knows the strategy of the defender and can observe her moves.
  We prove that the defender has an optimal strategy for every patrolling
problem. Further, we show that for every $\varepsilon$ > 0, there exists a
finite-memory $\varepsilon$-optimal strategy for the defender constructible in
exponential time, and we observe that such a strategy cannot be computed in
polynomial time unless P=NP.
  Then we focus ourselves to unrestricted defender's moves. Here, a patrolling
problem is fully determined by its signature, the number of targets of each
attack length. We bound the maximal probability of successfully defended
attacks. Then, we introduce a decomposition method which allows to split a
given patrolling problem $G$ into smaller subproblems and construct a
defender's strategy for $G$ by "composing" the strategies constructed for these
subproblems.
  Finally, for patrolling problems with $T = U$ and a well-formed signature, we
give an exact classification of all sufficiently connected environments where
the defender can achieve the same value as in the fully connected uniform
environment. This result is useful for designing "good" environments where the
defender can act optimally.
