An edge-weighted graph G = (V,E) is called stable if the value of a maximum-weightmatching equals the value of a maximum-weight fractional matching. Stable graphs playan important role in some interesting game theory problems, such as network bargaininggames and cooperative matching games, because they characterize instances which admitstable outcomes. Motivated by this, in the last few years many researchers have investigatedthe algorithmic problem of turning a given graph into a stable one, via edge- and vertex removaloperations. However, all the algorithmic results developed in the literature so faronly 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 ofvertices whose removal from G yields a stable graph, for any weighted graph G. The algorithmis combinatorial and exploits new structural properties of basic fractional matchings,which may be of independent interest. In contrast, we show that the problem of finding aminimum cardinality subset of edges whose removal from a weighted graph G yields a stablegraph, 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 Deltaisthe maximum degree of a node in G.
PDF
download
878987797
028-85220240
