TY - JOUR

T1 - Exponentiality of the exchange algorithm for finding another room-partitioning

AU - Edmonds, Jack

AU - Sanità, Laura

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Let T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for T is a subset R of the rooms such that each vertex of T is in exactly one room in R. Given a room-partitioning R for T, the exchange algorithm walks from room to room until it finds a second different room-partitioning R′. In fact, this algorithm generalizes the Lemke-Howson 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.

AB - Let T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for T is a subset R of the rooms such that each vertex of T is in exactly one room in R. Given a room-partitioning R for T, the exchange algorithm walks from room to room until it finds a second different room-partitioning R′. In fact, this algorithm generalizes the Lemke-Howson 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.

KW - Exchange algorithm

KW - Room-partitioning

KW - Two-person games

UR - http://www.scopus.com/inward/record.url?scp=84893761704&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2012.03.012

DO - 10.1016/j.dam.2012.03.012

M3 - Article

AN - SCOPUS:84893761704

VL - 164

SP - 86

EP - 91

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - PART 1

ER -