Stabilizing weighted graphs

Zhuan Khye Koh, Laura Sanità

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Samenvatting

An edge-weighted graph G 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 network bargaining games and cooperative matching games, because they characterize instances that admit stable outcomes. 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 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(Δ)-approximation algorithm for the problem, where Δ is the maximum degree of a node in G.
Originele taal-2Engels
Pagina's (van-tot)1318-1341
Aantal pagina's24
TijdschriftMathematics of Operations Research
Volume45
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - 1 nov 2020

Vingerafdruk

Duik in de onderzoeksthema's van 'Stabilizing weighted graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit