Finding small stabilizers for unstable graphs

• 成果类型: Article
• 署名作者: Bock, Adrian; Chandrasekaran, Karthekeyan; Koenemann, Jochen; Peis, Britta; Sanita, Laura
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Illinois System; University of Illinois Urbana-Champaign; University of Waterloo; RWTH Aachen University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0854-1
• 发表日期: 2015
• 页码: 173-196
• 关键词: Approximation

摘要

An undirected graph is stable if the cardinality of a maximum matching equals the size of a minimum fractional vertex cover. We call a set of edges a stabilizer if its removal from yields a stable graph. In this paper we study the following natural edge-deletion question: given a graph , 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 (Int J Game Theory 1(1):111-130, 1971) we are given an undirected graph where vertices represent players, and we define the value of each subset as the cardinality of a maximum matching in the subgraph induced by . The core of such a game contains all fair allocations of the value of among the players, and is well-known to be non-empty iff graph 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 prove that every minimum-cardinality stabilizer avoids some maximum matching of . We use this insight to give efficient approximation algorithms for sparse graphs and for regular graphs.