
News
Colloquia
Finding Small Stabilizers for Unstable Graphs
Speaker: Jochen Konemann
University of Waterloo
January 27, 2014  4:00 p.m. to 5:00 p.m.
Location: Ricketts 211
Hosted By: Dr. Elliot Anshelevich (x6941)
Abstract:
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 a stabilizer if its removal from G yields a stable graph. In this talk we study the following natural edgedeletion question: given a graph G, can we find a minimumcardinality stabilizer?
Stable graphs play an important role in cooperative game theory. In the classic matching game introduced by Shapley and Shubik we are given an undirected graph G where vertices represent players, and we define the value of each subset S of vertices 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 wellknown to be nonempty iff graph G is stable. The minimum stabilizer problem addresses the question of how to modify the graph to ensure that the core is nonempty.
We show that this problem is vertexcover hard. We then prove that there is a minimumcardinality stabilizer that avoids some maximummatching of G. We employ this insight to give efficient approximation algorithms for sparse graphs, and for regular graphs.
Joint work with A. Bock, K. Chandrasekaran, B. Peis and L. Sanita
Last updated: January 16, 2014

