Finding small stabilizers for unstable graphs

Adrian Bock, Karthekeyan Chandrasekaran, Jochen Könemann, Britta Peis, Laura Sanità

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ⊆ 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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Proceedings
PublisherSpringer
Pages150-161
Number of pages12
ISBN (Print)9783319075563
DOIs
StatePublished - 2014
Externally publishedYes
Event17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014 - Bonn, Germany
Duration: Jun 23 2014Jun 25 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8494 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014
Country/TerritoryGermany
CityBonn
Period6/23/146/25/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Finding small stabilizers for unstable graphs'. Together they form a unique fingerprint.

Cite this