TY - GEN

T1 - Finding small stabilizers for unstable graphs

AU - Bock, Adrian

AU - Chandrasekaran, Karthekeyan

AU - Könemann, Jochen

AU - Peis, Britta

AU - Sanità, Laura

PY - 2014

Y1 - 2014

N2 - An undirected graph G = (V,E) is stable if its inessential vertices (those that are exposed by at least one maximum matching) form a stable set. We call a set of edges F ⊆ E a stabilizer if its removal from G yields a stable graph. In this paper we study the following natural edge-deletion question: given a graph G = (V,E), 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 [19] we are given an undirected graph G = (V,E) where vertices represent players, and we define the value of each subset S ⊆ V as the cardinality of a maximum matching in the subgraph induced by S. The core of such a game contains all fair allocations of the value of V among the players, and is well-known to be non-empty iff graph 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 then prove that there is a minimum-cardinality stabilizer that avoids some maximum matching of G. We use this insight to give efficient approximation algorithms for sparse graphs and for regular graphs.

AB - An undirected graph G = (V,E) is stable if its inessential vertices (those that are exposed by at least one maximum matching) form a stable set. We call a set of edges F ⊆ E a stabilizer if its removal from G yields a stable graph. In this paper we study the following natural edge-deletion question: given a graph G = (V,E), 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 [19] we are given an undirected graph G = (V,E) where vertices represent players, and we define the value of each subset S ⊆ V as the cardinality of a maximum matching in the subgraph induced by S. The core of such a game contains all fair allocations of the value of V among the players, and is well-known to be non-empty iff graph 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 then prove that there is a minimum-cardinality stabilizer that avoids some maximum matching of G. We use this insight to give efficient approximation algorithms for sparse graphs and for regular graphs.

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

U2 - 10.1007/978-3-319-07557-0_13

DO - 10.1007/978-3-319-07557-0_13

M3 - Conference contribution

AN - SCOPUS:84958525722

SN - 9783319075563

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 150

EP - 161

BT - Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Proceedings

PB - Springer

T2 - 17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014

Y2 - 23 June 2014 through 25 June 2014

ER -