Additive stabilizers for unstable graphs

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

Research output: Contribution to journalArticlepeer-review

Abstract

A weighted graph is called stable if the maximum weight of an integral matching equals the cost of a minimum-weight fractional vertex cover. We address the following question: how can we modify a given unstable graph in the least intrusive manner in order to achieve stability? Previous works have addressed stabilization through addition or deletion of the smallest possible number of edges/vertices. In this work we investigate the following more fine-grained additive stabilization strategy: given a graph G=(V,E) with unit edge weights; find non-negative c∈R E with minimum ∑ e c e such that adding c e to the unit edge weight of each e∈E yields a stable graph. We provide the first super-constant hardness of approximation results for any graph stabilization problem: (i) unless the current best-known algorithm for the densest- k-subgraph problem can be improved, there is no o(|V| 1∕24 )-approximation for additive stabilizers; (ii) the additive stabilizer problem has no o(log|V|) approximation unless P=NP. On the algorithmic side, we present (iii) a polynomial time algorithm with approximation factor at most |V| for a super-class of the instances generated in our hardness proofs, (iv) an algorithm to solve min additive stabilizer in factor-critical graphs exactly in polynomial time, and (v) an algorithm to solve min additive stabilizer in arbitrary graphs exactly in time exponential in the size of the Tutte set. Our main tools are the Gallai–Edmonds decomposition and structural results for the problem that reduce the continuous decision domain to a discrete decision domain.

Original languageEnglish (US)
Pages (from-to)56-78
Number of pages23
JournalDiscrete Optimization
Volume31
DOIs
StatePublished - Feb 2019

Keywords

  • Approximation algorithm
  • Gallai–Edmonds decomposition
  • Graph stabilization
  • Hardness
  • Matching
  • Vertex cover

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

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

Cite this