  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.
