Additive stabilizers for unstable graphs

DOI10.1016/J.DISOPT.2018.08.003MaRDI QIDQ2419360zbMATH OpenOpenAlexWikidataFDO

Authors Karthekeyan Chandrasekaran, Corinna Gottschalk, Jochen Könemann, Britta Peis, Daniel Schmand, Andreas Wierz

Publication date 13 June 2019

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.06797

zbMATH Keywords

approximation algorithmGallai-Edmonds decompositiongraph stabilizationhardnessmatchingvertex cover

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Games involving graphs (91A43)

Abstract: Stabilization of graphs has received substantial attention in recent years due to its connection to game theory. Stable graphs are exactly the graphs inducing a matching game with non-empty core. They are also the graphs that induce a network bargaining game with a balanced solution. A graph with weighted edges is called stable if the maximum weight of an integral matching equals the cost of a minimum fractional weighted vertex cover. If a graph is not stable, it can be stabilized in different ways. Recent papers have considered the deletion or addition of edges and vertices in order to stabilize a graph. In this work, we focus on a fine-grained stabilization strategy, namely stabilization of graphs by fractionally increasing edge weights. We show the following results for stabilization by minimum weight increase in edge weights (min additive stabilizer): (i) Any approximation algorithm for min additive stabilizer that achieves a factor of $O(|V{|}^{1/24-epsilon})$ for $epsilon>0$ would lead to improvements in the approximability of densest-$k$-subgraph. (ii) Min additive stabilizer has no $o(log|V|)$ approximation unless NP=P. Results (i) and (ii) together provide the first super-constant hardness results for any graph stabilization problem. On the algorithmic side, we present (iii) an algorithm to solve min additive stabilizer in factor-critical graphs exactly in poly-time, (iv) an algorithm to solve min additive stabilizer in arbitrary-graphs exactly in time exponential in the size of the Tutte set, and (v) a poly-time algorithm with approximation factor at most $sqrt|V|$ for a super-class of the instances generated in our hardness proofs.

Recommendations

• Stabilizing weighted graphs
• Stabilizing weighted graphs
• Stabilizing network bargaining games by blocking players
• Finding small stabilizers for unstable graphs
• Finding small stabilizers for unstable graphs

Cites work

• Algorithmic Game Theory
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Analytical approach to parallel repetition
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms.
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Efficient stabilization of cooperative matching games
• Every Monotone Graph Property Is Testable
• Finding small stabilizers for unstable graphs
• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• scientific article; zbMATH DE number 5485541 (Why is no real title available?)
• scientific article; zbMATH DE number 3557552 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 3437188 (Why is no real title available?)
• scientific article; zbMATH DE number 3220175 (Why is no real title available?)
• scientific article; zbMATH DE number 3313442 (Why is no real title available?)
• Integer and Fractional Matchings
• Maximum matching and a polyhedron with 0,1-vertices
• Multiagent Systems
• Networks, crowds and markets. Reasoning about a highly connected world.
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Social and economic networks.
• Solutions for the stable roommates problem with payments
• Stabilizing network bargaining games by blocking players
• The assignment game. I: The core
• The bargaining problem
• The complexity of König subgraph problems and above-guarantee vertex cover
• The cooperative game theory foundations of network bargaining games
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Vertex packings: Structural properties and algorithms

Cited in

(8)

• The stable fixtures problem with payments
• Stabilizing weighted graphs
• Stabilizing weighted graphs
• Finding small stabilizers for unstable graphs
• Stabilization of capacitated matching games
• The complexity of matching games: a survey
• Stabilization of capacitated matching games
• Finding small stabilizers for unstable graphs

This page was built for publication: Additive stabilizers for unstable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419360)