TY - JOUR

T1 - Finding small stabilizers for unstable graphs

AU - Bock, Adrian

AU - Chandrasekaran, Karthekeyan

AU - Könemann, Jochen

AU - Peis, Britta

AU - Sanità, Laura

PY - 2015/12/1

Y1 - 2015/12/1

N2 - An undirected graph (Formula presented.) is stable if the cardinality of a maximum matching equals the size of a minimum fractional vertex cover. We call a set of edges (Formula presented.) a stabilizer if its removal from (Formula presented.) yields a stable graph. In this paper we study the following natural edge-deletion question: given a graph (Formula presented.), can we find a minimum-cardinality stabilizer? Stable graphs play an important role in cooperative game theory. In the classic matching game introduced by Shapley and Shubik (Int J Game Theory 1(1):111–130, 1971) we are given an undirected graph (Formula presented.) where vertices represent players, and we define the value of each subset (Formula presented.) as the cardinality of a maximum matching in the subgraph induced by (Formula presented.). The core of such a game contains all fair allocations of the value of $$V$$V among the players, and is well-known to be non-empty iff graph $$G$$G is stable. The stabilizer problem addresses the question of how to modify the graph to ensure that the core is non-empty. We show that this problem is vertex-cover hard. We prove that every minimum-cardinality stabilizer avoids some maximum matching of $$G$$G. We use this insight to give efficient approximation algorithms for sparse graphs and for regular graphs.

AB - An undirected graph (Formula presented.) is stable if the cardinality of a maximum matching equals the size of a minimum fractional vertex cover. We call a set of edges (Formula presented.) a stabilizer if its removal from (Formula presented.) yields a stable graph. In this paper we study the following natural edge-deletion question: given a graph (Formula presented.), can we find a minimum-cardinality stabilizer? Stable graphs play an important role in cooperative game theory. In the classic matching game introduced by Shapley and Shubik (Int J Game Theory 1(1):111–130, 1971) we are given an undirected graph (Formula presented.) where vertices represent players, and we define the value of each subset (Formula presented.) as the cardinality of a maximum matching in the subgraph induced by (Formula presented.). The core of such a game contains all fair allocations of the value of $$V$$V among the players, and is well-known to be non-empty iff graph $$G$$G is stable. The stabilizer problem addresses the question of how to modify the graph to ensure that the core is non-empty. We show that this problem is vertex-cover hard. We prove that every minimum-cardinality stabilizer avoids some maximum matching of $$G$$G. We use this insight to give efficient approximation algorithms for sparse graphs and for regular graphs.

KW - Game theory

KW - Matchings

KW - Network bargaining

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

U2 - 10.1007/s10107-014-0854-1

DO - 10.1007/s10107-014-0854-1

M3 - Article

AN - SCOPUS:84946406446

VL - 154

SP - 173

EP - 196

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -