How hard is it to satisfy (almost) all roommates?∗
Jiehua Chen

Danny Hermelin
Harel Yedidsion

Manuel Sorge

arXiv:1707.04316v3 [cs.CC] 20 Feb 2018

Ben-Gurion University of the Negev, Beer Sheva, Israel
jiehua.chen2@gmail.com, hermelin@bgu.ac.il,
sorge@post.bgu.ac.il, yedidsio@post.bgu.ac.il

Abstract
The classic Stable Roommates problem (which is the non-bipartite generalization
of the well-known Stable Marriage problem) asks whether there is a stable matching
for a given set of agents, i.e. a partitioning of the agents into disjoint pairs such that no
two agents induce a blocking pair. Herein, each agent has a preference list denoting who
it prefers to have as a partner, and two agents are blocking if they prefer to be with each
other rather than with their assigned partners.
Since stable matchings may not be unique, we study an NP-hard optimization variant
of Stable Roommates, called Egalitarian Stable Roommates, which seeks to find
a stable matching with a minimum egalitarian cost γ, i.e. the sum of the dissatisfaction of
the agents is minimum. The dissatisfaction of an agent is the number of agents that this
agent prefers over its partner if it is matched; otherwise it is the length of its preference list.
We also study almost stable matchings, called Min-Block-Pair Stable Roommates,
which seeks to find a matching with a minimum number β of blocking pairs. Our main
result is that Egalitarian Stable Roommates parameterized by γ is fixed-parameter
tractable, while Min-Block-Pair Stable Roommates parameterized by β is W[1]-hard,
even if the length of each preference list is at most five.

∗
This work is supported by the People Programme (Marie Curie Actions) of the European Union’s Seventh
Framework Programme (FP7/2007-2013) under REA grant agreement number 631163.11 and Israel Science
Foundation (grant no. 551145/14).

1

Introduction

This paper presents algorithms and hardness results for two variants of the Stable Roommates
problem, a well-studied generalization of the classic Stable Marriage problem. Before going
into describing our results, we give a brief background that will help motivate our work.
Stable Marriage and Stable Roommates An instance of the Stable Marriage problem
consists of two disjoint sets of n men and n women (collectively called agents), who are each
equipped with his or her own personal strict preference list that ranks every member of the opposite sex. The goal is to find a bijection, or matching, between the men and the women that does
not contain any blocking pairs. A blocking pair is a pair of man and woman who are not matched
together but both prefer each other over their own matched partner. A matching with no blocking pairs is called a stable matching, and perfect if it is a bijection between all men and women.
Stable Marriage is a classic and fundamental problem in computer science and applied
mathematics, and as such, entire books were devoted to it [27, 35, 53, 40]. The problem emerged
from the economic field of matching theory, and it can be thought of as a generalization of
the Maximum Matching problem when restricted to complete bipartite graphs. The most
important result in this context is the celebrated Gale-Shapley algorithm [25]: This algorithm
computes in polynomial time a perfect stable matching in any given instance, showing that
regardless of their preference lists, there always exists a perfect stable matching between any
equal number of men and women.
The Stable Marriage problem has several interesting variants. First, the preference lists
of the agents may be incomplete, meaning that not every agent is an acceptable partner to
every agent of the opposite sex. In graph theoretic terms, this corresponds to the bipartite
incomplete case. The preference lists could also have ties, meaning that two or more agents
may be considered equally good as partners. Finally, the agents may not be partitioned into
two disjoint sets, but rather each agent may be allowed to be matched to any other agent.
This corresponds to the non-bipartite case in graph theoretic terms, and is referred to in the
literature as the Stable Roommates problem.
While Stable Marriage and Stable Roommates seem very similar, there is quite a big
difference between them in terms of their structure and complexity. For one, any instance of
Stable Marriage always contains a stable matching (albeit perhaps not perfect), even if the
preference lists are incomplete and with ties. Moreover, computing some stable matching in
any Stable Marriage instance with 2n agents can be done in O(n2 ) time [25]. However,
an instance of Stable Roommates may have no stable matchings at all, even in the case
of complete preference lists without ties (see the third example in Figure 1). Furthermore,
when ties are present, deciding whether an instance of Stable Roommates contains a stable
matching is NP-complete [52], even in the case of complete preference lists.
All variants of Stable Marriage and Stable Roommates mentioned here have several
applications in a wide range of application domains. These include partnership issues in the
real-world [25], resource allocation [5, 16, 30], centralized automated mechanisms that assign
children to schools [3, 4], assigning school graduates to universities [7, 9], assigning medical
students to hospitals [1, 2], and several others [6, 24, 32, 33, 36, 37, 38, 40, 41, 54, 55].
Optimization variants As noted above, some Stable Roommates instances do not admit
any stable matching at all, and in fact, empirical study suggests that a constant fraction of
all sufficiently large instances will have no solution [50]. Moreover, even if a given Stable
Roommates instance admits a solution, this solution may not be unique, and there might
be other stable matchings with which the agents are more satisfied overall. Given these two
facts, it makes sense to consider two types of optimization variants for Stable Roommates:
In one type, one would want to compute a stable matching that optimizes a certain social

1

1:
2:
3:
4:

2
3
4
1

≻
≻
≻
≻

3 ≻ 4 1
1
2
4
2 ≻ 1
3
3

1:
2:
3:
4:

2
1
1
3

∼
≻
∼
≻

1
3 ≻ 4
3
2
4
2 ≻ 4
3
1

1:
2:
3:
4:

2
3
1
1

≻
≻
≻
≻

3
1
2
2

≻
≻
≻
≻

1
4
4 2
4
4
3
3

Figure 1: An example of three Stable Roommates instances, where x ≻ y means that x
is strictly preferred to y, and x ∼ y means that they are equally good and tied as a partner. The instance on the left is incomplete without ties and has exactly two stable matchings
{{1, 2}, {3, 4}} and {{1, 4}, {2, 3}}, both of which are perfect. The instance in the middle is
incomplete with ties and has two stable matchings {{1, 3}} and {{1, 2}, {3, 4}}, the latter being
perfect while the former not. The right instance is complete without ties and has no stable
matchings at all.
criteria in order to maximize the overall satisfaction of the agents. In the other, one would want
to compute matchings which are as close as possible to being stable, where closeness can be
measured by various metrics. In this paper, we focus on one prominent example of each of these
two types—minimizing the egalitarian cost of a stable matching, and minimizing the number
of blocking pairs in a matching which is close to being stable.
Egalitarian optimal stable matchings. Over the years, several social optimality criteria
have been considered, yet arguably one of the most popular of these is the egalitarian cost
metric [44, 35, 34, 39, 42]. The egalitarian cost of a given matching is the sum of the rank s
of the partners of all agents, where the rank of the partner y of an agent x is the number
of agents that are strictly preferred over y by x. The corresponding Egalitarian Stable
Marriage and Egalitarian Stable Roommates problems ask whether there is a stable
matching with egalitarian cost at most γ, for some given bound γ ∈ N (Section 2 contains the
formal definition).
When the input preferences do not have ties (but could be incomplete), Egalitarian
Stable Marriage is solvable in O(n4 ) time [34]. For preferences with ties, Egalitarian
Stable Marriage becomes NP-hard [39]. Thus, already in the bipartite case, it becomes
apparent that allowing ties in preference lists makes the task of computing an optimal egalitarian
matching much more challenging. Marx and Schlotter [42] showed that Egalitarian Stable
Marriage is fixed-parameter tractable when parameterized by the parameter “sum of the
lengths of all ties”.
For Egalitarian Stable Roommates, Feder [22] showed that the problem is NP-hard
even if the preferences are complete and have no ties, and gave a 2-approximation algorithm for
this case. Halldórsson et al. [28] showed inapproximability results for Egalitarian Stable
Roommates, and Teo and Sethuraman [56] proposed a specific LP formulation for Egalitarian Stable Roommates and other variants. Cseh et al. [19] studied Egalitarian Stable
Roommates for preferences with bounded length ℓ and without ties. They showed that the
problem is polynomial-time solvable if ℓ = 2, and is NP-hard for ℓ ≥ 3.
Matchings with minimum number of blocking pairs. For the case where no stable
matchings exist, the agents may still be satisfied with a matching that is close to being stable.
One very natural way to measure how close a matching is to being stable is to count the number
of blocking pairs [48, 21]. Accordingly, the Min-Block-Pair Stable Roommates problem
asks to find a matching with a minimum number of blocking pairs.
Abraham et al. [6] showed that Min-Block-Pair Stable Roommates is NP-hard, and
cannot be approximated within a factor of n0.5−ε unless P = NP, even if the given preferences
are complete. They also showed that the problem can be solved in nO(β) time, where n and

2

β denote the number of agents and the number of blocking pairs, respectively. This implies
that the problem is in the XP class (for parameter β) of parameterized complexity. Biró et al.
[11] showed that the problem is NP-hard and APX-hard even if each agent has a preference
list of length at most 3, and presented a (2ℓ − 3)-approximation algorithm for bounded list
length ℓ. Biró et al. [10] and Hamada et al. [29] showed that the related variant of Stable
Marriage, where the goal is to find a matching with minimum blocking pairs among all
maximum-cardinality matchings, cannot be approximated within n1−ε unless P = NP.
Our contributions We analyze both Egalitarian Stable Roommates and Min-BlockPair Stable Roommates from the perspective of parameterized complexity, under the natural
parameterization of each problem (i.e. the egalitarian cost and number of blocking pairs, respectively). We show that while the former is fixed-parameter tractable, the latter is W[1]-hard
even when each preference list has length at most five and has no ties. This shows a sharp
contrast between the two problems: Computing an optimal egalitarian stable matching is a
much easier task than computing a matching with minimum blocking pairs.
When no ties are present, an instance of the Egalitarian Stable Roommates problem
has a lot of structure, and so we can apply a simple branching strategy for finding a stable
matching with egalitarian cost of at most γ in 2O(γ) n2 time. Moreover, we derive a kernelization
algorithm, obtaining a polynomial problem kernel (Theorems 3 and 4). Note that the original
reduction of Feder [22] already shows that Egalitarian Stable Roommates cannot be solved
in 2o(γ) nO(1) time unless the Exponential Time Hypothesis [20] fails.
When ties are present, the problem becomes much more challenging because several agents
may be tied as a first ranked partner and it is not clear how to match them to obtain an
optimal egalitarian stable matching. Moreover, we have to handle unmatched agents. When
preferences are complete or without ties, all stable matchings match the same (sub)set of agents
and this subset can be found in polynomial time [27, Chapter 4.5.2]. Thus, unmatched agents
do not cause any real difficulties. However, in the case of ties and with incomplete preferences,
stable matchings may involve different sets of unmatched agents. Aiming at a socially optimal
egalitarian stable matching, we consider the cost of an unmatched agent to be the length of its
preference list [42]. (For the sake of completeness, we also consider two other variants where the
cost of an unmatched agent is either zero or a constant value, and show that both these variants
are unlikely to be fixed-parameter tractable.) Our first main result is given in the following
theorem:
3

Theorem 1. Egalitarian Stable Roommates can be solved in 2O(γ ) · n3 · (log n)3 time,
even for incomplete preferences with ties, where n denotes the number of agents and γ denotes
the egalitarian cost.
The general idea behind our algorithm is to apply random separation [14] to “separate”
irrelevant pairs from the pairs that belong to the solution matching, and from some other pairs
that would not block our solution. This is done in two phases, each involving some technicalities,
but in total the whole separation can be computed in γ O(γ) · nO(1) time. After the separation
step, the problem reduces to Minimum-Weight Perfect Matching, and we can apply known
techniques. Recall that for the case where the preferences have no ties, a simple depth-bounded
search tree algorithm suffices (Theorem 4).
In Section 4, we show that Min-Block-Pair Stable Roommates is W[1]-hard with respect to the parameter β (the number of the blocking pairs) even if each input preference list
has length at most five and does not have ties. This implies that assuming bounded length of
the preferences does not help in designing an f (β) · nO(1) -time algorithm for Min-Block-Pair
Stable Roommates, unless FPT = W[1]. Our W[1]-hardness result also implies as a corollary
a lower-bound on the running time of any algorithm. By adapting our reduction, we also answer

3

Objective
Parameter

Without ties

With ties

O(n2 ) [31]

NP-c [52]

Any stable matching

Egalitarian Stable Roommates
NP-c [22]
Egalitarian cost γ
Unmatched agents’ costs = pref. list length O(2γ · n2 ), size-O(γ 2 ) kern. [T. 3+4]⋆
Unmatched agents’ costs = 0
O(2γ · n2 ), size-O(γ 2 ) kern. [T. 3+4]⋆
Unmatched agents’ costs = a constant
O(2γ · n2 ), size-O(γ 2 ) kern. [T. 3+4]⋆
Min-Block-Pair Stable Roommates
#Blocking pairs β
Min-Block-Agents Stable Roommates
#Blocking agents η

NP-c [6], NP-c (ℓ = 3) [11]
n2·β+2 [6], W[1]-h (ℓ = 5) [T. 2]⋆
2
O(2η

·

NP-h [C. 1]⋆
W[1]-h (ℓ = 5) [C. 1]⋆

nη+2 ),

NP-c [52]
γ O(γ) · nO(1) [T. 1]⋆
NP-h (γ = 0) [T. 5]⋆
W[1]-h [T. 6], XP [P. 2]⋆
NP-c (β = 0) [52]
NP-c (β = 0) [52]
NP-c (η = 0) [52]
NP-c (η = 0) [52]

Table 1: Classical and parameterized complexity results of Egalitarian Stable Roommates, Min-Block-Pair Stable Roommates, and Min-Block-Agents Stable Roommates. Herein, n denotes the number of agents. Results marked in bold and with ⋆ are
obtained in this paper. “W[1] (ℓ = 5)” means that the W[1]-hardness (for the respective parameter) holds even if each input preference list has length at most five.
in the negative an open question regarding the number of blocking agents proposed by Manlove
[40, Chapter 4.6.5] (Corollary 1).
Theorem 2. Let n denote the number of agents and β denote the number of blocking pairs.
Even when each input preference list has length at most five and has no ties, Min-Block-Pair
Stable Roommates is W[1]-hard with respect to β and admits no f (β) · no(β) -time algorithms
unless the Exponential Time Hypothesis is false.
Our results are summarized in Table 1.
Besides the relevant work mentioned above there is a growing body of research regarding the
parameterized complexity of preference-based stable matching problems [42, 43, 46, 45, 26, 15].

2

Definitions and notations

We introduce necessary concepts and notation for the paper. Let V = {1, 2, . . . , n} be a set of
even number n agents. Each agent i ∈ V has a subset of agents Vi ⊆ V which it finds acceptable
as a partner and has a preference list i on Vi (i.e. a transitive and complete binary relation on
Vi ). Here, x i y means that i weakly prefers x over y (i.e. x is better or as good as y). We use
≻i to denote the asymmetric part (i.e. x i y and ¬(y i x)) and ∼i to denote the symmetric
part of i (i.e. x i y and y i x). For two agents x and y, we call x most acceptable to y if
x is a maximal element in the preference list of y. Note that an agent can have more than one
most acceptable agent. For two disjoint subsets of agents X ⊆ V and Y ⊆ V , X ∩ Y 6= ∅, we
write X  Y if for each pair of agents x ∈ X and y ∈ Y we have x  y.
A preference profile P for V is a collection (i )i∈V of preference lists for each agent i ∈ V .
A profile P may have the following properties: It is complete if for each agent i ∈ V it holds
that Vi ∪ {i} = V ; otherwise it is incomplete. The profile P has ties if there is an agent i ∈ V
for which there are two agents x, y ∈ Vi such that x ∼i y and we say that x and y are tied
by i.To an instance (V, P) we assign an acceptability graph, which has V as its vertex set
and two agents are connected by an edge if each finds the other acceptable. Without loss of
generality, G does not contain isolated vertices, meaning that each agent has at least one agent
which it finds acceptable. The rank of an agent i in the preference list of some agent j is the
number of agents x that j strictly prefers over i: rankj (i) := |{x | x ≻j i}|.
Given a preference profile P for a set V of agents, a matching M ⊆ E(G) is a subset of
disjoint pairs {x, y} of agents with x 6= y (or edges in E(G)), where E(G) is the set of edges
4

in the corresponding acceptability graph G. For a pair {x, y} of agents, if {x, y} ∈ M , then we
denote the corresponding partner y by M (x); otherwise we call this pair unmatched. We write
M (x) = ⊥ if agent x has no partner ; i.e. if agent x is not involved in any pair in M . If no
agent x has M (x) = ⊥ then M is perfect.
Given a matching M of P, an unmatched pair {x, y} ∈ E(G) \ M is blocking M if both x
and y prefer each other to being unmatched or to their
 assigned partners, i.e. it holds that
M (x) = ⊥ ∨ y ≻x M (x) ∧ M (y) = ⊥ ∨ x ≻y M (y) . We call a matching M stable if no
unmatched pair is blocking M . The Stable Roommates problem is defined as follows:
Stable Roommates
Input: A preference profile P for a set V = {1, 2, . . . , n} of n agents with n being
even.
Question: Does P admit a stable matching?
By the definition of stability, a stable matching for an instance with complete preferences must
assign a partner to each agent. This leads to the following observation. By our definition of
stability, a stable matching for complete preferences must assign a partner to each agent.
Observation 1. Each stable matching in a Stable Roommates instance with complete preferences is perfect.
The two problems we consider in the paper are Egalitarian Stable Roommates and
Min-Block-Pair Stable Roommates. The latter asks to determine whether a given preference profile P for a set of agents V has a stable matching with at most β blocking pairs. The
former problem asks to find a stable matching with P
minimum egalitarian cost; the egalitarian
cost of a given matching M is as follows: γ(M ) := i∈V ranki (M (i)), where we augment the
definition rank with ranki (⊥) := |Vi |. For example, the second profile in Figure 1 has two stable
matchings M1 = {{1, 3}} and M2 = {{1, 2}, {3, 4}} with γ(M1 ) = 4 and γ(M2 ) = 2.
The egalitarian cost, as originally introduced for the Stable Marriage problem, does not
include the cost of an unmatched agent because the preference lists are complete. For complete
preferences, a stable matching must assign a partner to each agent (Observation 1), meaning
that our notion of egalitarian cost equals the one used in the literature. For preferences without
ties, all stable matchings match the same subset of agents [27, Chapter 4.5.2]. Thus, the two
concepts differ only by a fixed value which can be pre-determined in polynomial time [27,
Chapter 4.5.2]. For incomplete preferences with ties, there seems to be no consensus on whether
to “penalize” stable matchings by the cost of unmatched agents [19]. Our concept of egalitarian
cost complies with Marx and Schlotter [42], but we tackle other concepts as well (Section 3.3).

3

Minimizing the egalitarian cost

In this section we give our algorithmic and hardness results for Egalitarian Stable Roommates. Section 3.1 treats the case when no ties are present, where we can use a straightforward
branching strategy. In Section 3.2 we solve the case where ties are present. Herein, we need
a more sophisticated approach based on random separation. Finally, in Section 3.3, we study
variants of the egalitarian cost, differing in the cost assigned to unmatched agents.

3.1

Warm-up: Preferences without ties

By the stability concept, if the preferences have no ties and two agents x and y that are each
other’s most acceptable agents (i.e. rankx (y) = ranky (x) = 0), then any stable matching must
contain the pair {x, y}, which has cost zero. Hence, we can safely add such pairs to a solution
matching. After we have matched all pairs of agents with zero cost, all remaining, unmatched
agents induce cost at least one when they are matched. This leads to a simple depth-bounded
branching algorithm. In terms of kernelization, we can delete any two agents that are most
5

acceptable to each other (i.e. they induce zero cost) and delete agents from some preference list
that are ranked higher than γ. This gives us a polynomial kernel.
First, we recall a part of the polynomial-time algorithm by Irving [31] which finds an
arbitrary stable matching in a Stable Roommates instance without ties if one exists. The
whole algorithm works in two phases. We present here a modified version of the first phase
to determine “relevant” agents by sorting out fixed pairs—pairs of agents that occur in every
stable matching [27, Chapter 4.4.2]—and marked pairs—pairs of agents that cannot occur in
any stable matching. We note that the first phase of Irving [31]’s algorithm deletes marked
pairs, but we will keep them, because they are important for maintaining the egalitarian cost.
The modified phase-1 algorithm is given in Algorithm 1. Herein, by marking a pair {u, w} we
mean marking the agents u and w in the preference lists of w and u, respectively.

Algorithm 1: A modified version of the phase-1 algorithm of Irving [31] (the complete
algorithm finds a stable matching in a Stable Roommates instance without ties, if one
exists).

4

repeat
foreach agent u ∈ U whose preference list contains at least one unmarked agent do
w ← the first agent in the preference list of u such that {u, w} is not yet marked
foreach u′ with u ≻w u′ do mark {u′ , w}

5

until no new pair was marked in the last iteration

1
2
3

For an illustration, consider the following profile with ten agents.
Example 1. The following profile, ignoring the underlines of the agents in the preference lists,
has ten agents with preference lists that do not have ties but may be incomplete.
agent 1 : 6 ≻ 2 ≻ 7 ≻ 4 ≻ 10 ≻ 3 ≻ 5 ≻ 8 ≻ 9, agent 6 : 2 ≻ 3 ≻ 1 ≻ 8,
agent 2 : 7 ≻ 8 ≻ 6 ≻ 1,

agent 7 : 3 ≻ 1 ≻ 8 ≻ 2,

agent 3 : 8 ≻ 6 ≻ 1 ≻ 7,

agent 8 : 2 ≻ 6 ≻ 7 ≻ 3 ≻ 1,

agent 4 : 1,

agent 9 : 1,

agent 5 : 10 ≻ 1,

agent 10 : 5 ≻ 1.

Our modified version of the phase-1 algorithm marks a subset of the agents, indicated by the
underlines. These markings are used to keep track of pairs that do not belong to any stable
matching. Now, observe that both agents 4 and 9 have preference lists that consist only of
marked agents. By the results of Gusfield and Irving [27], we can conclude that no stable
matching will assign any partner to agent 4 or 9.
Let p = {5, 10}. One can verify that the above profile has exactly two stable matchings M1 =
{{1, 6}, {2, 7}, {3, 8}, p} and M2 = {{1, 7}, {2, 8}, {3, 6}, p}. Observe that the pair p exists in
every stable matching as they are each other’s most acceptable agents that are available for them.
Hence, by definition p is a fixed pair. The egalitarian costs of M1 and M2 are γ(M1 ) = 10 and
γ(M2 ) = 8, where the unmatched agents 4 and 9 have each contribute a cost of one which is
the length of their preference lists.
Let P0 be the preference profile produced by the phase-1 algorithm shown in Algorithm 1.
For each agent x, let first(P0 , x) and last(P0 , x) denote the first and the last agent in the
preference list of x that are not marked, respectively. Then, the following shows that we can
ignore irrelevant agents whose preference lists consists of only marked agents.
Proposition 1. [27, Chapters 4.4.2 and 4.5.2] For each two agents x and y in the phase-1
profile P0 , the following holds.
(1) If first(P0 , x) = y, then last(P0 , y) = x.
6

(2) If first(P0 , x) = y and first(P0 , y) = x, then {x, y} exists in every stable matching.
(3) If the preference list of x consists of only marked agents, then no stable matching assigns a
partner to x.
(4) If the preference list of x has some unmarked agent, then every stable matching must assign
some partner to agent x.
(5) No stable matching contains a pair that is marked.
(6) No marked pair is blocking any matching that consist of only unmarked pairs.
By Proposition 1(1), the fixed pairs are those pairs {x, y} such that first(P0 , x) = y and
first(P0 , y) = x. Observe that the preference lists of x and y cannot obtain any unmarked agent
other than each other. As already discussed in the beginning of the section, any stable matching
for preferences without ties must contain all fixed pairs. We introduce two more notions to
partition the agent set V . Let marked(P0 ) denote the set of all agents whose preference lists
consist of only marked agents, and let unmarked(P0 ) denote the set of all agents whose preference
lists have at least one unmarked agent. Obviously, marked(P0 ) and unmarked(P0 ) partition the
set V , i.e. V = marked(P0 ) ⊎ unmarked(P0 ). We can now predetermine some special cases.
Lemma 1. If |marked(P0 )| > γ| or unmarked(P0 ) has an agent x with rankx (first(P0 , x)) > γ,
then the original profile for P0 admits no stable matchings with egalitarian cost at most γ.
Proof. Assume that |marked(P0 )| > γ. By Proposition 1(3), we know that no stable matching
will assign a partner to any agent in marked(P0 ). Since each of unmatched agent will contribute a cost of at least one, we deduce that each stable matching has egalitarian cost at least
|marked(P0 )|. Thus, by our assumption, each stable matching will have egalitarian cost more
than γ.
Assume that unmarked(P0 ) has some agent x with rankx (first(P0 , x)) > γ. By Proposition 1(4) , each agent that has some unmarked agent in its preference list must obtain some
partner in every stable matching. Thus, by our assumption that the first unmarked agent in the
preference list of x has a rank larger than γ, the partner that x obtains from each stable matching will contribute to an egalitarian cost of more than γ. Consequently, each stable matching
must also have an egalitarian cost more than γ.
Using Lemma 1, we can shrink our instance to obtain a polynomial size problem kernel.
Theorem 3. Egalitarian Stable Roommates without ties admits a size-O(γ 2 ) problem
kernel with at most 2γ + 1 agents and at most γ + 1 agents in each of the preference lists.
Proof. Let I = (P, V, γ) be an instance of Egalitarian Stable Roommates and let P0 be
the profile that Algorithm 1 produces for P. We use F to denote the set of agents of all fixed
pairs(i.e. agents in pairs {x, y} such that first(P0 , x) = y and first(P0 , y) = x), and we use O
to denote the set of ordered pairs (x, y) of agents such that x ranks y higher than γ. Briefly
put, our kernelization algorithm will delete all agents in F ∪ marked(P0 ), and introduce O(γ)
dummy agents to replace the deleted agents and some more that are identified by O. Initially,
F and O are set to empty sets.
1. If |marked(P0 )| > γ or if there is an agent x in unmarked(P0 ) with rankx (first(P0 , x)) > γ, then
replace the input instance with a trivial no-instance; otherwise proceed with the remaining
steps.
2. For each two agents x, y ∈ unmarked(P0 ) with first(P0 , x) = y and first(P0 , y) = x, add to F
the agents x and y.
3. Update the egalitarian cost bound for P
the agents that are either in
Pa fixed pair or unmatched
by any stable matching. Let γ̂ = γ − x∈F rankx (first(P0 , x)) − x∈marked(P0 ) |Vx |.
4. If γ̂ < |unmarked(P0 )\F |, then replace the input instance with a trivial no-instance; otherwise
do the remaining steps.

7

5. Add to the original agent set a set D of 2k dummy agents d1 , d2 , . . . , d2k , where k = 2⌈γ̂/2⌉,
such that for each i ∈ {1, 2, . . . , k}, the preference list of di consists of only dk+i , and the
preference list of dk+i consists of only di . In this way, each stable matching must contain all
pairs {di , dk+i }, which have zero egalitarian costs.
6. For each two agents x, y ∈ unmarked(P0 ) with rankx (y) > γ̂, add to O the ordered pair (x, y).
7. For each agent a ∈ unmarked(P0 ) \ F do the following.
(1) For each value i ∈ {0, 1, 2, . . . , γ̂}, let x be the agent with ranka (x) = i and do the
following. If x ∈ F ∪ marked(P0 ) or if (x, a) ∈ O, then replace in a’s preference list
agent x with a dummy agent d, using a different dummy agent for each i, and append a
to the preference list of d.
(2) Delete all agents y in the preference list of a with ranka (y) > γ̂.
8. Delete F ∪ marked(P0 ) from P0 .
We show that the above algorithm produces a problem kernel with at most 2γ̂ + 1 agents and
with preference list length at most γ̂ + 1 each.
First, the correctness of Step 1 is ensured by Lemma 1. Second, by Proposition 1(2), we
know that each fixed pair must be matched together in each stable matching. That is, if x and
y are each other’s most preferred unmarked agents (ignoring the marked agents, because they
cannot form blocking pairs), then each stable matching must match x and y together. Hence,
it does not alter the equivalence between the input instance and the kernel if we decrease the
egalitarian cost by the amount of ranks of those agents whose partners are fixed. Moreover,
by Proposition 1(5), no agent from marked(P0 ) will have a partner assigned from any stable
matching. However, we have to take their egalitarian cost into account. This leads to the
correctness of Steps 3 and 4. From now on, we assume that γ̂ ≥ 1.
The introduction of at most γ̂+1 dummy agents in Step 5 does not contribute any egalitarian
cost; hence, this step is correct.
In Step 7, we update the preference lists of all original agents that will stay in the problem
kernel. These are those agents that do not belong to F ∪ marked(P0 ). To see why this step is
correct, for each agent a ∈ unmarked(P0 )\F , we have already reasoned that a will not be assigned
a partner from F ∪ marked(P0 ). Furthermore, to obtain a stable matching with egalitarian cost
at most γ̂, we also cannot assign to an agent a ∈ (unmarked(P0 ) \ F ) a partner x such that
(x, a) ∈ O since the rank of a in the preference list of x is higher than γ̂. Note that appending
agents to the preference list of dummy agents does not change the fact that each dummy agent
can only be matched with another dummy agent in each stable matching. Thus, the first part
of Step 7 is indeed correct. Finally, it is obviously correct to remove in the preference list of a
all agents x that have a higher rank: ranka (x) > γ̂; note that a ∈ (unmarked(P0 ) \ F ). In this
way, the length of the preference list of a is at most γ̂ + 1, and that the preference list of a
consists of agents x with x ∈ D ∪ (unmarked(P0 ) \ F ).
After all these changes, we delete all agents from F ∪ marked(P0 ). Note that their (non)matches are determined to be the same in each stable matching, and that the corresponding
cost has been accounted for by updating the egalitarian cost bound. This shows that the
kernelization algorithm is correct. It remains to bound the size of our problem kernel. The
kernel has exactly |unmarked(P0 ) \ F | original agents and at most γ̂ + 1 dummy agents. By
Step 4, we know that |unmarked(P0 ) \ F | ≤ γ̂. Thus, the kernel has at most 2γ̂ + 1 agents. By
Steps 5 and 7, each of the agents has a preference list of length at most γ̂ + 1.
As for the running time, computing P0 takes O(n2 ) time and each of the above steps takes
O(n · γ) time. Thus, in total, the kernelization algorithm takes O(n2 ) time.
To illustrate our kernelization algorithm, consider Example 1 again and assume that γ = 8.
By our kernelization algorithm, F = {5, 10}, marked(P0 ) = {4, 9}. Updating our egalitarian
bound, we obtain that γ̂ = 6. In Step 5, we need to introduce 2⌈γ̂/2⌉ = 6 dummy agents,
d1 , d2 , . . . , d6 . In Step 6, we obtain that O = {(1, 8), (1, 9)}. After Step 7, the updated preference

8

lists of all agents in (unmarked(P0 ) \ F ) could be as follows:
agent 1 : 6 ≻ 2 ≻ 7 ≻ d1 ≻ d2 ≻ 3 ≻ d3 , agent 6 : 2 ≻ 3 ≻ 1 ≻ 8,
agent 2 : 7 ≻ 8 ≻ 6 ≻ 1,

agent 7 : 3 ≻ 1 ≻ 8 ≻ 2,

agent 3 : 8 ≻ 6 ≻ 1 ≻ 7,

agent 8 : 2 ≻ 6 ≻ 7 ≻ 3 ≻ d1 ,

agent d1 : d4 ≻ 1 ≻ 8,

agent d4 : d1 ,

agent d2 : d5 ≻ 1,

agent d5 : d2 ,

agent d3 : d6 ≻ 1,

agent d6 : d3 .

Finally, we delete the agents from F ∪ marked(P0 ).
Now, we turn to our simple branching algorithm.
Theorem 4. Let n denote the number of agents and γ denote the egalitarian cost. Egalitarian
Stable Roommates without ties can be solved in O(2γ · n2 ) time.
Proof. Let I = (P, V, γ) be an instance of Egalitarian Stable Roommates and let P0 be
the profile that Algorithm 1 produces for input P. We aim to construct a stable matching M
of egalitarian cost at most γ for V .
First, we use F to collect the agents in the fixed pairs, that exist in all stable matchings,
i.e. F = {x, y ∈ unmarked(P0 ) | first(P0 , x) = y ∧ first(P0 , y) = x}. We also add to M the
corresponding pairs, i.e. M = {{x, y} ⊆ unmarked(P0 ) | first(P0 , x) = y ∧ first(P0 , y) = x}.
Second, just as in our kernelization algorithm
stated in the proofPof Theorem 3, we update our
P
egalitarian bound by setting γ̂ = γ − x∈F rankx (first(P0 , x)) − x∈marked(P0 ) |Vx |.
Our branching algorithm will extend the matching M to find a stable one with egalitarian
cost at most γ̂ and works as follows. Pick an arbitrary unmatched agent u ∈ (unmarked(P0 ) \ F )
and let Vu∗ = {v ∈ Vu \ F | {u, v} is not marked and ranku (v) + rankv (u) ≤ γ̂} be the set of
agents v which are still acceptable to u such that rankv (u) + ranku (v) ≤ γ̂. Note that |U | ≤ γ̂ + 1
and that, clearly, u cannot be matched to any of its acceptable agents outside of U as otherwise
the egalitarian cost will exceed γ̂. Branch into all possibilities to add {u, v} to M for v ∈ U and
decrease the remaining budget γ accordingly; that is, make one recursive call for each possibility.
If afterwards γ̂ > 0, then recurse with another yet unmatched agent u. If γ̂ = 0 or there is
no unmatched agent anymore, then check whether the current matching M is stable in O(n2 )
time. Accept if M is stable and otherwise reject.
Clearly, in O(n2 ) time, we can compute P0 , match all fixed pairs, and update the egalitarian
cost bound. The recursive procedure makes at most γ̂ + 1 recursive calls, and in each of them,
the budget is reduced by 1, 2, . . . , γ̂, γ̂, respectively. To see why the budgets in the first γ̂
calls are updated in this way, we observe that for each agent u ∈ unmarked(P0 ) and each
acceptable agent v ∈ Vu∗ with rankv (u) ≤ |Vu∗ | − 1, it holds that rankv (u) ≥ 1 as otherwise the
agent v ′ ∈ Vu∗ with rank |Vu∗ | would be marked, as ensured by Proposition 1(1). Thus, our
branching algorithm has a branching vector (1, 2, . . . , γ̂, γ̂), which amounts to a running time
of O(call-time · 2γ̂ ), where call-time denotes the running time of each call (see for instance [49,
Chapter 8.1] for some discussion on how to obtain the corresponding running time). Since each
call can be carried out in O(n2 ) time, our algorithm runs in O(n2 · 2γ̂ ) = O(n2 · 2γ ).

3.2

Preferences with ties

When the preferences may contain ties, we can no longer assume that if two agents are each
other’s most acceptable agents, denoted as a good pair, then a minimum egalitarian cost stable
matching would match them together; note that good pairs do not induce any egalitarian cost.
This is because their match could force other pairs to be matched together that have large cost.
Nevertheless, a good pair will never block any other pair, i.e. no agent in a good pair will form
with an agent in some other pair a blocking pair. It is straightforward to see that each stable
9

matching must contain a maximal set of disjoint good pairs. However, it may also contain
some other pairs which have non-zero cost. We call such pairs costly pairs. Aiming to find a
stable matching M with egalitarian cost at most γ, it turns out that we can also identify in
γ O(γ) · nO(1) time a subset S of pairs of agents, which contains all costly pairs of M and contains
no two pairs that may induce a blocking pair. It hence suffices to find a minimum-cost maximal
matching in the graph induced by S and the good pairs. The crucial idea is to use the random
separation technique [14] to highlight the difference between the matched costly pairs in M
and the unmatched costly pairs. This enables us to ignore the costly pairs which pairwisely
block each other or are blocked by some pair in M so as to obtain the desired subset S.
Perfectness. Before we get to the algorithm, we show that we can focus on the case
where our desired stable matching is perfect, i.e., each agent is matched, even when the input
preferences are incomplete. (Note that the case with complete preferences is covered by Observation 1.) We show this by introducing dummy agents to extend each non-perfect stable
matching to a perfect one, without altering the egalitarian cost.
Lemma 2. Egalitarian Stable Roommates for n agents and egalitarian cost γ is O(γ ·n2 )time reducible to Egalitarian Stable Roommates for at most n + γ agents and egalitarian
cost γ with an additional requirement that the stable matching should be perfect.
Proof. Let (V, P, γ) be an instance of Egalitarian Stable Roommates. Construct another
instance (V ′ , P ′ , γ ′ ) of Egalitarian Stable Roommates as follows. Define k = γ if γ is even
and k = γ − 1 otherwise. Introduce a set A := {a1 , . . . , ak } of k agents, and let V ′ := V ∪ A. Let
V ∗ consist of all agents in V that each have at most γ acceptable agents. To obtain P ′ , define
the preference list of each agent in V \ V ∗ to be the same as in P. All agents in A have the
same set of acceptable agents, namely A ∪ V ∗ , which are tied as most acceptable. Consistently,
for each agent b ∈ V ∗ , the preference list of b in P ′ is Lb ≻ A, where Lb is the preference
list of b in P. This completes the construction of (V ′ , P ′ , γ). It can clearly be carried out in
O(γ · n2 ) time.
We claim that (V, P, γ) admits a stable matching M with egalitarian cost at most γ if and
only if (V ′ , P ′ , γ) admits a perfect stable matching M ′ with egalitarian cost at most γ.
For the “only if” part, let V⊥ ⊆ V be the agents left unmatched by M . Observe that
|V⊥ | ≤ γ as each unmatched agent has at least one acceptable agent and thus contributes at
least one unit to the egalitarian cost. Moreover, since |V | is even, |V⊥ | is even. Construct a
matching M ′ for (V ′ , P ′ , γ) with M ⊆ M ′ by matching each agent in V⊥ to a unique agent in
A. Match the remaining, so far unmatched, agents in A among themselves. Note that this is
possible because both V⊥ and A are even.
Observe that M ′ is perfect. It is also stable: No agent in V \ V⊥ is involved in a blocking
pair according to M and each agent in V⊥ is matched to some agent in A, and each agent in A
is matched to one of his most acceptable agents. It remains to determine the egalitarian cost
of M ′ .
Note that each agent in A contributes zero units to the egalitarian cost of M ′ because they
are matched with their most acceptable agents. Hence, the only difference between γ(M ) and
γ(M ′ ) may arise from the cost of the agents in V⊥ . Let b ∈ V⊥ and let ℓ be the number of
agents acceptable to b according to P. By our egalitarian cost definition and by the preference
lists of b and M (b) in P, the cost of b for M is the same as the cost of {b, M ′ (b)} for M ′ . Hence,
indeed M ′ is a perfect stable matching and has egalitarian cost at most γ.
For the “if” part, let M ′ be a perfect stable matching of egalitarian cost at most γ for P ′ .
Obtain a matching M for P by taking M = {p ∈ M ′ | p ⊆ V }. Observe that no two agents a, b
that are both unmatched with respect to M are acceptable to each other as otherwise, they
would prefer to be with each other rather than with their respective partners given by M ′ ,

10

forming a blocking pair for M ′ (note that the partners assigned to a and b by M ′ are in A and
hence have a largest rank in the preference lists of a and b according to P ′ ).
We claim that M is stable for (V, P, γ). Suppose, towards a contradiction, that {a, b} ⊆ V is
blocking M . This implies that a and b are acceptable to each other, and by the above reasoning,
at least one of the agents a and b is matched in M . Furthermore, either a or b needs to be
unmatched by M as, otherwise, {a, b} is a blocking pair for M ′ —a contradiction. Say in M ,
agent a is unmatched but agent b is matched, implying that M ′ (a) ∈ A and b prefers a to its
partner M (b) = M ′ (b). However, by the definition of the preference list of agent a in P ′ , it
prefers agent b over any agent in A, implying that {a, b} is also blocking M ′ —a contradiction.
Finally, by a reasoning similar to the one given for the “only if” part, we can obtain that
the egalitarian costs of M and M ′ remain the same, which is at most γ.
Lemma 2 allows, in a subprocedure of our main algorithm, to compute a minimum-cost perfect
matching in polynomial time instead of a minimum-cost maximal matching (which is NP-hard).
The algorithm. As mentioned, our algorithm is based on random separation [14]. We
apply it already in derandomized form using Bshouty’s construction of cover-free families [12], a
notion related to universal sets [47]. Let n̂, p, q ∈ N such that p + q ≤ n̂. A family F of subsets
of some n̂-element universe U is called (n̂, p, q)-cover-free family if for each subset S ⊆ U of
cardinality p + q and each subset S ′ ⊆ S of cardinality p, there is a member A ∈ F with
S ∩ A = S ′ .1 The result by Bshouty [12, Theorem 4] implies that if p ∈ o(q), then there is
an (n̂, p, q)-cover-free family of cardinality q O(p) · log n̂ which can be computed in time linear
of this cardinality. A similar result with a larger running time is given by Chitnis et al. [17,
Lemma 1] based on so-called splitters [47].
In the remainder of this section, we prove our main result:
3

Theorem 1. Egalitarian Stable Roommates can be solved in 2O(γ ) · n3 · (log n)3 time,
even for incomplete preferences with ties, where n denotes the number of agents and γ denotes
the egalitarian cost.
Let P be a preference profile for a set V of agents, possibly incomplete and with ties. For
brevity we denote by a solution (of P) a stable matching M with egalitarian cost at most γ. By
Lemma 2, we assume that each solution is perfect. Our goal is to construct a graph with vertex
set V which contains all matched “edges”, representing the pairs, of some solution and some
other edges for which
 no two edges in this graph are blocking each other. Herein, we say that
V
′
two edges e, e ∈ 2 are blocking each other if, assuming both edges (which are two disjoint
pairs of agents) are in the matching, they would induce a blocking pair, i.e. u′ ≻u v and u ≻u′ v ′ ,
where e := {u, v} and e′ := {u′ , v ′ }.
Pricing the edges with their corresponding cost, by Lemma 2, it is then enough to find a
minimum-cost perfect matching. The graph is constructed in three phases (see Algorithm 2).
In the first phase, we start with the acceptability graph of our profile P and remove all edges
whose “costs” each exceed γ. In the second and the third phases, we remove all edges that
block each other while keeping a stable matching with minimum egalitarian cost intact.
We introduce some more necessary concepts. Let G be the acceptability graph corresponding
to P with vertex set V , which also denotes the agent set, and with edge set E. The cost of
an edge {x, y} is the sum of the ranks of each endpoint in the preference list of the other:
rankx (y) + ranky (x). We call an edge e := {x, y} a zero edge if it has cost zero, i.e. rankx (y) +
ranky (x) = 0, otherwise it is a costly edge if the cost does not exceed γ. We ignore all edges with
1
The standard definition of cover-free families [12] is stated differently from but equivalent to ours. Namely,
an (n̂, p, q)-cover-free family is a tuple (X, B), where B is a family of n̂ subsets of X such that for each list
(B
) ∈ Bp and each list (A1 , . . . , Aq ) ∈ Bq with Bi 6= Aj , i ∈ {1, . . . , p}, j ∈ {1, . . . , q}, we have
Tp1 , . . . , BpS
q
i=1 Bi 6⊆
j=1 Aj . Bshouty and Gabizon [13] showed that the two definitions are equivalent.

11

Algorithm 2: Constructing a perfect stable matching of egalitarian cost at most γ.
Input: A set V of agents, a preference profile P over V , and a budget γ ∈ N.
Output: A stable matching of egalitarian cost at most γ if it exists.

12

/* Phase 1
*/
(V, E) ← The acceptability graph of P
E zero ← {{x, y} ∈ E | rankx (y) + ranky (x) = 0}
// The set of zero edges in E
E exp ← {{x, y} ∈ E | 1 ≤ rankx (y) + ranky (x) ≤ γ}
// The set of costly edges in E
E1 ← E zero ∪ E exp
/* Phase 2
*/
F exp ← (|E exp |, γ, γ 3 )-cover-free family over the universe E exp
foreach E ′ ∈ F exp do
Apply Reduction rules 1 and 2 to E1 to obtain E2
/* Phase 3
*/
C ← (|V |, γ 2 + 2 · γ, 2 · γ)-cover-free family over the universe V
foreach V ′ ∈ C do
Apply Reduction rules 3 and 4 to E2 to obtain E3
M ← Minimum-cost perfect matching in the graph (V, E3 ) or ⊥ if none exists
if M 6= ⊥ and M has cost at most γ then return M

13

reject

1
2
3
4

5
6
7

8
9
10
11

cost exceeding γ. Note that no such edge belongs to or is blocking any stable matching with
egalitarian cost at most γ. To distinguish between zero edges and costly edges, we construct
two subsets E zero and E exp such that E zero consists of all zero edges, i.e. E zero := {{x, y} ∈ E |
rankx (y) + ranky (x) = 0}, and E exp consists of all costly edges, i.e. E exp := {{x, y} ∈ E | 0 <
rankx (y) + ranky (x) ≤ γ}.
Phase 1. We construct a graph G1 = (V, E1 ) from G with vertex set V and with edge
set E1 := E zero ∪ E exp . We can compute G1 in O(γ · n2 ) time with n being the number of agents.
As already noted, no edge with cost exceeding γ belongs to or is blocking any solution. The
following is easy to see.
Lemma 3. If P has a stable matching M with egalitarian cost at most γ, then M ⊆ E1 .
Observe also that a zero edge cannot block any other edge because the agents in a zero edge
already obtain their most acceptable agents. Thus, we have the following.
Lemma 4. If two edges in E1 block each other, then they are both costly edges.
Phase 2. In this phase, comprising Lines 5–7 in Algorithm 2, we remove from G1 some of
the costly edges that block each other (by Lemma 4, no zero edges are blocking any other edge).
For technical reasons, we distinguish two types of costly edges: We say that a costly edge e with
e := {u, v} is critical for its endpoint u if the largest possible rank of v over all linearizations of
the preference list of u exceeds γ, i.e. |{x ∈ Vu \ {v} | x u v}| > γ. Otherwise, e is harmless
for u. If an edge is critical for at least one endpoint, then we call it critical and otherwise
harmless. Observe that a critical edge could still belong to a solution. If two edges e and e′
block each other due to the blocking pair {u, u′ } with u ∈ e, u′ ∈ e′ such that e′ is harmless
for u′ , then we say that e is harmlessly blocking e′ (at the endpoint u′ ). Note that blocking is
symmetric while harmlessly blocking is not.
Intuitively, we want to distinguish the solution edges from all edges blocked by the solution.
There is a “small” number of harmless edges blocked by the solution, so we can easily distinguish
between them. For the critical edges, we do not have such a bound; we deal with the critical
edges blocked by the solution in Phase 3 in some other way.
Lemma 5. Let M be a stable matching with egalitarian cost at most γ. In G1 , at most γ 3 edges
are harmlessly blocked by some edge in M .
12

Proof. By Lemma 4, if an edge e′ from G1 is blocked by an edge e in M , then both edges e′
and e are costly edges. Pick a costly edge e in M , denote its endpoints by u and v, and let
Fe denote the set of all edges that are harmlessly blocked by e. Recall that each edge e′ :=
{u′ , v ′ } ∈ Fe that is blocked by e induces a blocking pair consisting of some endpoint of e, say
u, and some endpoint of e′ , say u′ . By the definition of induced blocking pairs, it follows that
ranku (u′ ) ≤ ranku (v)−1. Thus, since e has cost at most γ, meaning that ranku (v)+rankv (u) ≤ γ,
there are at most γ − 2 different endpoints of the costly edges in Fe , which each form with an
endpoint of e a blocking pair. Since each edge e′ in Fe is harmlessly blocked by e it follows that
|{x ∈ Vu′ \ {v ′ } | x u′ v ′ }| ≤ γ. Thus, in Fe , at most γ edges are incident with endpoint u′
and could be harmlessly blocked by e due to {u′ , z} with z ∈ e. In total, we obtain that
|Fe | ≤ γ · (γ − 2). Since M has egalitarian cost at most γ, it has at most γ costly edges that
could block some other edge (recall that zero edges do not block any edges). Hence, there are
in total γ · (γ − 2) · γ < γ 3 edges which are harmlessly blocked by some edge in M .
Let M ′ := M ∩ E exp be the set of all costly edges in some solution M and let BM be the set
of all edges harmlessly blocked by some edge in M . By the definition of costly edges and by
Lemma 5, it follows that |M ′ | ≤ γ and |BM | ≤ γ 3 . In order to identify and delete all edges
in BM we apply random separation. Compute a (|E exp |, γ, γ 3 )-cover-free family F exp over the
universe E exp . For each member of F exp , perform all the computations below (in this phase
and in Phase 3). By the properties of cover-free families, F exp contains a good member E ′
that “separates” M ′ from BM , i.e. M ′ ⊆ E ′ and BM ⊆ E exp \ E ′ . Formally, we call a
member E ′ ∈ F exp good if there is a solution M such that each costly edge in M belongs to E ′ ,
and each edge that is harmlessly blocked by M belongs to E exp \E ′ . We also call E ′ good for M .
By the property of cover-free families, if there is a solution M , then F exp contains a member E ′
which is good for M . In the following we present two data reduction rules that delete edges
and show their correctness. By correctness we mean that, if some member E ′ ∈ F exp is good,
then the corresponding solution is still present after the edge deletion.
Recall that the goal was to compute a graph that contains all edges from a solution and
some other edges such that no two edges in the graph block each other. Observe that we can
ignore the edges in E exp \ E ′ , because, if E ′ is good, then it contains all costly edges in the
corresponding solution; note that |E ′ | could be unbounded. This implies the correctness of the
following reduction rule.
Reduction rule 1. Remove all edges in E exp \ E ′ from E1 .
Apply also the following reduction rule.
Reduction rule 2. If there are two edges e, e′ ∈ E ′ that are harmlessly blocking each other,
then remove both e and e′ from E1 .
Proof of the correctness of Reduction rule 2. Let M be a solution for which E ′ is good. Suppose, towards a contradiction, that e ∈ M . Since E ′ is good, no edge is harmlessly blocked by
M belongs to E ′ . Thus, e′ ∈
/ E ′ —a contradiction. Analogously, we deduce that e′ ∈
/ M . Thus,
′
we can safely delete both e and e .
Let G2 = (V, E2 ) be the graph obtained from G1 by exhaustively applying Reduction rules 1
and 2. By the goodness of E ′ and by the correctness of Reduction rules 1 and 2, we have the
following.
Lemma 6. If there is a stable matching M with egalitarian cost at most γ, then F exp contains
a member E ′ such that the edge set E2 of G2 defined for E ′ contains all edges of M .
By Lemma 4 and since all pairs of edges that are harmlessly blocking each other are deleted
by Reduction rule 2, we have the following.
Lemma 7. If two edges in G2 block each other due to a blocking pair {u, u′ }, then one of the
edges is critical for u or u′ .
13

Phase 3. In line 10 of Algorithm 2 we remove from G2 the remaining (critical) edges that
do not belong to M but are blocked by some other edges. This includes the edges that are
blocked by M . While the number of edges blocked by M could still be unbounded, we show
that there are only O(γ 2 ) agents due to which an edge could be blocked by M . The idea here is
to identify such agents, helping to find and delete edges blocked by M or blocking some other
edges. We introduce one more notion. Consider an arbitrary matching N (i.e. a set of disjoint
pairs of agents) of G2 . Let e ∈ N and e′ ∈ E2 \ N be two edges. If they induce a blocking
pair {u, u′ } with u ∈ e and u′ ∈ e′ , then we say that u′ is a culprit of N . Similar to the proof
of Lemma 5, we obtain the following upper bound on the number of culprits with respect to a
solution.
Lemma 8. Let M be a stable matching. Then, each culprit of M is incident with some edge
in M . If M has egalitarian cost at most γ, then it admits at most γ 2 culprits.
Proof. For the first statement, let u′ be a culprit of M . Suppose, towards a contradiction, that
u′ is not incident with any edge in M . This means that u′ is unmatched under M . However,
by the definition of culprits, M contains an edge e such that u′ and one of the endpoint of e
would form a blocking pair for M —a contradiction to M being stable.
For the second statement, observe that M contains at most γ costly edges. Each edge that
is blocked by an edge in M is costly and is blocked by a costly edge in M . Pick a costly edge e
in M and consider the set Fe of all edges blocked by e. Recall that each edge e′ blocked by e
would induce a blocking pair {u, u′ } with u ∈ e and u′ ∈ e′ . By the same reasoning as used for
Lemma 5, we obtain that Fe has at most γ − 2 endpoints. Hence, M has in total γ · (γ − 2) < γ 2
culprits.
Consider a solution M and let CI(M ) = {v ∈ V | v is a culprit of or incident with some
costly edge of M }. By Lemma 8 and since M has at most γ costly edges, it follows that
|CI(M )| ≤ γ 2 + 2γ. Our goal was to delete edges without disturbing the solution M such that
no remaining edges are blocking each other. To achieve this, we identify in CI(M ) a subset R(M )
of agents incident with a critical edge in M , i.e. R(M ) = {v ∈ CI(M ) | {v, w} ∈ M with {v, w}
being critical for v}. Since M has at most 2γ costly edges, it follows that |R(M )| ≤ 2γ. To
“separate” R(M ) from CI(M ), we compute a (|V |, 2γ, γ 2 + 2γ)-cover-free family C on the set V
of agents. We call a member V ′ ∈ C good if there is a solution M ⊆ E2 such that for each
agent v ∈ CI(M ) the following holds.
- If v ∈ R(M ), then v ∈ V ′ , i.e. if v is incident with an edge in M that is critical for v, then
v ∈ V ′;
- otherwise, v ∈ V \ V ′ , meaning that if v is incident with a zero edge or with an edge in M
that is harmless for v, then v ∈ V \ V ′ .
Since |R(M )| ≤ 2γ and |CI(M ) \ R(M )| ≤ γ 2 + 2γ, by a similar reasoning as given for Phase 2
and by the properties of cover-free families, if there is a solution M ⊆ E2 , then C contains a
good member V ′ . We describe two reduction rules to delete some edges from G2 and show their
correctness, i.e. if some member V ′ ∈ C is good, then the rules do not delete any edge of a
corresponding solution.
Reduction rule 3. For each agent y ∈ V \ V ′ , delete all incident edges that are critical for y.
Proof of the correctness of Reduction rule 3. Assume that V ′ is good and let M ⊆ E2 be a
corresponding solution. Since y ∈
/ V \ V ′ , it follows that y is not incident with an edge in M
that is critical for y. Thus, we can safely delete all incident edges that are critical for y.
After having exhaustively applied Reduction rule 3, we use the following reduction rule.
Recall that by Lemma 7, if two edges in E2 block each other, then one of them is critical.
Reduction rule 4. If E2 contains two edges e and e′ that induce a blocking pair {u, u′ } with
u ∈ e and u′ ∈ e′ such that e is critical for u, then remove e′ from E2 .
14

Proof of the correctness of Reduction rule 4. Assume that V ′ is good and let M ⊆ E2 be a
corresponding solution. Towards a contradiction, suppose that e′ ∈ M . Hence, u is a culprit
of M . By the first statement of Lemma 8, let {u, w} ∈ M be an incident edge. Since Reduction
rule 3 has been applied exhaustively, all critical edges that are incident with agents in V \ V ′
are deleted. Since V ′ is good, it follows that u ∈ V ′ and {u, w} is critical for u. Since e is also
critical for u, it follows that v ∼u w, where v is the endpoint of e different from u. However, since
e and e′ are blocking each other, it follows that {u, w} and e′ are also blocking each other—a
contradiction to M being stable.
Let G3 = (V, E3 ) be the graph obtained after having exhaustively applied Reduction rules 3
and 4 to G2 . As mentioned, by the properties of cover-free families, if there is a solution
contained in E2 , then the above constructed cover-free family C contains a good member. Thus,
by the correctness of Reduction rules 3 and 4 we have the following.
Lemma 9. If there is a stable matching M ⊆ E2 with egalitarian cost at most γ, then the
constructed cover-free family C contains a good member V ′ ∈ C such that the edge set E3 of G3
resulting from the application of Reduction rules 3 and 4 contains all edges of M .
Since for each member V ′ ∈ C, we delete all edges that pairwisely block each other, each perfect
matching in G3 induces a stable matching. We thus have the following.
Lemma 10. If G3 admits a perfect matching M with edge cost at most γ, then M corresponds
to a stable matching with egalitarian cost at most γ.
Proof. Since the cost of each edge in G3 is exactly the egalitarian cost induced, considering M
as a matching, the egalitarian cost of M is at most γ. Towards a contradiction, suppose that
a perfect matching M in G3 has two blocking edges e and e′ . By Lemma 7 one of e and e′ is
critical for its endpoint in the corresponding blocking pair. Since Reduction rule 4 does not
apply to G3 anymore, the other edge is not present in E3 , a contradiction.
Thus, to complete Algorithm 2, in line 11 we compute a minimum-cost perfect matching for G3
and output yes, if it has egalitarian cost at most γ.
Summarizing, by Lemma 2 if there is a stable matching of egalitarian cost at most γ, then
it is perfect and thus, by Lemmas 3, 6 and 9, there is a perfect matching in G3 of cost at
most γ. Hence, if our input is a yes-instance, then Algorithm 2 accepts by returning a desired
solution. Furthermore, if it accepts, then by Lemma 10 the input is a yes-instance.
As to the running time, as a slight modification to Algorithm 2, prior to any other computation, we first compute an (n2 ,γ, γ 3 )-cover-free family F exp with cardinality (γ 3 )O(γ) · log n
from Phase 2 in O (γ 3 )O(γ) · log n = γ O(γ) · log n time [12], and an (n, 2γ, γ 2 + 2γ)-cover-free

family C from Phase 3 in O (γ 2 + 2γ)O(γ) · log n = γ O(γ) · log n time [12]. Note that we can
reuse C during the course of the algorithm. The remaining computation time can be bounded
as follows. First, we compute G1 in O(γ · n2 ) time by checking for each pair of agents, whether
they are most acceptable to each other or whether the sum of their ranks is at most γ. Then, in
Phase 2, we iterate through all members of the cover-free family F exp and for each member we
need the following computation time. We first compute G2 in O(γ · n2 ) time (note that O(γ)
time is enough to check whether two given edges block each other, assuming the preference
lists are ordered). Then we iterate through all members of the cover-free family C and for each
of them compute G3 . Computing G3 can be done in O(γ · n2 ) time by similar reasoning as
before. Finally, the minimum-cost perfect matching can be found in O(n3 · log n) time [18].
Thus, overall the running time is γ O(γ) · n3 · (log n)3 . Thus we have proved Theorem 1.

15

3.3

Variants of the egalitarian cost for unmatched agents

As discussed in Sections 1 and 2, when the input preferences are incomplete, a stable matching
may leave some agents unmatched. In the absence of ties, all stable matchings leave the same
set of agents unmatched [27, Chapter 4.5.2]. Hence, whether an unmatched agent should infer
any cost is not relevant in terms of complexity. However, when preferences are incomplete and
with ties, stable matchings may involve different sets of matched agents. The cost of unmatched
agents changes the parameterized complexity dramatically.
In this section, we consider two variants of assigning costs to unmatched agents: zero cost or a
constant fixed cost, and we show that for both cost variants, seeking for an optimal egalitarian
stable matching is parameterized intractable. (Note that the cost ∞, that is, allowing only
perfect matchings, is already covered in Section 3.2.)
Unmatched agents have cost zero. By the definition of stability, if two agents are
acceptable to each other, but their corresponding dissatisfaction is large, then either they are
matched, contributing a large, or possibly too large, portion to the egalitarian cost, or one
of the two agents must be matched with someone else. This can be used to model a choice
of truth value for a variable in a reduction from satisfiability problems. Indeed, we can show
that the problem is already hard for Egalitarian Stable Marriage, the bipartite variant
of Egalitarian Stable Roommates.
Theorem 5. If the cost of the unmatched agents is zero, then Egalitarian Stable Marriage with incomplete preferences and ties is NP-complete even in the case where the egalitarian
cost is zero and each agent has at most three acceptable agents.
Proof. We reduce from the NP-complete 3SAT variant in which each literal appears exactly
twice and each clause has exactly three literals [8]. Let φ be a corresponding Boolean formula
in conjunctive normal form with variable set X and clause set C.
The reduction proceeds as follows. For each variable xi ∈ X, we introduce 3 agents a∗i , atrue
i ,
s , cs , and ds for all j ∈ {1, 2} and s ∈ {true, false}. The
and afalse
,
and
12
agents,
denoted
as
b
i
i,j i,j
i,j
agents for one specific variable xi are shown in the variable gadget in Figure 2. The preference
list of an agent v in the variable gadget is defined as follows: Each agent that is adjacent to v
with a solid line is a most acceptable agent of v (and vice versa); they have rank 0 in each
other’s preference list. Each agent that is adjacent to v with a dashed line has rank 1. For
each clause Cj (note that it contains three literals), we construct a clause gadget that consists
of 2 agents u∗j and wj∗ , and of 9 agents, denoted as xj,i , yj,i, and zj,i for all i ∈ {1, 2, 3}. The
agents for clause Cj are shown in the variable gadget on the left in Figure 2. We use the same
conventions (the solid and dashed edges) to define their preference lists as we did for the variable
gadgets.
To combine the clause and variable gadgets, for each variable xi ∈ X and for each clause Cj ∈
C we do the following: If xi appears positively in a clause Cj ∈ C, then we pick two agents ctrue
i,s ,
true
di,s in xi ’s variable gadget and two agents yj,r , zj,r in Cj ’s clause gadget that have not been
true
used for combining before, and identify ctrue
i,s = zj,r and di,s = yj,r . Analogously, if xi appears
false
negatively in Cj , then we identify cfalse
i,s = zj,r and di,s = yj,r .
This completes the construction, which can clearly be done in polynomial time. Observe that
each agent has at most three acceptable agents. One can verify that the underlying acceptability
graph is bipartite since every cycle has an even length. Hence, the constructed preference profile
is indeed a valid instance of Stable Marriage.
To see that a satisfying assignment for φ induces a stable matching with egalitarian
cost 0, construct a matching M as follows. For each variable xi that is assigned to true,
false false
true true
let {a∗i , atrue
i } ∈ M and, for each s ∈ {1, 2}, let {ci,s , di,s }, {bi,s , ci,s } ∈ M . Accordingly,
∗
false
for each variable xi that is assigned to false, let {a , a } ∈ M and, for each i ∈ {1, 2} let
16

a∗i
atrue
i

wj∗

afalse
i

u∗j

btrue
i,1

btrue
i,2

bfalse
i,1

bfalse
i,2

xj,1

xj,2

xj,3

ctrue
i,1

ctrue
i,2

cfalse
i,1

cfalse
i,2

yj,1

yj,2

yj,3

dtrue
i,1

dtrue
i,2

dfalse
i,1

dfalse
i,2

zj,1

zj,2

zj,3

Figure 2: A variable gadget (left) and a clause gadget (right) for the proof of Theorem 5.
true
false false
{btrue
i,s , ci,s }, {ci,s , di,s } ∈ M . Observe that, if an agent from the variable gadget is matched,
then it is matched with one of his most acceptable agents. Furthermore, if an agent (except
false/true
di,s
) is not matched, then all of its acceptable agents are matched. For each clause Cj ,
pick a literal that satisfies it, say it is the literal x1 , and let {u∗j , xj,2 }, {wj∗ , xj,3 } ∈ M . Again,
each matched agent is with one of its most acceptable agents, hence the egalitarian cost is 0.
Furthermore, for each agent v from the clause gadget, v is either matched (with egalitarian
cost 0), or each agent acceptable to v is matched to one of its most acceptable agents. Hence,
there are no blocking pairs. We conclude that M is a stable matching and has egalitarian cost 0.
Now let M be a stable matching of egalitarian cost 0. Note that, in the variable gadget of
each variable xi , agent a∗i is matched to either atrue
or afalse
. This is because M being stable
i
i
true
false
implies that at least one of ai and ai has to be matched and a∗ is the only agent acceptable
to them that has cost 0. For each variable xi , assign to xi true if {a∗i , atrue
i } ∈ M and false
otherwise. We claim that each clause Cj ∈ C is satisfied in this way. To see this, consider Cj ’s
clause gadget and observe that one of the triple xj,1 , xj,2 , and xj,3 is not matched in M because
there are only two agents that are most acceptable to the triple; note that the total egalitarian
cost should be zero. Say xj,1 is not matched (the other cases are symmetric). This implies that
p = {yj,1 , zj,1 } ∈ M , which corresponds to a literal as by our construction. Assume that this
true
pair p equals a pair {dtrue
i,1 , ci,1 } for some variable xi (i.e. it occurs positively in Cj ). This is
true
without loss of generality, due to symmetry. Since {atrue
i , bi,1 } should be neither a member of
∗
true
nor blocking M , it follows that ai is matched to ai , meaning that variable xi is set to true.
Thus, clause Cj is satisfied, as claimed.

Unmatched agents have some constant positive cost. If the unmatched agents have
some constant positive cost c, then it is easy to see that Egalitarian Stable Roommates
belongs to XP.
Proposition 2. If the cost of each unmatched agent is some positive constant, then Egalitarian Stable Roommates with incomplete preferences and with ties can be solved in
3
nγ · 2O(γ ) · n3 · (log n)3 time, where γ is the egalitarian cost.
Proof sketch. Let c be the cost for an unmatched agent. The algorithm is as follows. Guess, by
trying all possibilities, a subset A of at most γ/c unmatched agents. Remove A from the set
of agents V and all preference lists and modify the preference lists of the remaining agents as
follows. For each agent u ∈ V \ A who was acceptable to some agent a ∈ A, remove from u’s
preference list all agents b for which u strictly preferred a over b. In the remaining instance,
search for a perfect stable matching of egalitarian cost at most γ − c˙|A|. This can be done
3
in 2O(γ ) · n3 · (log n)3 time using Theorem 1. If such a matching exists, accept and otherwise
reject.
We cannot substantially improve on the above algorithm in general, however. Indeed, we
17

can use the same idea as in the reduction for Theorem 5 and utilize the fact that, when there
are ties, an agent can select his partner from an unbounded number of agents with the same
cost, in order to obtain a polynomial-time parameterized reduction from the W[1]-complete
Independent Set problem (parameterized by the size of the independent set solution).
Theorem 6. Let n denote the number of agents and γ denote the egalitarian cost. If the cost of
each unmatched agent is some positive constant, then Egalitarian Stable Roommates with
incomplete preferences and ties is W[1]-hard with respect to γ. It does not admit an f (γ) · no(γ) time algorithm unless the Exponential Time Hypothesis is false.
Proof. We reduce from Independent Set, which, given an n-vertex graph G = (U, E) with
vertex set U and edge set E, and a number k ∈ N, asks whether G admits a k-vertex independent
set, a vertex subset U ′ ⊆ U with pairwisely non-adjacent vertices. Let c be the cost for an
unmatched agent, which is positive; without loss of generality, we assume that c is also a positive
integer. To construct an instance of Egalitarian Stable Roommates, set the egalitarian
cost to c · k and construct a preference profile as follows. Set the set V of agents to U ∪ A ∪ D,
where U is a set of vertex agents, A = {a1 , a2 , . . . , an−k } is a set of n − k selector agents, and
D = {du1,i , du2,i | i ∈ {1, 2, . . . , c} ∧ u ∈ U } is a set of 2 · c · n dummy agents. Note that we use U
to denote both the vertex set and the set of vertex agents, and we will make it clear whether
we mean the vertices or their corresponding vertex agents.
For each i ∈ {1, 2, . . . , n − k} the set of acceptable agents to ai is precisely U and each pair of
acceptable agents are tied, that is, they have rank 0 in ai ’s preference list. For each vertex u ∈ U ,
the set of the acceptable agents of the corresponding agent u is A∪{du1,i | i ∈ {1, 2, . . . , c}}∪N (u).
The preference list of u is A ≻ du1,1 ≻ du1,2 ≻ . . . ≻ du1,c ≻ N (u), i.e. A are all tied with rank 0,
followed by c dummy agents, and finally the agents from the neighborhood N (u) are all tied
with rank c + 1. Finally, for each u ∈ U and i ∈ {1, 2, . . . , c}, agent du1,i is the only acceptable
agent of du2,i , and du1,i ’s preference list is du2,i ≻ u. This completes the construction, which can
clearly be done in polynomial time. If the reduction is correct, then it implies the result, because
Independent Set is well-known to be W[1]-hard and, moreover, an f (k) · no(k)-time algorithm
for Independent Set would contradict the Exponential Time Hypothesis [20].
To see that a size-k independent set U ′ induces a stable matching of egalitarian cost c · k,
match each agent ai with a distinct vertex in U \U ′ and, for each u ∈ U and each i ∈ {1, 2, . . . , c},
match du1,i with du2,i . Observe that the thus constructed matching M has egalitarian cost c · k,
because, besides the k unmatched agents in U ′ , each agent is matched with one of its most
acceptable agents. To see that M is also stable, it suffices to show that no pair of agents u, v ∈ U ′
induces a blocking pair. This clearly holds, since u and v are not adjacent in G and thus not
acceptable to each other. Thus, M is a stable matching of egalitarian cost at most c · k.
To see that a stable matching M of egalitarian cost c · k induces a size-k independent set U ′
for G, let U ′ = {v ∈ U | M (u) ∈
/ A} be the set of agents in U , which are not assigned to some
selector agent ai by M as a partner. Observe that each selector agent ai is matched to some
agent in U . Otherwise, there is some agent b ∈ U which is either unmatched or matched to
some other agent in U or some dummy agent. Hence {b, ai } would form a blocking pair. Thus,
each selector agent ai is matched to some agent in U , meaning that |U ′ | = k. Observe also that
each agent du1,i is matched to du2,i , because, otherwise, they would form a blocking pair. Hence,
the only possible matches for agents in U ′ are their neighbors in G. However, if two agents in U ′
are matched together, then M ’s egalitarian cost is in total larger than c · k, a contradiction.
Thus, no two agents in U ′ are matched together, and since M is stable, no two agents in U ′ are
acceptable to each other. Thus, U ′ is of size k and induces an independent set, as required.

18

u0
a0

u4

c0
d

a4

d0

4

1

c

4

c

d

d
3

u3

x5

x0

1

y2

2

c
c3

a3

a1

a

b

u1

x4

x1

d2
x3

a2

x2
y1

u2

Figure 3: The acceptability graphs for Constructions 1 and 2 with n′ = 2 and δ = 2. Left:
Thick lines correspond to a matching with exactly one blocking pair, {a1 , a2 }. Right: Thick
lines correspond to a possible stable matching when y 1 and y 2 are matched with some agents
that they prefer to x2 and x4 , respectively.

4

Minimizing the number of blocking pairs

In this section, we strengthen the known result [6] (i.e. Min-Block-Pair Stable Roommates
is NP-complete even for complete preferences without ties) by showing that Min-Block-Pair
Stable Roommates is W[1]-hard with respect to “the number β blocking pairs”, even when
each preference list has length at most five. Note that the NP-hardness reduction in [6] is from
the problem of finding a maximal matching of minimum cardinality in a graph. However, this
matching problem is fixed-parameter tractable for the cardinality of the solution [51]. Thus, it
is not clear how to adapt the proof of Abraham et al. [6] to provide a parameterized reduction.
The main building block of our reduction, which is from the W[1]-hard Multi-Colored Independent Set problem (see appendix for the definition), is a selector gadget (Construction 1)
that always induces at least one blocking pair and allows for many different configurations. To
keep the lengths of the preference lists short we use “duplicating” agents (Construction 2).
Our result excludes any f (β)·nO(1) -time algorithm (unless FPT = W[1]) and any f (β)·no(β) time algorithm (unless Exponential Time Hypothesis fails). Using the same reduction, we also
answer an open question by Manlove [40, Chapter 4.6.5], showing that minimizing the number η
of blocking agents is NP-hard and W[1]-hard with respect to η.
First, we discuss a vertex-selection gadget which we later use to select a vertex of the input
graph into the independent set. The selected vertex is indicated by an agent which is matched
to someone outside of the vertex-selection gadget. The gadget always induces at least one
blocking pair. Moreover, if an agent from the gadget is not matched to one of a specified set
of agents, then an arbitrary matching induces more than one blocking pair. An illustration
is shown in the left part of Figure 4. In the following, let n′ be a positive integer, and all
additions and subtractions in the superscript are taken modulo 2n′ + 1:
Construction 1. Consider the following four disjoint sets U, A, C, D of 2n′ + 1 agents each,
where A := {ai | 0 ≤ i ≤ 2n′ }, U := {ui | 0 ≤ i ≤ 2n′ }, C := {ci | 0 ≤ i ≤ 2n′ }, and
D := {di | 0 ≤ i ≤ 2n′ }. The preference lists of the agents in A ∪ C ∪ D are as follows:
∀i ∈ {0, 1, . . . , 2n′ } : Agent ai : ai+1 ≻ ai−1 ≻ ui ≻ ci ≻ di ,
Agent ci :
di ≻ ai ,
i
Agent d : ai ≻ ci .
The preferences of the agents in U are intentionally left unspecified and we define them
19

later when we use the gadget. Regardless of the preferences of the agents in U , we can verify
that if no ai obtains an agent ui as a partner, then it induces at least two blocking pairs.
Lemma 11. Let P be a profile with agents A ⊎ U ⊎ C ⊎ D where the preferences of the agents
in A ∪ C ∪ D obey Construction 1. Let M be a matching for P. The following holds.
1. M induces at least one blocking pair of the form {ai−1 , ai } for some i ∈ {0, 1, . . . , 2n′ }.
Moreover, if M (ai ) 6= ui , then M induces one more blocking pair p′ with p′ ⊆ {ai , bi , ci }.
2. Assume that there is an agent ai ∈ A with M (ai ) = ui . If (i) for each z ∈ {1, . . . , n′ }
it holds that M (ai+2z−1 ) = ai+2z , and (ii) for each z ′ ∈ {0, 1, . . . , 2n′ } it holds that
′
′
M (cz ) = dz , then {ai , ai−1 } is the only blocking pair that involves some agent from
A ∪ C ∪ D.
Proof. To show the first statement, observe that |A| is odd, implying that there is an i ∈
{0, 1, . . . , 2n′ } such that M (ai ) ∈
/ A. Then, since ai−1 ranks ai in the first position it follows
i−1
i
that {a , a } is blocking M . Now, assume that M (ai ) 6= ui . By assumption, it holds that
M (ai ) ∈
/ A ∪ {ui }, implying that M (ai ) ∈ {⊥, ci , di }. If M (ai ) = ⊥, then since di ranks ai in
the first position, it follows that {ai , di } is also blocking M . If M (ai ) = ci , then M (di ) = ⊥
and {di , ci } is blocking M (observe that ci ranks di in the first position). If M (ai ) = di , then
M (ci ) = ⊥ and {ci , ai } is blocking M (observe that ai prefers ci to di ). In any case, we find at
least two blocking pairs, namely {ai , ai−1 } and another that involves two agents from {ai , ci , di }.
It remains to show the last statement. Let M be a matching for P with M (ai ) = ui for
some i and satisfying Condition (i) and (ii). First of all, for each z ′ ∈ {0, 1, . . . , 2n′ } we observe
′
′
that cz already obtains its most preferred agent, and the only agent that dz prefers to its
′
′
′
′
′
′
partner cz is az . However, az prefers its partner (which is some agent from {az +1 , az −1 , uz })
′
to dz . Thus, no blocking pair involves any agent from C ∪ D.
Now consider an agent ai+2z−1 with z ∈ {1, 2, . . . , n′ }. By the assumption on the matching M , we know that ai+2z−1 already obtains its most preferred agent ai+2z . Thus, no blocking
pair involves any agent of the form ai+2z−1 . Consider an agent ai+2z with z ∈ {1, 2, . . . , n′ − 1}
and observe that agent ai+2z+1 is the only agent that ai+2z prefers to its partner M (ai+2z ) =
ai+2z−1 . However, as already reasoned, agent ai+2z+1 already obtains its most preferred agent
as a partner. Thus, no blocking pair involves an agent of the form ai+2z . By the reasoning for
the first statement, {ai−1 , ai } is the only blocking pair.
Next, we construct verification gadgets that ensure that no two adjacent vertices are chosen
into the independent set solution. A straightforward idea would be to have a single agent for each
vertex which prefers to be with its “neighbor” rather than with any agent from the selection gadget. If an agent and its “neighbor” are forced to be matched elsewhere by the selection gadgets,
they would induce a blocking pair, exceeding the cost bound. However, this would introduce
preference lists of unbounded length. We now show how, by configuring some additional agents
in a cyclic fashion, we can reduce the length of a preference list, while maintaining the independent set model. The resulting gadget is illustrated in the right part of Figure 4. Herein, let δ be
a positive integer, and all additions and subtractions in the superscript are taken modulo 2δ + 2.
Construction 2. Consider two disjoint sets X ⊎ Y where X = {xi | 0 ≤ i ≤ 2δ + 1} is a
set of 2δ + 2 agents and Y = {y i | 1 ≤ i ≤ δ} is a set of δ agents. Let a, b be two agents
distinct from the agents in X ∪ Y . The preference lists of the agents from X are as follows.
Agent x0 :
x1 ≻ a ≻ x2δ+1 ,
∀i ∈ {1, . . . , δ} : Agent x2i−1 :
x2i ≻ x2i−2 ,
2i
∀i ∈ {1, . . . , δ} : Agent x :
x2i+1 ≻ y i ≻ x2i−1 .
2δ+1
Agent x
: x0 ≻ b ≻ x2δ .
The preferences of the agents a, b and those in Y are intentionally left unspecified and will
be defined when we use the gadget later. Regardless of the concrete preferences of agents in
20

Y ∪{a, b}, we claim that the above gadget has two possible matchings such that no blocking pair
involves any agent from X. The first one is straightforward from the definition of the preference
lists: {{x2i , x2i+1 } | i ∈ {0, 1, . . . , δ}}. The second one is stated in the following lemma.
Lemma 12. Let P be a profile with agents X ∪ Y ∪ {a, b} where the preferences of the agents
from X obey Construction 2. Let M be a matching for P such that M (x0 ) = a and M does not
induce any blocking pair involving an agent from X. The following holds.
1. For each z ∈ {1, 2, . . . , δ}, it holds that M (x2z−1 ) = x2z , and y z prefers M (y z ) to x2z .
2. M (x2δ+1 ) = b.
Proof. The first statement can be proved by induction on z with 1 ≤ z ≤ δ. For z = 1, since
M (x0 ) = a, it follows that M (x1 ) = x2 as otherwise {x0 , x1 } is blocking M . Furthermore, since
x2 prefers y 1 to x1 and since no blocking pair involves agent x2 , it follows that y 1 prefers M (y 1 )
to x2 .
Now assume that M (x2δ−3 ) = x2δ−2 and that y δ−1 prefers M (y δ−1 ) to x2δ−2 . By an analogous reasoning as above we deduce that M (x2δ−1 ) = x2δ as otherwise {x2δ−1 , x2δ−2 } would be
blocking M . Consequently, y δ must obtain an agent M (y δ ) that it prefers to x2δ .
The second statement follows since M (x2δ ) = x2δ−1 and M (x0 ) = a.
Using Lemmas 11 and 12, we can prove our second main result, Theorem 2, by providing a parameterized reduction from the W[1]-complete Multi-Colored Independent Set
problem [23] parameterized by the size of the independent set (see the proof of Theorem 6 for
the definition of Independent Set). This is a special variant of Independent Set (also
see the definition in the proof of Theorem 6), in which given a graph G on k disjoint vertex
subsets V1 , V2 , . . . , Vk we ask whether there is a size-k multi-colored independent set V ′ for G,
i.e. an independent set which has exactly one vertex from each subset Vi .
Theorem 2. Let n denote the number of agents and β denote the number of blocking pairs.
Even when each input preference list has length at most five and has no ties, Min-Block-Pair
Stable Roommates is W[1]-hard with respect to β and admits no f (β) · no(β) -time algorithms
unless the Exponential Time Hypothesis is false.
Proof. Let (G = (V1 , V2 , . . . , Vk , E)) be a Multi-Colored Independent Set instance (see
appendix for ). Without loss of generality, assume that each vertex subset Vj has exactly 2n′ + 1
′
vertices and has the following form Vj = {vj0 , vj1 , . . . , vj2n }. Construct a Min-Block-Pair Stable Roommates instance with the following groups of agents: Uj , Aj , Bj , Cj , Dj , Fj , Wj , j ∈
{1, 2, . . . , k}, where Uj corresponds to the vertex subset Vj . Let δji denote the degree of vertex vji .
i,2δi +1

i,1
j
For each vertex vji ∈ Vj , construct 2δji +2 agents ui,0
and let Uji = {ui,z
j , uj , . . . , uj
j |0≤z ≤
i
i
2δj + 1}. Define Uj = ∪0≤i≤2n′ Uj . For each (Q, q) ∈ {(A, a), (B, b), (C, c), (D, d), (F, f ), (W, w)}
and for each i ∈ {1, 2, . . . , k}, the set Qj := {qji | 0 ≤ i ≤ 2n′ } consists of 2n′ + 1 agents. The
preference lists of the agents in Uji obey the verification gadget constructed in Construction 2.
Formally, for each j ∈ {1, . . . , k} and each i ∈ {0, 1, . . . , 2n′ } we introduce a verification gadget
i
i
for vji as in Construction 2 where we set δ = δji , xz = ui,z
j , 0 ≤ z ≤ 2δj + 1, a = aj , and
′
b = bij . The agents from Y correspond to the neighbors of vji : For each neighbor vji ′ of vji we
′
pick a not-yet-set agent y z in the verification gadget for vji and a not-yet-set agent y z in the
′

′

verification gadget for vji ′ , and define y z = uij ′,2z and y z = ui,2z
j .
1
0
For instance, if vertex v1 and v2 are adjacent, and the agent y 2 for v10 and the agent y 1 for
0,4
1
1
v21 are not yet set, then the agent y 2 for v10 could be u1,2
2 and the agent y for v2 could be u1 .
0,5
1,2
0,3
In this way, the preference list of u0,4
1 will have the form u1 ≻ u2 ≻ u1 . The preference list
1,3
0,4
1,1
of u1,2
2 will have the form u2 ≻ u1 ≻ u2 .
′
For each j ∈ {1, . . . , k}, the preference lists of Aj ∪ Cj ∪ Dj ∪ {ui,0
j | 0 ≤ i ≤ 2n } obey
Construction 1. Formally, for each j ∈ {1, . . . , k} we introduce a vertex-selection gadget as in
′

21

′

Construction 1 and for each i ∈ {0, 1, . . . , 2n′ } we set ai = aij , ci = cij , di = dij , and ui = ui,0
j .
i,2δi +1

Analogously, for each j ∈ {1, . . . , k}, the preference lists of Bj ∪Fj ∪Wj ∪{uj j | 0 ≤ i ≤ 2n′ }
obey Construction 1. Formally, for each j ∈ {1, . . . , k} we introduce a vertex-selection gadi,2δji +1

get for Bj ∪ Fj ∪ Wj ∪ {uj

| 0 ≤ i ≤ 2n′ }: For each i ∈ {0, 1, . . . , 2n′ } we set ai = bij ,

i,2δj +1

ci = fji , di = wji , and ui = uj i . To complete the construction, we set the upper bound on
the number of blocking pairs as β = 2k.
We show that G = (V1 , V2 , . . . , Vk , E) is a yes-instance of Multi-Colored Independent
Set if and only if the constructed profile admits a matching with at most β := 2k blocking pairs.
For the “if” part, assume that M is a matching with at most 2k blocking pairs. By the
first statement of Lemma 11 it follows that for each j ∈ {1, 2, . . . , k}, matching M induces at
i′ −1 i′
i
2
least two blocking pairs p1j and p2j of the forms p1j = {ai−1
, bj } for some
j , aj } and pj = {bj
i, i′ ∈ {0, 1, · · · , 2n′ }.
By the second part of the first statement of Lemma 11, the agent aij that is involved in
the blocking pair p1j must be matched to ui,0
j as otherwise there will be more than 2k blocking
i,0
′
i
i
pairs. We claim that V = {vj | {aj , uj } ∈ M } is a size-k multi-colored independent set.
Obviously, |V ′ | = k.
Suppose, for the sake of contradiction, that V ′ contains two adjacent vertices. Let these
′
vertices be vji and vji ′ for two distinct j, j ′ ∈ {1, 2, . . . , k} and some i, i′ ∈ {0, 1, . . . , 2n′ }. By the
′

i ,0
i
definition of V ′ , we have that {aij , ui,0
j }, {aj , uj ′ } ∈ M . By the first statement of Lemma 12,
′

′
i
for each z ∈ {1, . . . , δji } it holds that {uji,2z−1 , ui,2z
j } ∈ M , and for each z ∈ {1, . . . , δj ′ } it
′

′

′

′

′

holds that {uij ′,2z −1 , uji ′,2z } ∈ M . However, since vji and vji ′ are adjacent, by the preference
′

′

′

lists under Construction 2 for Uji and Uji′ , there are two agents ui,2z
and uij ′,2z (for some
j
′

′

′

′

′

and uji ′,2z
prefers uji ′,2z to its partner ui,2z−1
z ∈ {0, 1, . . . , δij }, z ′ ∈ {0, 1, . . . , δij′ }) such that ui,2z
j
j
′

′

′

′

′

i ,2z
prefers ui,2z
to its partner uji ′,2z −1 . This implies that {ui,2z
} is blocking M , that is, M
j
j , uj ′
induces more than 2k blocking pairs—a contradiction. Hence, indeed V ′ is an independent set.
For the “only if” part, assume that V ′ ⊂ V is a multi-colored independent set of size k.
i−1 i
i
′
i
We claim that BP = {{ai−1
j , aj }, {bj , bj } | vj ∈ V } consists of all 2k blocking pairs of the
matching M defined as follows. For each color j ∈ {1, 2, . . . , k} and for each i ∈ {0, 1, . . . , 2n′ }
do the following; all additions and subtractions in subscripts of the agents in the vertex-selection
gadgets are taken modulo 2n′ + 1.
• Set M (cij ) = dij . If vji ∈ V ′ (i.e. the vertex belongs to the multi-colored independent
i,2δi +1

j
i
set), then set M (ui,0
) = bij , for each z ∈ {1, 2, . . . , n′ } set
j ) = aj and M (uj
) = bji+2z .
) = aji+2z and M (bi+2z−1
M (ai+2z−1
j
j
Note that this in particular defines matchings for all vertex-selection gadgets. By the third
statement in Lemma 11, the only blocking pairs introduced so far are for each vji ∈ V ′ the
i−1 i
i
pairs {ai−1
j , aj } and {bj , bj }.
i,2z+1
• If vji ∈
.
/ V ′ , then for each z ∈ {0, 1, . . . , δji } set M (ui,2z
j ) = uj

• Finally, for each vji ∈ V ′ and each z ∈ {1, 2, . . . , δji } set M (ui,2z−1
) = ui,2z
j
j .
We claim that BP as defined above consists of all blocking pairs of M . Towards a contradiction,
suppose that M induces a blocking pair p ∈
/ BP. As mentioned, by the third statement of
Lemma 11 and the construction of our matching M , besides the blocking pairs in BP, the only
agents that could form a blocking pair are from verification gadget(s). We distinguish two
cases. In the first case the two agents in p are in the verification gadget for one and the same
vertex vji ∈ Vj for some j ∈ {1, 2, . . . , k} and i ∈ {0, 1, . . . , 2n′ }. Then, vji ∈ V ′ because for each
two agents that correspond to the same vertex v ′ ∈ V \ V ′ (which is not in the independent set
solution V ′ ) and are acceptable to each other, one of them already obtains its most preferred
i,z ′
i,z
i
′
agent. Assume that p = {ui,z
j , uj } for some independent set vertex vj ∈ V such that uj and
22

′

ui,z
are acceptable to each other but not matched together. If z, z ′ ∈
/ {0, 2δji , 2δji + 1}, then p
j
cannot form a blocking pair as one of the agents in p already obtains its most preferred agent.
i,2δji

This implies that {z, z ′ } = {0, 2δji + 1} or {z, z ′ } = {2δji , 2δji + 1} because agents ui,0
j and uj
i,2δji +1

i
do not find each other acceptable. However, ui,0
j prefers its partner aj to uj

i,2δji +1

and uj

i,2δi

prefers its partner bij to uj j . Thus, we deduce that no blocking pair involves two agents that
correspond to the same vertex.
It remains to consider the case when the two agents in p are in verification gadgets of two
′
′
different vertices vji , vji ′ ∈ V with vji 6= vji ′ . Since only agents that correspond to two adjacent
′
vertices could find each other acceptable, it follows that vji and vji ′ are adjacent. By the prefer′

′

i ,2z
ence lists of the verification gadgets for vji and vji ′ , it also follows that p = {ui,2z
} for some
j , uj ′
′

i,2z−1
z, z ′ ∈ {1, 2, . . . , k}. Since p is blocking M it follows that M (ui,2z
and M (ui,2z
j ) = uj
j ) =
′

i ,0 i
i
ui,2z−1
. Moreover, by the construction of M it must hold that {ui,0
j
j , aj }, {uj ′ , aj ′ } ∈ M for some
′
j, j ′ ∈ {1, 2, . . . , k}, meaning that vji , vji ′ ∈ V ′ —a contradiction to V ′ being an independent set.
Assuming Exponential Time Hypothesis, if our problem would have an f (β) · no(β) -time
algorithm, then by our reduction, Multi-Colored Independent Set would also admit
an g(k) · no(k) -time algorithm, where f and g are two computable functions—a contradiction
to [20, Corollary 14.23].
′

The reduction given in the proof of Theorem 2 shows that the lower-bound on the number β
of blocking pairs given by Abraham et al. [6, Lemma 4] is tight. The reduction also answers
an open question by Manlove [40, Chapter 4.6.5] pertaining to the complexity of the following
related problem. In Min-Block-Agents Stable Roommates, we are given a preference
profile and an integer η, and we want to know whether there is a matching with at most η
blocking agents, that is, agents involved in blocking pairs.
First of all, we observe the following for the vertex-selection gadget given in Construction 1.
Lemma 13. Let P be a preference profile with agents A ⊎ U ⊎ C ⊎ D where the preferences of
the agents in A ∪ C ∪ D obey Construction 1. Let M be a matching for P. The following holds.
1. M induces at least two blocking agents ai−1 , ai for some i ∈ {0, 1, . . . , 2n′ }.
2. If for each i ∈ {0, 1, . . . , 2n′ } it holds that M (ai ) 6= ui , then M induces at least three
blocking agents.
3. Assume that there is an agent ai , i ∈ {0, 1, . . . , 2n′ }, with M (ai ) = ui . If (i) for each z ∈
{1, . . . , n′ } it holds that M (ai+2z−1 ) = ai+2z , and (ii) for each z ′ ∈ {0, 1, . . . , 2n′ } it holds
′
′
that M (cz ) = dz , then agents ai−1 and ai are the only two blocking agents from A∪C ∪D.
Proof. For the first statement, we observe that the first statement of Lemma 11 implies that
there is an integer i ∈ {0, 1, . . . , 2n′ } with {ai−1 , ai } being a blocking pair. Thus, ai−1 and ai
are two blocking agents.
Similarly, by the reasoning for the second statement of Lemma 11, if no agent ai is matched
with ui , then there are at least two blocking pairs, which share at most one blocking agent.
Thus, there are at least three blocking agents.
The last statement follows by the last statement of Lemma 11.
Corollary 1. Let n be the number of agents and η be the number of blocking agents. Even when
each input preference list has length at most five and has no ties, Min-Block-Agents Stable Roommates is NP-hard and W[1]-hard with respect to η. Min-Block-Agents Stable
2
Roommates for preferences without ties is solvable in O(2η · nη+2 ) time.
Proof. To show the hardness results, we use the same reduction as in the proof of Theorem 2 and
we set the number of blocking agents allowed to be η = 2k. As in the proof of Theorem 2, now
using Lemma 13, if the Min-Block-Agents Stable Roommates instance is a yes-instance,
23

then the Independent Set instance is also a yes-instance. In the other direction, observe that
the matching constructed from a size-k independent set solution in Theorem 2 induces exactly
2k = η blocking agents.
In the remainder of the proof, we provide an algorithm for our problem and show that the
2
running time is O(2η · nη+2 ). This algorithm uses as a subprocedure the algorithm provided
by Abraham et al. [6] that, given a set B of pairs of agents, checks in O(n2 ) time whether there
is matching N such that each pair in B is blocking N and no other pair is blocking N .
Assume that there is a matching M with exactly η blocking agents. First, we guess the set of
these η agents that form some blocking pairs of M and denote this set as A∗ = {a1 , a2 , . . . , aη }.
Now, observe that any blocking pair must only involve agents from A∗ . Thus, we guess the
blocking pairs of M that only involve agents from A∗ . Finally, we call the algorithm by Abraham
et al. [6] to check whether the guess is correct.
It is straightforward to see that there is a matching M with exactly η blocking agents if and
only if one of the guesses gives a subset of pairs of agents that are exactly the blocking pairs of M .
Now observe that there are O(nη ) guesses of the subset of blocking agents with size η and for each
2
of these subset of blocking agents there are O(2η ) guesses for a corresponding subset of blocking
pairs. Since for each guessed subset of blocking pair, we invoke the algorithm by Abraham et al.
2
[6] which runs in O(n2 ) time, our algorithm has a running time of O(2η · nη+2 ).

5

Conclusion and outlook

We showed that Egalitarian Stable Roommates and Min-Block-Pair Stable Roommates, though both NP-hard in the classical complexity point of view, behave completely differently in a parameterized perspective. In particular, we showed that Egalitarian Stable
Roommates is fixed-parameter tractable with respect to the egalitarian cost γ while MinBlock-Pair Stable Roommates with bounded preference length is W[1]-hard with respect
to the number β of blocking pairs.
Our work leads to some open questions. First, we showed that for preferences without ties,
Egalitarian Stable Roommates admits a size-O(γ 2 ) kernel. It would thus be interesting to
see whether Egalitarian Stable Roommates also admits a polynomial kernel when ties are
present. Second, it would be interesting to see whether the running time in Theorem 1 is tight.

References
[1] URL http://www.nrmp.org. National Resident Matching Program website.
[2] URL http://www.nes.scot.nhs.uk/sfas. Scottish Foundation Allocation Scheme website.
[3] A. Abdulkadiroǧlu, P. A. Pathak, and A. E. Roth. The Boston public school match.
American Economic Review, 95(2):368–371, 2005.
[4] A. Abdulkadiroǧlu, P. A. Pathak, and A. E. Roth. The New York City high school match.
American Economic Review, 95(2):364–367, 2005.
[5] D. Abraham, N. Chen, V. Kumar, and V. S. Mirrokni. Assignment problems in rental
markets. In Proceedings of the Second International Workshop on Internet and Network
Economics (WINE ’06), pages 198–213, 2006.
[6] D. J. Abraham, P. Biró, and D. Manlove. “Almost stable” matchings in the roommates
problem. In Proceedings of the Third International Workshop on Approximation and Online
Algorithms (WAOA ’05), pages 1–14, 2005.

24

[7] M. Baı̈ou and M. Balinski. Student admissions and faculty recruitment. Theoretical Computer Science, 322(2):245–265, 2004.
[8] P. Berman, M. Karpinski, and A. D. Scott. Approximation hardness of short symmetric
instances of MAX-3SAT. Technical Report 49, Electronic Colloquium on Computational
Complexity, 2003.
[9] P. Biró and S. Kiselgof. College admissions with stable score-limits. Central European
Journal of Operations Research, 23(4):727–741, 2015.
[10] P. Biró, D. Manlove, and S. Mittal. Size versus stability in the marriage problem. Theoretical Computer Science, 411(16-18):1828–1841, 2010.
[11] P. Biró, D. Manlove, and E. McDermid. “Almost stable” matchings in the Roommates
problem with bounded preference lists. Theoretical Computer Science, 432:10–20, 2012.
[12] N. H. Bshouty. Linear time Constructions of some d-Restriction Problems. In Proceedings
of the 9th International Conference on Algorithms and Complexity (CIAC ’15), volume
9079 of Lecture Notes in Computer Science, pages 74–88. Springer, 2015.
[13] N. H. Bshouty and A. Gabizon. Almost Optimal Cover-Free Families. In Proceedings of the
11th International Conference on Algorithms and Complexity (CIAC ’17), volume 10236
of Lecture Notes in Computer Science, pages 140–151. Springer, 2017.
[14] L. Cai, S. M. Chan, and S. O. Chan. Random Separation: A New Method for Solving FixedCardinality Optimization Problems. In Proceedings of the Second International Workshop
on Parameterized and Exact Computation (IWPEC ’06), pages 239–250. Springer, 2006.
[15] J. Chen, R. Niedermeier, and P. Skowron. Stable marriage with multi-modal preferences.
Technical report, arXiv:1801.02693 [cs.MA,], 2018.
[16] Y. Chen and T. Sönmez. Improving efficiency of on-campus housing: An experimental
study. American Economic Review, 92(5):1669–1686, 2002.
[17] R. Chitnis, M. Cygan, M. Hajiaghayi, M. Pilipczuk, and M. Pilipczuk. Designing FPT Algorithms for Cut Problems Using Randomized Contractions. SIAM Journal on Computing,
45(4):1171–1229, 2016.
[18] W. Cook and A. Rohe. Computing Minimum-Weight Perfect Matchings. INFORMS
Journal on Computing, 11(2):138–148, 1999.
[19] Á. Cseh, R. W. Irving, and D. F. Manlove. The stable roommates problem with short
lists. In Proceedings of the 9th International Symposium on Algorithmic Game Theory
(SAGT ’16), pages 207–219, 2016.
[20] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk,
and S. Saurabh. Parameterized Algorithms. Springer, 2015.
[21] K. Eriksson and O. Häggström. Instability of matchings in decentralized markets with
various preference structures. International Journal of Game Theory, 36(3):409–420, 2008.
[22] T. Feder. A new fixed point approach for stable networks and stable marriages. Journal
of Computer and System Sciences, 45(2):233–284, 1992.
[23] M. R. Fellows, D. Hermelin, F. Rosamond, and S. Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1):53–61,
2009-01-28.
25

[24] A. Gai, D. Lebedev, F. Mathieu, F. de Montgolfier, J. Reynier, and L. Viennot. Acyclic
preference systems in P2P networks. In Proceedings of the 13th International Euro-Par
Conference, pages 825–834, 2007.
[25] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American
Mathematical Monthly, 120(5):386–391, 2013.
[26] S. Gupta, S. Roy, S. Saurabh, and M. Zehavi. Balanced stable marriage: How close is close
enough? Technical report, arXiv:1707.09545 [], 2017.
[27] D. Gusfield and R. W. Irving. The Stable marriage problem–Structure and algorithms.
Foundations of computing series. MIT Press, 1989.
[28] M. M. Halldórsson, R. W. Irving, K. Iwama, D. Manlove, S. Miyazaki, Y. Morita, and
S. Scott. Approximability results for stable marriage problems with ties. Theoretical
Computer Science, 306(1-3):431–447, 2003.
[29] K. Hamada, K. Iwama, and S. Miyazaki. An improved approximation lower bound for
finding almost stable maximum matchings. Information Processing Letters, 109(18):1036–
1040, 2009.
[30] A. Hylland and R. Zeckhauser. The efficient allocation of individuals to positions. Journal
of Political Economy, 87(2):293–314, 1979.
[31] R. W. Irving. An efficient algorithm for the ‘stable roommates’ problem. Journal of
Algorithms, 6(4):577–595, 1985.
[32] R. W. Irving. Optimal stable marriage. In M. Kao, editor, Encyclopedia of Algorithms,
pages 1470–1473. Springer, 2016.
[33] R. W. Irving. Stable marriage. In M. Kao, editor, Encyclopedia of Algorithms, pages
2060–2064. Springer, 2016.
[34] R. W. Irving, P. Leather, and D. Gusfield. An efficient algorithm for the ‘optimal’ stable
marriage. Journal of the ACM, 34(3):532–543, 1987.
[35] D. Knuth. Mariages Stables. Les Presses de L’Université de Montréal, 1976.
[36] E. Kujansuu, T. Lindberg, and E. Mäkinen. The Stable Roommates problem and chess
tournament pairings. Divulgaciones Matemáticas, 7(1):19–28, 1999.
[37] D. Lebedev, F. Mathieu, L. Viennot, A. Gai, J. Reynier, and F. de Montgolfier. On using
matching theory to understand P2P network design. In Proceedings of the International
Network Optimization Conference (INOC 2007), pages 1–7, 2007.
[38] D. Manlove. Hospitals/residents problem. In M. Kao, editor, Encyclopedia of Algorithms.
Springer, 2008.
[39] D. Manlove, R. W. Irving, K. Iwama, S. Miyazaki, and Y. Morita. Hard variants of stable
marriage. Theoretical Computer Science, 276(1-2):261–279, 2002.
[40] D. F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science. WorldScientific, 2013.
[41] D. F. Manlove and G. O’Malley. Paired and altruistic kidney donation in the UK: Algorithms and experimentation. ACM Journal of Experimental Algorithmics, 19(1), 2014.

26

[42] D. Marx and I. Schlotter. Parameterized complexity and local search approaches for the
stable marriage problem with ties. Algorithmica, 58(1):170–187, 2010.
[43] D. Marx and I. Schlotter. Stable assignment with couples: Parameterized complexity and
local search. Discrete Optimization, 8(1):25–40, 2011.
[44] D. G. McVitie and L. B. Wilson. The Stable Marriage problem. Communications of the
ACM, 14(7):486–490, 1971.
[45] K. Meeks and B. Rastegari. Solving hard stable matching problems involving groups of
similar agents. Technical report, arXiv:1708.04109 [cs.GT], 2017.
[46] M. Mnich and I. Schlotter. Stable marriage with covering constraints-A complete computational trichotomy. In Proceedings of the 10th International Symposium on Algorithmic
Game Theory (SAGT ’17), pages 320–332, 2017.
[47] M. Naor, L. J. Schulman, and A. Srinivasan. Splitters and near-optimal derandomization.
In Proceedings of 36th Annual IEEE Symposium on Foundations of Computer Science,
pages 182–191, 1995.
[48] M. Niederle and A. E. Roth. Market culture: How norms governing exploding offers
affect market performance. Working Paper 10256, National Bureau of Economic Research,
February 2004.
[49] R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
[50] B. Pittel and R. W. Irving. An upper bound for the solvability of a random stable roommates instance. Random Structures and Algorithms, 5(3):465–487, 1994.
[51] E. Prieto. Systematic Kernelization in FPT Algorithm Design. PhD thesis, The University
of Newcastle, Australia, 2005.
[52] E. Ronn. NP-complete stable matching problems. Journal of Algorithms, 11(2):285–304,
1990.
[53] A. E. Roth and M. A. O. Sotomayor. Two-Sided Matching: A Study in Game-Theoretic
Modeling and Analysis. Cambridge University Press, 1992. Part of Econometric Society
Monographs.
[54] A. E. Roth, T. Sönmez, and M. U. Ünver. Pairwise kidney exchange. Journal of Economic
Theory, 125(2):151–188, 2005.
[55] A. E. Roth, T. Sönmez, and M. U. Ünver. Efficient kidney exchange: Coincidence of
wants in markets with compatibility-based preferences. American Economic Review, 97
(3):828–851, 2007.
[56] C. Teo and J. Sethuraman. On a cutting plane heuristic for the stable roommates problem
and its applications. European Journal of Operational Research, 123(1):195–205, 2000.

27

