Finding small stabilizers for unstable graphs
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 5158|
A vertex v of a graph G is called inessential if there exists a maximum matching in G that exposes v. G is said to be stable if the set of its inessential vertices forms a stable set.
Stable graphs play a key role in network bargaining games where we are given a set of players represented as vertices of a graph G, and a set of possible deals between players represented by the edges of G. Kleinberg and Tardos [STOC ’08] defined the notion of a balanced outcome for a network bargaining game, and proved that a balanced outcome exists if and only if the correspondent graph G is stable.
This connection motivates the optimization problem of finding a minimum cardinality stabilizer of a given unstable graph G, that is a subset of edges F such that G\F is stable. In this talk we prove some structural results about this problem and develop efficient approximation algorithms for sparse graphs.
Joint work with A.Bock, K.Chandrasekaran, J.Koenemann, B.Peis
200 University Avenue West
Waterloo, ON N2L 3G1