Skip to main content

Research Repository

Advanced Search

Solutions for the stable rommates problem with payments

Biró, P.; Bomhoff, M.; Golovach, P. A.; Kern, W.; Paulusma, D.

Authors

P. Biró

M. Bomhoff

P. A. Golovach

W. Kern



Contributors

Martin Charles Golumbic
Editor

Michal Stern
Editor

Avivit Levy
Editor

Gila Morgenstern
Editor

Abstract

The stable roommates problem with payments has as input a graph G = (V,E) with an edge weighting w: E → ℝ +  and the problem is to find a stable solution. A solution is a matching M with a vector p∈R V + that satisfies pu + pv = w(uv) for all uv ∈ M and pu = 0 for all u unmatched in M. A solution is stable if it prevents blocking pairs, i.e., pairs of adjacent vertices u and v with pu + pv < w(uv). By pinpointing a relationship to the accessibility of the coalition structure core of matching games, we give a simple constructive proof for showing that every yes-instance of the stable roommates problem with payments allows a path of linear length that starts in an arbitrary unstable solution and that ends in a stable solution. This result generalizes a result of Chen, Fujishige and Yang for bipartite instances to general instances. We also show that the problems Blocking Pairs and Blocking Value, which are to find a solution with a minimum number of blocking pairs or a minimum total blocking value, respectively, are NP-hard. Finally, we prove that the variant of the first problem, in which the number of blocking pairs must be minimized with respect to some fixed matching, is NP-hard, whereas this variant of the second problem is polynomial-time solvable.

Citation

Biró, P., Bomhoff, M., Golovach, P. A., Kern, W., & Paulusma, D. (2012). Solutions for the stable rommates problem with payments. In M. C. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, 26-28 June 2012 ; revised selected papers (69-80). https://doi.org/10.1007/978-3-642-34611-8_10

Publication Date 2012
Deposit Date Mar 11, 2013
Volume 7551
Pages 69-80
Series Title Lecture notes in computer science
Series Number 9551
Series ISSN 0302-9743,1611-3349
Book Title Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, 26-28 June 2012 ; revised selected papers.
ISBN 9783642346101
DOI https://doi.org/10.1007/978-3-642-34611-8_10
Public URL https://durham-repository.worktribe.com/output/1156309
Additional Information Series: Lecture Notes in Computer Science, Volume 7551


You might also like



Downloadable Citations