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 contributionAcademicpeer-review

    1 Citation (Scopus)

    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
    Title of host publicationInteger Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Proceedings
    PublisherSpringer
    Pages150-161
    Number of pages12
    ISBN (Print)9783319075563
    DOIs
    Publication statusPublished - 2014
    Event17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014 - Bonn, Germany
    Duration: 23 Jun 201425 Jun 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

    Conference

    Conference17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014
    CountryGermany
    CityBonn
    Period23/06/1425/06/14

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

    Cite this