  Muller games are played by two players moving a token along a graph; the
winner is determined by the set of vertices that occur infinitely often. The
central algorithmic problem is to compute the winning regions for the players.
Different classes and representations of Muller games lead to problems of
varying computational complexity. One such class are parity games; these are of
particular significance in computational complexity, as they remain one of the
few combinatorial problems known to be in NP and co-NP but not known to be in
P. We show that winning regions for a Muller game can be determined from the
alternating structure of its traps. To every Muller game we then associate a
natural number that we call its trap-depth; this parameter measures how
complicated the trap structure is. We present algorithms for parity games that
run in polynomial time for graphs of bounded trap depth, and in general run in
time exponential in the trap depth.
