P. Biró
Solutions for the stable rommates problem with payments
Biró, P.; Bomhoff, M.; Golovach, P. A.; Kern, W.; Paulusma, D.
Authors
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
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search