Solutions for the stable roommates problem with payments

Péter Biró, M.J. Bomhoff, Petr A. Golovach, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (Scopus)
31 Downloads (Pure)

Abstract

The stable roommates problem with payments has as input a graph G = (V , E ) with an edge weighting w : E → R≥0 and the problem is to find a stable solution. By pinpointing a relationship to the accessibility of the coalition structure core of matching games, we give a 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 generalizes a result of Chen, Fujishige and Yang (2011) [4] 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.
Original languageUndefined
Pages (from-to)53-61
Number of pages9
JournalTheoretical computer science
Volume540-541
DOIs
Publication statusPublished - 26 Jun 2014

Keywords

  • Stable roommates
  • EWI-25927
  • IR-95673
  • Game Theory
  • METIS-312547
  • Blocking pairs

Cite this