Additive stabilizers for unstable graphs

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.