We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Solutions for the stable rommates problem with payments.

Biró, P. and Bomhoff, M. and Golovach, P.A. and Kern, W. and Paulusma, Daniel (2012) 'Solutions for the stable rommates problem with payments.', in Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, 26-28 June 2012 ; revised selected papers. Berlin ; Heidelberg: Springer, 69-80 . Lecture notes in computer science., 7551 (9551).


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.

Item Type:Book chapter
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:2012
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar