Exponentiality of the exchange algorithm for finding another room-partitioning ?
Let T T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning  for T T is a subset R R of the rooms such that each vertex of T T is in exactly one room in R R . Given a room-partitioning R R for T T , the exchange algorithm  walks from room to room until it finds a second different room-partitioning R? R ? . In fact, this algorithm generalizes the LemkeHowson algorithm for finding a Nash equilibrium for two-person games. In this paper, we show that the running time of the exchange algorithm is not polynomial relative to the number of rooms, by constructing a sequence of (planar) instances, in which the algorithm walks from room to room an exponential number of times. We also show a similar result for the problem of finding a second perfect matching in Eulerian graphs.
exchange algorithm room-partitioning two-person games