  An edge-weighted graph $G=(V,E)$ is called stable if the value of a
maximum-weight matching equals the value of a maximum-weight fractional
matching. Stable graphs play an important role in some interesting game theory
problems, such as network bargaining games and cooperative matching games,
because they characterize instances which admit stable outcomes. Motivated by
this, in the last few years many researchers have investigated the algorithmic
problem of turning a given graph into a stable one, via edge- and
vertex-removal operations. However, all the algorithmic results developed in
the literature so far only hold for unweighted instances, i.e., assuming unit
weights on the edges of $G$.
  We give the first polynomial-time algorithm to find a minimum cardinality
subset of vertices whose removal from $G$ yields a stable graph, for any
weighted graph $G$. The algorithm is combinatorial and exploits new structural
properties of basic fractional matchings, which are of independent interest. In
particular, one of the main ingredients of our result is the development of a
polynomial-time algorithm to compute a basic maximum-weight fractional matching
with minimum number of odd cycles in its support. This generalizes a
fundamental and classical result on unweighted matchings given by Balas more
than 30 years ago, which we expect to prove useful beyond this particular
application.
  In contrast, we show that the problem of finding a minimum cardinality subset
of edges whose removal from a weighted graph $G$ yields a stable graph, does
not admit any constant-factor approximation algorithm, unless $P=NP$. In this
setting, we develop an $O(\Delta)$-approximation algorithm for the problem,
where $\Delta$ is the maximum degree of a node in $G$.
