# Manipulating the outcome of
stable matching and roommates problems

Kristóf Bérczi MTA-ELTE Momentum Matroid Optimization Research Group and MTA-
ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd
University, Budapest, Hungary. Email<EMAIL_ADDRESS> Gergely
Csáji MTA-ELTE Momentum Matroid Optimization Research Group, Department of
Operations Research, Eötvös Loránd University, Budapest, Hungary. Email:
<EMAIL_ADDRESS> Tamás Király MTA-ELTE Momentum Matroid
Optimization Research Group and MTA-ELTE Egerváry Research Group, Department
of Operations Research, Eötvös Loránd University, Budapest, Hungary. Email:
<EMAIL_ADDRESS>
###### Abstract

The stable marriage and stable roommates problems have been extensively
studied due to their high applicability in various real-world scenarios.
However, it might happen that no stable solution exists, or stable solutions
do not meet certain requirements. In such cases, one might be interested in
modifying the instance so that the existence of a stable outcome with the
desired properties is ensured.

We focus on three different modifications. In stable roommates problems with
all capacities being one, we give a simpler proof to show that removing an
agent from each odd cycle of a stable partition is optimal. We further show
that the problem becomes NP-complete if the capacities are greater than one,
or the deleted agents must belong to a fixed subset of vertices.

Motivated by inverse optimization problems, we investigate how to modify the
preferences of the agents as little as possible so that a given matching
becomes stable. The deviation of the new preferences from the original ones
can be measured in various ways; here we concentrate on the $\ell_{1}$-norm.
We show that, assuming the Unique Games Conjecture, the problem does not admit
a better than $2$ approximation. By relying on bipartite-submodular functions,
we give a polynomial-time algorithm for the bipartite case. We also show that
a similar approach leads to a 2-approximation for general graphs.

Last, we consider problems where the preferences of agents are not fully
prescribed, and the goal is to decide whether the preference lists can be
extended so that a stable matching exists. We settle the complexity of several
variants, including cases when some of the edges are required to be included
or excluded from the solution.

Keywords: Inverse optimization, Preference extension, Stable matching, Stable
roommates problem, Vertex deletion

##  1 Introduction

The stable marriage problem was introduced by Gale and Shapley in 1962 in
their seminal paper [13]. Since then, an enormous amount of research has been
done in the field; see for example [22] for a survey.

Our work belongs to the line of research that studies modifications of the
preference system in order to get a stable solution with certain properties.
Preference modifications in stable matching problems have been widely studied,
mainly from a strategic point of view, where a given agent or a coalition of
agents wants to submit false preferences in order to achieve better results.
This setting is also closely related to inverse optimization problems, where
we are given a feasible solution to an underlying optimization problem
together with a linear weight function, and the goal is to modify the weights
as little as possible so that the input solution becomes optimal; for further
details on inverse optimization, see e.g. [10, 24].

#### Previous work.

Concerning edge modifications, Abraham et al. [1] considered the problem of
finding a matching in the roommates problem that has a minimum number of
blocking edges. They showed that the problem is hard and is also hard to
approximate. Biró et al. [4] studied a similar question for the marriage
problem, where the goal is to find a maximum matching with minimum number of
blocking edges. Tan [27] considered the problem of finding a maximum number of
disjoint pairs of persons such that these pairs are stable among themselves,
and gave an algorithm for determining an optimum solution.

Roth [25] showed that there is no matching mechanism that produces a stable
matching and is strategy-proof for every agent, but the Gale-Shapley algorithm
is at least strategy-proof for one side. Coalitional manipulations were
studied by Shen et al. [26]. Hosseini et al. [17] investigated cases where the
coalition can contain both men and women. Aziz et al. [3] investigated the
case where the agents who want to manipulate the outcome have capacity larger
than one, like firms or hospitals. Coalitional manipulations where a fixed
subset of edges must be contained in the output of the Gale-Shapley algorithm
has been studied by Kobayashi and Matsui [20] and by Gupta and Roy [15].

Modifying the preferences by ‘bribing’ the agents in order to have a stable
matching satisfying certain conditions was studied by Boehmer et al. [5]. They
examined several variants in terms of manipulative actions and manipulation
goals in bipartite preference systems. Later, Eiben et al. [12] extended their
work to the capacitated case. Finding a matching that is robust with respect
to small modifications of the preferences have been studied by Chen et al.
[7].

Stable matchings with forced and forbidden edges were considered by several
papers, see Dias et al. [11], Cseh and Manlove [9], Cseh and Heeger [8].

#### Our results.

One of the difficulties in markets that can be described as stable roommates
problems is that they might not have a stable solution at all. To overcome
this difficulty, a natural idea is to exclude certain agents or contracts from
the market in order to guarantee the existence of a stable outcome. Both cases
have been studied already, we concentrate on the deletion of agents. The
latter problem was previously solved by Tan [27] who gave an algorithm based
on Irving’s algorithm [18]. We give a significantly simpler approach to show
that deleting an agent from each odd cycle in a stable partition is optimal.
We also study the case when the cost of excluding someone might differ from
agent to agent, or when only agents of some fixed subset are allowed to be
removed, and show that these problems are NP-hard as well as when agents have
nonnegative integer capacities.

In certain applications, it might happen that the central authority already
has a most preferred outcome and it wants to make this outcome acceptable to
the agents, too, by possibly compensating them. We concentrate on the problem
where to goal is to bribe the agents in order to make a given outcome stable.
We consider a more general framework than the one in [5] and [12]. In our
framework, the preferences are given with real numbers, and instead of swap
distance we work with the $\ell_{1}$-norm. This model allows to express that
the differences between two adjacent agents in a preference list might differ
a lot, whereas in swap distance interchanging any two of them would count as
only one swap. In addition, this approach also makes possible to have ties
among agents. We show that the problem is solvable in bipartite graphs in the
capacitated setting, even when upper and lower bounds are given on the changes
and the compensation cost differs for each agent. We also consider the
roommate case which has not yet been investigated before. We show that the
problem is NP-hard, but it admits a 2-approximation.

Finally, we investigate problems where the preferences are manipulated by the
agents themselves in order to force or avoid certain contracts to form. While
previous papers only considered manipulations with respect to the outcome of
the Gale-Shapley algorithm, we investigate more general cases. Our goal is to
ensure that there exists a stable matching with respect to the modified
preferences. This can be practically important, for example when a stable
matching is chosen randomly, not by the Gale-Shapley algorithm. We also study
cases where there are forbidden edges instead of forced ones, or some places
in the preferences are fixed and cannot be manipulated. We show that almost
all problems arising this way are NP-complete even in rather restricted
settings. On the positive side, we give an algorithm for the case when certain
places in the preference lists are not allowed to be manipulated by the
agents.

The rest of the paper is organized as follows. Basic notation and definitions
are introduced in Section 2. Section 3 focuses on problems where the goal is
to ensure the existence of a stable matching through the deletion of a subset
of vertices. Preference modifications in order to make a given outcome stable
are discussed in Section 4. Finally, in Section 5, we investigate preference
extension problems.

##  2 Preliminaries

#### Basic notations.

We denote the sets of _real_ , _nonnegative real_ , _integer_ , and
_nonnegative integer_ numbers by $\mathbb{R}$, $\mathbb{R}_{+}$, $\mathbb{Z}$,
and $\mathbb{Z}_{+}$, respectively. For a positive integer $k$, we use
$[k]\coloneqq\\{1,\dots,k\\}$.

Given a ground set $S$ and subsets $X,Y\subseteq S$, the _difference_ of $X$
and $Y$ is denoted by $X\setminus Y$. If $Y$ consists of a single element $y$,
then $X\setminus\\{y\\}$ and $X\cup\\{y\\}$ are abbreviated by $X-y$ and
$X+y$, respectively. We call a $3$-element subset a _$3$ -set_ for short. Some
hardness proofs in Section 5 will be based on the following NP-complete
problems, see [14].

x3c
Input: A family $\mathcal{C}=\\{C_{1},\dots,C_{3n}\\}$ of 3-sets of a ground
set $a_{1},\dots,a_{3n}$. Question: Does there exist $n$ 3-sets in
$\mathcal{C}$ that partition $\\{a_{1},\dots,a_{3n}\\}$?

3sat
Input: A Boolean formula $\Phi$ in conjunctive normal form where each clause
is limited to at most three literals. Question: Does there exist a truth
assignment to the variables for which $\Phi$ is true?

Let $G=(V,E)$ be an undirected graph, $S\subseteq V$ be a subset of vertices,
and $F\subseteq E$ be a subset of edges. The graphs obtained by _deleting the
vertices in $S$_ (together with the edges incident to them) or _the edges in
$F$_ are denoted by $G-S$ and $G-F$, respectively. We call $S$ a _vertex
cover_ if $G-S$ has no edges. For a vertex $u\in V$, the _set of neighbors of
$u$_ is denoted by $N(u)=\\{v\in V\mid uv\in E\\}$. The _set of edges in $F$
incident to a vertex_ $v\in V$ is denoted by $F(v)$. The following is a well-
known NP-hard problem.

vertex-cover
Input: A graph $G=(V,E)$. Goal: Find a vertex cover of minimum size.

#### Submodular and bipartite-submodular set functions.

A set function $f\colon 2^{V}\to R$ is called _submodular_ if $f(X)+f(Y)\geq
f(X\cup Y)+f(X\cap Y)$ holds for every $X,Y\subseteq V$. It is known that this
is equivalent to $f(X+a)+f(X+b)\geq f(X+a+b)+f(X)$ for every $X\subseteq V$
and distinct $a,b\in V\setminus X$. A function $f$ defined on the vertex set
of a bipartite graph $G=(A,B;E)$ is _bipartite-submodular_ if there exist two
submodular functions $f_{A}$ and $f_{B}$ defined on $A$ and $B$, respectively,
such that $f(X)=f_{A}(X\cap A)+f_{B}(X\cap B)$ for every $X\subseteq A\cup B$.
The following result appeared in [16].

######  Theorem 1 (Hochbaum).

Given a bipartite graph $G=(A,B;E)$ and a polynomial-time computable
submodular cost function $c\colon 2^{A\cup B}\to E$, the minimum cost vertex
cover problem can be 2-approximated in polynomial time. Furthermore, if $c$ is
also bipartite-submodular, then a minimum cost vertex cover can be found in
polynomial time.

#### Stable matchings.

Let $G=(V,E)$ be an undirected simple graph, and let $<_{u}$ be a linear order
on $N(u)$ for each $u\in V$. The pair $(G,>)$ is called a _stable roommates
instance_. If $G$ is bipartite, then $(G,>)$ is a _stable marriage instance_.
If ties are allowed, i.e., $<_{u}$ are weak orders, then $(G,>)$ is a _stable
roommates instance with ties_. For a stable roommates instance $(G=(V,E),>)$
and a matching $M\subseteq E$, an edge $uv\in E\setminus M$ is _blocking_ if
$u$ prefers $v$ to its partner in $M$ (or has no partner in $M$) and $v$
prefers $u$ to its partner in $M$ (or has no partner in $M$). If no blocking
edge exists, then $M$ is a _stable matching_.

Let $(G,>)$ be a stable roommates instance. A _stable partition of $(G,>)$_ is
a permutation $\pi\colon V\to V$ such that for each $u\in V$, (i) if
$\pi(u)\neq\pi^{-1}(u)$, then $u\pi(u),u\pi^{-1}(u)\in E$ and
$\pi(u)>_{u}\pi^{-1}(u)$, and (ii) for each $v$ adjacent to $u$, if $\pi(u)=u$
or $v>_{u}\pi^{-1}(u)$, then $\pi^{-1}(v)>_{v}u$. The cycles of the
permutation $\pi$ partition the agents into _odd_ and _even cycles_ depending
on the parity of their lengths. We call an agent $u$ a _singleton in $\pi$_ if
$\pi(u)=u$. The following fundamental result is due to Tan [28].

######  Theorem 2 (Tan).

Any stable roomates instance $(G,>)$ admits a stable partition $\pi$, and such
a partition can be found in $\mathcal{O}(|V|^{2})$ time. Furthermore, each
stable partition has the same set of singleton agents and the same set of odd
cycles. There exists a stable matching if and only if there exist a stable
partition without odd cycles of length $\geq 3$.

We will also need the notion of weak stability. Let $(G=(V,E),>)$ be a stable
roommates instance with ties, and let $M\subseteq E$ be a matching. An edge
$uv\in E\setminus M$ _strongly blocks $M$_ if $u$ strictly prefers $v$ to its
partner in $M$ (or has no partner in $M$) and $v$ strictly prefers $u$ to its
partner in $M$ (or has no partner in $M$). If no strongly blocking edge
exists, then $M$ is a _weakly stable matching_.

We also consider cases where the vertices of $G$ have nonnegative integer
capacities $q(v)$. In such an instance, we call $M\subseteq E$ a $q$-matching
if $|M(v)|\leq q(v)$ for each $v\in V$. A vertex is _unsaturated_ in $M$ if
$|M(v)|<q(v)$. We say that an edge $uv\in E\setminus M$ blocks $M$ if both $u$
and $v$ are either unsaturated by $M$ or strictly prefer the other to some of
their partners in $M$. The $q$-matching $M$ is called a stable $q$-matching if
it is not blocked by any edge. We also say that an edge $uv\in E\setminus M$
is dominated at $u$ if $|M(u)|=q(u)$ and for all $xu\in M(u)$, we have
$x>_{u}v$. Clearly a $q$-matching $M$ is stable if and only if each $uv\in
E\setminus M$ is dominated at either $u$ or $v$.

The hardness of the following problem, proved by Manlove et al. [23], is a
useful tool for proving NP-completeness of various stable matching problems.

com-smti
Input: An instance $(G=(A,B;E),>)$ of the stable marriage problem in which
ties only occur at some vertices in $B$ with exactly two neighbors. Question:
Is there a perfect weakly stable matching?

The following two versions of the stable marriage with ties problem was proven
to be NP-complete by Cseh and Heeger [8].

1-forced-smti
Input: An instance $(G=(A,B;E),>)$ of the stable marriage problem with ties
and a forced edge $e\in E$. Question: Is there a weakly stable matching
containing $e$?

1-forbidden-smti
Input: An instance $(G=(A,B;E),>)$ of the stable marriage problem with ties
and a forbidden edge $f\in E$. Question: Is there a weakly stable matching not
containing $f$?

A _one-sided preference model_ involves a bipatite graph $G=(A,B;E)$ and
linear orders $>_{a}$ on $N(a)$ for every $a\in A$. A matching $M$ is _Pareto-
optimal_ if there is no matching $M^{\prime}$ that is better than $M$ for some
agent in $A$, and at least as good as $M$ for the other agents in $A$. Some
hardness proofs in Section 5 will be based on the following NP-complete
problem, introduced by Abraham et al. [2].

min-pom
Input: A bipartite graph $G=(A,B;E)$ with preferences for each $a\in A$ and a
non-negative integer $k$. Question: Does there exist a Pareto-optimal matching
of size at most $k$?

Given a bipartite graph $G=(A,B;E)$ with preferences for each $a\in A$ and a
matching $M$, a _coalition_ is a cycle $(a_{1},b_{1},a_{2},\dots,b_{r})$, such
that $a_{i}b_{i}\in M$ for each $i\in[r]$ and each agent prefers $b_{i+1}$ to
$b_{i}$. The matching is _non-wasteful_ if there is no element of $B$ that is
not covered by $M$, but is preferred by an agent in $A$ to his current
partner. Abraham et al. verified the following.

######  Theorem 3 (Abraham et al.).

A matching $M$ (in the one sided preference model) is Pareto-optimal if and
only if it is maximal, non-wasteful, and coalition-free.

##  3 Vertex deletion

In this section, we study the problem of removing vertices so that the
remaining graph has a stable matching. Two variants are considered: in the
first one, the aim is to remove the minimum number of vertices, while in the
second one, an arbitrary number of vertices can be removed, but only from a
given vertex subset $T\subseteq V$.

Let $G=(V,E)$ be a graph with strict preferences $>_{v}$ for each vertex $v\in
V$. A vertex set $S\subseteq V$ is _removable_ if $G-S$ admits a stable
matching. When vertex capacities $q(v)$ are considered, a vertex set
$S\subseteq V$ is removable if $G-S$ admits a stable $q$-matching.

vertex-del-sr
Input: A graph $G=(V,E)$ with strict preferences $>_{v}$ on the vertices and
an integer $k\in\mathbb{Z}_{+}$. Question: Does there exist a removable set
$S\subseteq V$ such that $|S|\leq k$?

vertex-subset-del-sr
Input: A graph $G=(V,E)$ with strict preferences $>_{v}$ on the vertices and a
vertex subset $T\subseteq V$. Question: Does there exist a removable set
$S\subseteq T$?

vertex-del-sqm
Input: A graph $G=(V,E)$ with strict preferences $>_{v}$ and capacities $q(v)$
on the vertices, and an integer $k\in\mathbb{Z}_{+}$. Question: Does there
exist a removable set $S\subseteq V$ such that $|S|\leq k$?

The analogous edge-deletion problems are also of interest, and have already
been studied in the literature. The minimization version is equivalent to
finding a matching that has the smallest possible number of blocking pairs.
This problem was shown to be NP-hard by Abraham et al. [1], even for complete
preference lists. The subset version is equivalent to the following: given an
edge subset $F\subseteq E$, is there a matching in $G$ for which every
blocking edge is in $F$? This problem is called _stable roommates with free
edges_ , and was shown to be NP-complete by Cechlárová and Fleiner [6].

Among the vertex deletion problems, vertex-del-sr was considered by Tan [27]
who gave an algorithm based on Irving’s algorithm [18]. In the following, we
give a significantly simpler algorithm for vertex-del-sr. We also show that
vertex-subset-del-sr is NP-complete. The latter implies that finding a minimum
weight removable set is NP-complete even for vertex weights in $\\{0,1\\}$,
and it is inapproximable, since it is hard to decide if there is a removable
set of weight 0.

We show that it is very easy to determine a minimum cardinality removable
vertex set using a stable partition. The algorithm is presented as Algorithm
1; it chooses an arbitrary vertex from each odd cycle in the stable partition.
Note, however, that a removable set does not necessarily contain a vertex from
each odd cycle, so optimality is not obvious. We show the correctness of the
algorithm in the proof of the theorem below.

Algorithm 1 Algorithm for vertex-del-sr.

1:Input: A graph $G=(V,E)$ with strict preferences $>_{v}$ on the vertices.

2:Output: A smallest removable set $S\subseteq V$ and a stable matching $M$ in
$G-S$.

3:Set $S\leftarrow\emptyset$ and $M\leftarrow\emptyset$.

4:Find a stable partition $\pi$ using Theorem 2.

5:Let $C_{1},\dots,C_{k}$ be the set of odd cycles of $\pi$ of length $\geq
3$, and let $C_{k+1},\dots,C_{l}$ be the set of even cycles of $\pi$. Let
$\\{v^{i}_{0},\dots,v^{i}_{j_{i}}\\}$ denote the vertices of $C_{i}$, where
$\pi(v^{i}_{j_{i}})=v^{i}_{0}$, and $\pi(v^{i}_{j})=v^{i}_{j+1}$ otherwise.

6:for $i=1,\dots,k$ do

7: Set $S\leftarrow S+v^{i}_{0}$ and $M\leftarrow M\cup\\{v_{2j-1}v_{2j}\mid
1\leq j\leq j_{i}/2\\}$.

8:end for

9:for $i=k+1,\dots,l$ do

10: Set $M\leftarrow M\cup\\{v_{2j-2}v_{2j-1}\mid 1\leq j\leq j_{i}/2\\}$.

11:end for

12:return $S$, $M$

######  Theorem 4.

Algorithm 1 runs in in polynomial time and finds a smallest removable set.

###### Proof.

By Theorem 2, the algorithm has polynomial running time. We prove the
correctness in two steps. First, we show that Algorithm 1 outputs a removable
set.

######  Claim 5.

Algorithm 1 outputs a set $S\subseteq V$ and a matching $M$ that is stable in
$G-S$.

###### Proof.

Let $uv$ be an edge of $G-S$ not in $M$; we show that $uv$ is not a blocking
edge. Recall that $\pi$ denotes the stable partition of $(G,>)$ obtained by
applying Tan’s algorithm.

Assume first that at least one of $u$ and $v$ is a singleton in $\pi$, say,
$\pi(u)=u$. Then for any of its neighbors $w\in N(u)$, we have $\pi(w)\neq w$,
$\pi(w)>_{w}u$, and $\pi^{-1}(w)>_{w}u$ since $\pi$ is a stable partition. In
particular, this holds for $v$. Since $v$ is matched to either $\pi(v)$ or
$\pi^{-1}(v)$ in $M$, $uv$ is not a blocking edge.

Consider the case when $\pi(u)\neq u$ and $\pi(v)\neq v$. Since every vertex
in $V\setminus S$ that is not a singleton in $\pi$ gets a partner in $M$, both
$u$ and $v$ are matched by the algorithm. If $u\neq\pi(v)$ and $v\neq\pi(u)$,
then $\pi(v)>_{v}u,\pi^{-1}(v)>_{v}u$ or $\pi(u)>_{u}v,\pi^{-1}(u)>_{u}v$ hold
as $\pi$ is a stable partition. As $u$ is matched to one of the vertices
$\pi(u),\pi^{-1}(u)$ and $v$ is matched to one of the vertices
$\pi(v),\pi^{-1}(v)$, $uv$ is not a blocking edge. Therefore we may assume
that $\pi(u)=v$. However, as $u$ and $v$ are not in $S$ and $uv$ is not in
$M$, $v$ is matched to $\pi(v)$ in $M$. By $\pi(v)>_{v}u$, $uv$ is not a
blocking edge. ∎

It remains to show that the size of a removable set cannot be smaller than the
number of odd cycles in a stable partition.

######  Claim 6.

The minimum size of a removable set is equal to the number of odd cycles of
length at least $3$ in any stable partition $\pi$.

###### Proof.

Let $S^{*}$ be a removable set, and let $M^{*}$ be a stable matching in
$G-S^{*}$. Since $\pi$ is a stable partition, every odd cycle of length at
least $3$ in $\pi$ must either have a vertex in $S^{*}$ or a vertex $u$
matched in $M^{*}$ to a partner better than $\pi^{-1}(u)$. Indeed, if this
does not hold for a cycle, then there is a vertex $v$ in the cycle that is
unmatched or matched to a worse partner than $v\pi(v)$ and $v\pi^{-1}(v)$. But
then $\pi^{-1}(v)v$ blocks, since $\pi^{-1}(v)$ is not matched to anyone that
is better than $v$ by our assumption. We call a vertex $v\in V\setminus S^{*}$
_out-dominated_ if it is matched in $M^{*}$ to a vertex $u\neq\pi(v)$ with
$u>_{v}\pi^{-1}(v)$. A vertex $u$ is an _in-dominator_ if it is the partner in
$M^{*}$ of an out-dominated vertex $v$. Note that $u$ prefers $\pi(u)$ and
$\pi^{-1}(u)$ to $v$ because $\pi$ is a stable partition.

Let $C=\\{v_{1},\dots,v_{t}\\}$ be an arbitrary cycle of length at least 2 in
$\pi$ such that $\pi(v_{i})=v_{i+1}$, and let $v_{i_{1}},\dots,v_{i_{z}}$ be
the in-dominator vertices in $C$. Observe that these vertices are pairwise
non-adjacent on the cycle $C$ as an adjacent pair would block $M^{*}$. Also,
each of $v_{i_{1}-1},\dots,v_{i_{z}-1}$ must be either in $S^{*}$ or out-
dominated. Indeed, if for some $1\leq j\leq z$ the vertex $v_{i_{j}-1}$ is not
in $S^{*}$ and also not out-dominated, then the edge $v_{i_{j}-1}v_{i_{j}}$
blocks as $v_{i_{j}}$ is an in-dominator.

Suppose now that $t$ is odd. We claim that there is at least one vertex in
$C\setminus\\{v_{i_{1}-1},\dots,v_{i_{z}-1}\\}$ that is either in $S^{*}$ or
is out-dominated. To see this, consider the paths obtained by removing the
vertices $\\{v_{i_{1}-1},v_{i_{1}},\dots,v_{i_{z}-1},v_{i_{z}}\\}$ from $C$.
Since $t$ is odd, one of the paths contains an odd number of vertices; we may
assume that this path is $v_{1},\dots,v_{p}$ for some odd $p$. If none of
these vertices is deleted or out-dominated, then at least one them, say
$v_{i}$, must be unmatched or matched in $M^{*}$ to a vertex worse than
$\pi^{-1}(v_{i})$. If $i\neq 1$, then $v_{i-1}v_{i}$ blocks $M^{*}$, a
contradiction. If $i=1$, then $v_{t}=\pi^{-1}(v_{1})$ is an in-dominator as
$v_{1}$ is the first vertex of the path. This implies that $v_{t}v_{1}$ blocks
$M^{*}$, a contradiction again. That is, at least one of the vertices
$v_{1},\dots,v_{p}$ is deleted or out-dominated.

We conclude that the number of in-dominators in each odd cycle $C$ is at most
the sum of the numbers of out-dominated and deleted vertices in $C$ minus one.
If $C$ is an even cycle, then the number of in-dominators is at most the sum
of the numbers of out-dominated and deleted vertices. Finally, a singleton in
$\pi$ cannot be an in-dominator. It follows from the definitions that the
number of in-dominators and the number of out-dominated vertices are the same.
By combining these observations, we get that $|S^{*}|$ is at least the number
of odd cycles in $\pi$. ∎

The theorem follows by Claims 5 and 6. ∎

We now show that the subset version of the problem is hard.

######  Theorem 7.

vertex-subset-del-sr is NP-complete.

###### Proof.

The problem is clearly in NP. To show hardness, we reduce from com-smti, see
the definition in Section 2.

Consider an instance $(G=(A,B;E),>)$ of com-smti, where
$A=\\{a_{1},\dots,a_{n}\\}$, $B=\\{b_{1},\dots,b_{n}\\}$, and ties are
restricted to a subset $b_{1},\dots,b_{\ell}$, each of which have two
neighbors. We create an instance of vertex-subset-del-sr as follows, see
Figure 1(b) for an example. For each $a_{i}\in A$, we add three agents
$a^{\prime}_{i}$, $x_{i}$ and $x_{i}^{\prime}$. For each $i\in[\ell]$, we add
three agents $b_{i}^{\prime}$, $b_{i}^{\prime\prime}$ and $y_{i}$. Finally,
for $i=\ell+1,\dots,n$, we add an agent $b_{i}^{\prime}$. Let
$T\coloneqq\\{b_{i}^{\prime}\mid i\in[n]\\}\cup\\{b_{i}^{\prime\prime}\mid
i\in[\ell]\\}\cup\\{y_{i}\mid i\in[\ell]\\}$.

The preference lists of the vertices $a^{\prime}_{i}$ for $i\in[n]$ and
$b^{\prime}_{i}$ for $i=\ell+1,\dots,n$ are inherited from the original
instance. We further extend the preferences as follows:

  * •

we add $x_{i}>x_{i}^{\prime}$ to the end of each $a_{i}^{\prime}$’s preference
lists,

  * •

$x_{i}$ has preference $x_{i}^{\prime}>a_{i}^{\prime}$ and $x_{i}^{\prime}$
has preference $a_{i}^{\prime}>x_{i}$,

  * •

$y_{i}$ has preference $b_{i}^{\prime\prime}>b_{i}^{\prime}$,

  * •

if $i\in[\ell]$ and $b_{i}$’s two neighbors were $a_{j}$ and $a_{k}$ with
$j<k$, then $b_{i}^{\prime}$’s preference is
$y_{i}>b_{i}^{\prime\prime}>a_{j}^{\prime}$ and $b_{i}^{\prime\prime}$’s
preference is $b_{i}^{\prime}>y_{i}>a_{k}^{\prime}$.

(a) An instance of com-smti with ties at $b_{1}$. Thick edges form a perfect
weakly stable matching $M$.

(b) The corresponding vertex-subset-del-sr instance with
$T=\\{b_{1}^{\prime},b_{1}^{\prime\prime},y_{1},b_{2}^{\prime}\\}$. Thick
edges form a stable matching $M^{\prime}$ after deleting $y_{1}$ and
$b_{1}^{\prime\prime}$.

(c) The corresponding vertex-del-sqm instance with capacity $3$ for vertices
$b_{1}^{\prime}$, $b_{1}^{\prime\prime}$, $s^{1}_{1}$ and $z^{1}_{1}$, and $1$
otherwise. Thick edges form a stable $q$-matching $M^{\prime}$ after deleting
$b_{1}^{\prime\prime}$.

Figure 1: Illustrations of Theorems 7 and 10. Higher values correspond to
higher preferences.

Let $(G^{\prime},>^{\prime},T)$ denote the obtained instance of vertex-subset-
del-sr. We claim that there exists a perfect weakly stable matching in $(G,>)$
if and only if there exists a removable set $S\subseteq T$ in
$(G^{\prime},>^{\prime},T)$. First suppose there is a perfect weakly stable
matching $M$. We create a matching $M^{\prime}$ in $G^{\prime}$ by adding
$a_{i}^{\prime}b_{j}^{\prime}$ or $a_{i}^{\prime}b_{j}^{\prime\prime}$ for
each $a_{i}b_{j}\in M$ and $x_{i}x_{i}^{\prime}$ for $i\in[n]$. Then, for
every $i\in[\ell]$, we delete $y_{i}$ and the unmatched copy of $b_{i}$.
Suppose there is a blocking edge to $M^{\prime}$. It cannot contain $x_{i}$ or
$x_{i}^{\prime}$, since each $a_{i}^{\prime}$ is with a better partner. On the
other hand, if there is a blocking edge of type
$a_{i}^{\prime}b_{j}^{\prime}$, then $j>\ell$, since $b_{j}^{\prime}$ is
matched with the best remaining partner if $j\leq\ell$. But by the definition
of $>^{\prime}$, this means that $a_{i}b_{j}$ is blocking $M$, a
contradiction.

For the other direction, suppose there is a set $S\subseteq T$ such that there
is a stable matching $M^{\prime}$ in $G^{\prime}-S$. Each $a_{i}$ must be
matched to some $b_{j}^{\prime}$ or $b_{j}^{\prime\prime}$, since otherwise
there would be no stable matching because of the cycle
$\\{a_{i}^{\prime},x_{i},x_{i}^{\prime}\\}$. Also, for any $j\in[\ell]$, at
most one of $b_{j}^{\prime}$ and $b_{j}^{\prime\prime}$ can be matched to some
$a_{i}^{\prime}$, since otherwise $b_{j}^{\prime}b_{j}^{\prime\prime}$ would
be a blocking edge. Therefore, $M^{\prime}$ induces a perfect matching $M$ in
the original instance. If there is an edge blocking $M$, then the copy of the
same edge is blocking $M^{\prime}$, contradiction. ∎

######  Remark 8.

vertex-subset-del-sr is NP-complete even in the special case when $G$ is
complete. In the reduction above, we can add the remaining edges to the end of
the agents’ preference lists, such that they are strictly worse than any
original edge.

######  Remark 9.

It also follows from Theorem 7 that the weighted version of vertex-del-sr is
NP-complete too. This can be seen from the fact that if we let the vertices of
$T$ have weight 0 and other vertices have weight 1, then there is a removable
set of weight 0 if and only if there is a removable set $S\subseteq T$.

Finally, we investigate vertex-min-del-sqm. The only difference now is that
each vertex $v$ has a nonnegative integer capacity $q(v)$, and the aim is to
achieve the existence of a stable $q$-matching by removing a minimum number of
vertices. Note that if the aim was to decrease the vertex capacities by a
minimum total amount, then the problem would be polynomial-time solvable.
Indeed, it could be reduced to vertex-del-sr by making $q(v)$ copies of each
vertex. However, if we look for a minimal size removable set $S\subseteq V$,
then the problem becomes NP-hard.

######  Theorem 10.

vertex-del-sqm is NP complete even if the capacities are at most $3$.

###### Proof.

The problem is clearly in NP. To show hardness, we reduce from com-smti, see
the definition in Section 2.

Consider an instance $(G=(A,B;E),>)$ of com-smti, where
$A=\\{a_{1},\dots,a_{n}\\}$, $B=\\{b_{1},\dots,b_{n}\\}$, and ties are
restricted to a subset $b_{1},\dots,b_{\ell}$, each of which have two
neighbors. We create an instance of vertex-del-sqm as follows, see Figure 1(c)
for an example. For each $a_{i}\in A$, we add three agents $a_{i}^{\prime}$,
$x_{i}$ and $x_{i}^{\prime}$ with
$q(a_{i}^{\prime})=q(x_{i})=q(x_{i}^{\prime})=1$. For each $i\in[\ell]$, we
add a gadget $G_{i}$ with eight agents $b_{i}^{\prime}$,
$b_{i}^{\prime\prime}$, $s_{i}^{1}$, $s_{i}^{2}$, $s_{i}^{3}$ and $z_{i}^{1}$,
$z_{i}^{2}$, $z_{i}^{3}$. Among these agents,
$q(b_{i}^{\prime})=q(b_{i}^{\prime\prime})=q(s_{i}^{1})=q(z_{i}^{1})=3$ and
$q(s_{i}^{2})=q(s_{i}^{3})=q(z_{i}^{2})=q(z_{i}^{3})=1$. Finally, for
$i=\ell+1,\dots,n$, we add an agent $b_{i}^{\prime}$ with
$q(b_{i}^{\prime})=1$. For $i\in[\ell]$, let $a_{i_{1}}^{\prime}$ and
$a_{i_{2}}^{\prime}$ denote the two neighbors of $b_{i}$ where $i_{1}<i_{2}$.

The preference lists of the vertices $a_{i}^{\prime}$ for $i\in[n]$ and
$b^{\prime}_{i}$ for $i=\ell+1,\dots,n$ are inherited from the original
instance. We further extend the preferences as follows:

  * •

we add $x_{i}>x_{i}^{\prime}$ to the end of each $a_{i}^{\prime}$’s preference
lists,

  * •

$x_{i}$ has preference $x_{i}^{\prime}>a_{i}^{\prime}$ and $x_{i}^{\prime}$
has preference $a_{i}^{\prime}>x_{i}$,

  * •

for $i\in[\ell]$, the agents have the following preferences:
$\displaystyle b_{i}^{\prime}\colon{}$
$\displaystyle{}s_{i}^{1}>z_{i}^{1}>a_{i_{1}}^{\prime}$ $\displaystyle
b_{i}^{\prime\prime}\colon{}$
$\displaystyle{}s_{i}^{1}>z_{i}^{1}>a_{i_{2}}^{\prime}$ $\displaystyle
s_{i}^{1}\colon{}$
$\displaystyle{}b_{i}^{\prime}>b_{i}^{\prime\prime}>s_{i}^{2}>s_{i}^{3}$
$\displaystyle s_{i}^{2}\colon{}$ $\displaystyle{}s_{i}^{3}>s_{i}^{1}$
$\displaystyle s_{i}^{3}\colon{}$ $\displaystyle{}s_{i}^{1}>s_{i}^{2}$
$\displaystyle z_{i}^{1}\colon{}$
$\displaystyle{}b_{i}^{\prime}>b_{i}^{\prime\prime}>z_{i}^{2}>z_{i}^{3}$
$\displaystyle z_{i}^{2}\colon{}$ $\displaystyle{}z_{i}^{3}>z_{i}^{1}$
$\displaystyle z_{i}^{3}\colon{}$ $\displaystyle{}z_{i}^{1}>z_{i}^{2}.$

Let $(G^{\prime}=(V^{\prime},E^{\prime}),>^{\prime},q)$ denote the obtained
instance of vertex-del-sqm and set $k=\ell$. We claim that there is a perfect
weakly stable matching $M$ in $(G,>)$ if and only if there is a removable set
$S\subseteq V^{\prime}$ with $|S|\leq k$ in $(G^{\prime},>^{\prime},q)$. We
start with an important observation.

######  Claim 11.

The gadget $G_{i}$ has no stable $q$-matching for $i\in[\ell]$. Furthermore,
if $v\in V(G_{i})$ is a vertex such that $G_{i}-v$ admits a stable
$q$-matching, then $v\in\\{b_{i}^{\prime},b_{i}^{\prime\prime}\\}$.

###### Proof.

Let $G_{i}$ be one of the gadgets. To see that $G_{i}$ does not admit a stable
$q$-matching, observe that since
$q(b_{i}^{\prime})=q(b_{i}^{\prime\prime})=q(s_{i}^{1})=q(z_{i}^{1})=3$, all
of them can get their two best partners, so the edges
$b_{i}^{\prime}s_{i}^{1}$, $b_{i}^{\prime}z_{i}^{1}$,
$b_{i}^{\prime\prime}s_{i}^{1}$ and $b_{i}^{\prime\prime}z_{i}^{1}$ must be
contained in any stable $q$-matching. But then $s_{i}^{1}$ has only one
remaining capacity for $s_{i}^{2}$ and $s_{i}^{3}$. Thus there exists no
stable $q$-matching as one of $s_{i}^{3}s_{i}^{1}$, $s_{i}^{1}s_{i}^{2}$ and
$s_{i}^{2}s_{i}^{3}$ blocks.

Suppose now that $v\in V(G_{i})$ is such that $G_{i}-v$ admits a stable
$q$-matching. If $v\in\\{s_{i}^{1},s_{i}^{2},s_{i}^{3}\\}$, then, since
$z_{i}^{1}$ is the best remaining choice for both $b_{i}^{\prime}$ and
$b_{i}^{\prime\prime}$, and $b_{i}^{\prime}$ and $b_{i}^{\prime\prime}$ are
the best two choices for $z_{i}^{1}$, the edges $b_{i}^{\prime}z_{i}^{1}$ and
$b_{i}^{\prime\prime}z_{i}^{1}$ are contained in any stable $q$-matching. But
then $z_{i}^{1}$ has only one remaining capacity for $z_{i}^{2}$ and
$z_{i}^{3}$, thus there exists no stable $q$-matching.

The case when $v\in\\{z_{i}^{1},z_{i}^{2},z_{i}^{3}\\}$ can be proved
analogously. ∎

Suppose there is a perfect weakly stable matching $M$. We create a
$q$-matching $M^{\prime}$ in $G^{\prime}$ by adding
$a_{i}^{\prime}b_{j}^{\prime}$ or $a_{i}^{\prime}b_{j}^{\prime\prime}$ for
each $a_{i}b_{j}\in M$ and $x_{i}x_{i}^{\prime}$ for $i\in[n]$. Then, for
every $i\in[\ell]$, we delete the copy of $b_{i}$ not matched to
$A^{\prime}=\\{a_{i}^{\prime}\mid i\in[n]\\}$. Then, if $b_{i}^{\prime}$ got
deleted, we add the edges of
$N_{i}^{\prime}=\\{b_{i}^{\prime\prime}s_{i}^{1},b_{i}^{\prime\prime}z_{i}^{1},s_{i}^{1}s_{i}^{2},s_{i}^{1}s_{i}^{3},z_{i}^{1}z_{i}^{2},z_{i}^{1}z_{i}^{3}\\}$
to $M^{\prime}$ and otherwise we add
$N_{i}^{\prime\prime}=\\{b_{i}^{\prime}s_{i}^{1},b_{i}^{\prime}z_{i}^{1},s_{i}^{1}s_{i}^{2},s_{i}^{1}s_{i}^{3},z_{i}^{1}z_{i}^{2},z_{i}^{1}z_{i}^{3}\\}$.
The number of deleted vertices is then exactly $k$. Suppose there is a
blocking edge to $M^{\prime}$. It cannot contain $x_{i}$ or $x_{i}^{\prime}$,
since each $a_{i}$ is with a better partner. If there is a blocking edge of
type $a_{i}^{\prime}b_{j}^{\prime}$, then $j>\ell$, since $b_{j}^{\prime}$ (or
$b_{j}^{\prime\prime})$ is matched with all of its partners if $j\leq\ell$.
But by the definition of $>^{\prime}$, this means that $a_{i}b_{j}$ is
blocking $M$, contradiction. Finally, the edges $s_{j}^{2}s_{j}^{3}$ and
$z_{j}^{2}z_{j}^{3}$ also do not block $M^{\prime}$, because $s_{j}^{3}$ and
$z_{j}^{3}$ are matched with their best partner in $M^{\prime}$ for each
$j\leq\ell$.

Now assume that there is a set $S\subseteq V^{\prime}$ with $|S|\leq k$ such
that there is a stable $q$-matching $M^{\prime}$ in $G^{\prime}-S$. Each
$a_{i}^{\prime}$ must be matched to some $b_{j}^{\prime}$ or
$b_{j}^{\prime\prime}$, since otherwise there would be no stable matching
because of the cycle $\\{a_{i}^{\prime},x_{i},x_{i}^{\prime}\\}$. Also, for
any $j\in[\ell]$, at most one of $b_{j}^{\prime}$ and $b_{j}^{\prime\prime}$
can be matched to some $a_{i}^{\prime}$, since by claim 11 one of them has to
be deleted, otherwise there would be a gadget $G_{i}$ where at least two
vertices are deleted (it is also clear that deleting vertices outside
$V(G_{i})$ cannot create a stable $q$-matching in $G_{i}$), contradicting
$|S|\leq k$. Therefore, $M^{\prime}$ induces a perfect matching $M$ in the
original instance. If there is an edge blocking $M$, then the copy of the same
edge is blocking $M^{\prime}$, contradiction. ∎

##  4 Preference modifications

In this section, we consider problems where the goal is to make a given
matching stable by bribing the agents to change their preferences. Each agent
$v$ assigns a nonnegative real number $p_{v}(u)$ to each acceptable partner
$u$. By abuse of notation, we extend this notation to edges incident to $v$ by
setting $p_{v}(uv)\coloneqq p_{v}(u)$, and call this the _value_ of the edge
$uv$ for $v$. The weak preference list of $v$ is derived from these values by
declaring $u\geq_{v}u^{\prime}$ if and only if $p_{v}(u)\geq
p_{v}(u^{\prime})$. The agents might also have positive integer capacities,
denoted by $q(v)$ for agent $v$.

The cost of modifying the preferences can be measured in various ways; here,
we concentrate on the case of $\ell_{1}$-norm. That is, changing the value of
$p_{v}(u)$ from $a$ to $b$ has cost $|a-b|$. If $p^{\prime}$ denotes the
modified preference values, then the _cost of $p^{\prime}$ (with respect to
$p$)_ is $\operatorname{cost}(p^{\prime})\coloneqq\sum_{v\in V}\sum_{u\in
N(v)}|p_{v}(u)-p^{\prime}_{v}(u)|$. The goal is to find a new preference
matrix $p^{\prime}$ of minimum cost such that a given b-matching $M$ becomes
weakly stable with respect to $p^{\prime}$.

$\ell_{1}$-min-pm
Input: A maximal $q$-matching $M$ and a matrix $p$ describing the preferences
of the agents. Goal: Preferences $p^{\prime}$ of minimum cost such that $M$ is
weakly stable with respect to $p^{\prime}$.

First we show that the problem is not only NP-hard in general, but it is also
hard to approximate within a factor better than 2.

######  Theorem 12.

$\ell_{1}$-min-pm is NP-hard even if each capacity is one. Furthermore,
assuming the Unique Games Conjecture, it cannot be approximated within a
factor of $2-\varepsilon$ for any $\varepsilon>0$.

###### Proof.

Observe that if each capacity is 1, then there always exists an optimal
solution that changes the values only on the edges of $M$. Indeed, lowering
the value of a non-matching edge $uv$ to become dominated at vertex $v$ has
the same cost as increasing the value of the edge in $M(v)$ for $v$ to
dominate $uv$. By doing the latter, we are surely better off as other edges
may become dominated too at $v$, while in the first case we do not make any
progress on dominating the other edges.

The problem is clearly in NP. To show NP-hardness, we reduce from vertex-
cover. Let $G=(V,E)$ be an instance of the minimum vertex cover problem. We
construct an instance $(G^{\prime}=(V^{\prime},E^{\prime}),p,M)$ of
$\ell_{1}$-min-pm. Let $V^{\prime}=\\{v^{\prime},v^{\prime\prime}\mid v\in
V\\}$ and $E^{\prime}=\\{u^{\prime}v^{\prime}\mid uv\in
E\\}\cup\\{v^{\prime}v^{\prime\prime}\mid v\in V\\}$. Furthermore, set
$M=\\{v^{\prime}v^{\prime\prime}\mid v\in V\\}$. For each vertex $v\in V$, we
define $p_{v^{\prime}}(v^{\prime\prime})=p_{v^{\prime\prime}}(v^{\prime})=0$
and set all the other $p_{v^{\prime}}(u^{\prime})$ values to be 1, see Figure
2.

(a) An instance of vertex-cover. Note that $\\{a,c\\}$ is a vertex cover of
minimum size.

(b) The corresponding $\ell_{1}$-min-pm instance. If the values of
$p_{a^{\prime}}(a^{\prime}a^{\prime\prime})$ and
$p_{c^{\prime}}(c^{\prime}c^{\prime\prime})$ are increased to $1$, then thick
edges form a weakly stable matching.

Figure 2: An illustration of Theorem 12. Higher values correspond to higher
preferences.

Let $p^{\prime}$ be a minimum cost solution of the $\ell_{1}$-min-pm instance
thus obtained. By the observation above, we may assume that $p^{\prime}$
differs from $p$ only on edges of $M$. Since vertices in
$\\{v^{\prime\prime}\mid v\in V\\}$ are matched with their only partner, their
preference values do not change. Clearly, for each vertex $v^{\prime}$, we
have either $p^{\prime}_{v^{\prime}}(v^{\prime\prime})=0$ or
$p^{\prime}_{v^{\prime}}(v^{\prime\prime})=1$. Furthermore, at least one of
the end vertices of each original edge increases the value of the incident
matching edge to $1$, hence the set of such vertices forms a vertex cover.
Vice versa, if we increase the values of the matching edges on the vertices of
a vertex cover, then no original edge of $G$ blocks $M$.

By the above, minimum vertex cover in $G$ is equivalent to $\ell_{1}$-min-pm
in $(G^{\prime},p,M)$, concluding the proof of NP-hardness. Assuming the
Unique Games Conjecture, vertex-cover cannot be approximated within a factor
better than $2$ by a result of Khoth and Regev [19], implying the second half
of the theorem. ∎

As a positive result, we show that $\ell_{1}$-min-pm is polynomial-time
solvable in bipartite graphs. Interestingly, our solution relies on Hochbaum’s
algorithm for the minimum cost vertex cover problem under bipartite-submodular
functions.

######  Theorem 13.

$\ell_{1}$-min-pm can be solved in polynomial time in bipartite graphs.

###### Proof.

We reduce $\ell_{1}$-min-pm to a minimum weight vertex cover problem in a
bipartite graph with a polynomial-time computable bipartite-submodular cost
function. Recall that, by Theorem 1, the latter problem is solvable in
polynomial time.

Let $G=(A,B;E)$ be the bipartite graph and $M$ be a fixed $q$-matching. We
first start with a series of preprocessing steps. If the $q$-matching $M$ is
not maximal, then the problem is infeasible and we stop. Otherwise, we iterate
through all edges and check whether they are already dominated. If an edge is
already dominated, then we delete it. This can be done as there always exists
an optimal solution that does not decrease the values on $M$ and does not
increase the values on $E\setminus M$. Therefore, we may assume that the
$q$-matching $M$ is maximal and all edges outside $M$ are blocking edges.

We construct an an auxiliary bipartite graph $H=(U,W;F)$ as follows. For each
vertex $v$, we add $\ell_{v}$ copies $v_{1},\dots,v_{\ell_{v}}$ of $v$, where
$\ell_{v}$ is the number of edges in $E(v)\setminus M(v)$. These vertices are
added to $U$ if $v\in A$ and to $W$ if $v\in B$. For each vertex $v$, consider
an arbitrary ordering $e_{1}^{v},\dots,e_{\ell_{v}}^{v}$ of the non-matching
edges incident to $v$. Then we define the edges of $H$ as follows:
$u_{i}v_{j}\in F$ if and only if $uv\in E\setminus M$, $uv=e_{i}^{u}$, and
$uv=e_{j}^{v}$.

Now we define an LP for each vertex $v$ saturated by $M$ and each subset
$\\{e^{v}_{j_{1}},\dots,e^{v}_{j_{k}}\\}$ of
$\\{e_{1}^{v},\dots,e_{\ell_{v}}^{v}\\}$:

($LP_{v}(v_{j_{1}},\dots,v_{j_{k}})$)
$\begin{array}[]{rlr}\min&\displaystyle\sum_{e\in
E(v)}|x(e)-p_{v}(e)|\\\\[15.0pt] \text{s.\,t.}&0\leq
x(e^{v}_{j_{i}})\leq\min_{e\in M(v)}x(e)&\qquad\text{for $1\leq i\leq
k$}\end{array}$

Though the above formulation is not an LP, both the objective function and the
constraints can be linearized using standard techniques. It is not difficult
to see that the optimum value of the LP is exactly the minimum cost of
dominating all of $\\{e_{j_{1}},\dots,e_{j_{k}}\\}$ at $v$ by changing the
values of the edges. We denote the optimum value by
$\operatorname{OPT}_{v}(v_{j_{1}},\dots,v_{j_{k}})$. If $v$ is not saturated
by $M$, then $\operatorname{OPT}_{v}(v_{j_{1}},\dots,v_{j_{k}})$ is defined to
be $+\infty$, since then no edge can be dominated at $v$. By the maximality of
$M$, at least one endpoint of each blocking edge is saturated, so we know that
there exists a solution.

For each vertex $v\in A\cup B$, we define a function $f_{v}$. Let $X\subseteq
U\cup W$. If $X\cap\\{v_{1},\dots,v_{\ell_{v}}\\}=\emptyset$, then define
$f_{v}(X)\coloneqq 0$. Otherwise, if
$X\cap\\{v_{1},\dots,v_{\ell_{v}}\\}=\\{v_{j_{1}},\dots,v_{j_{k}}\\}$, then
define $f_{v}(X)=f_{v}(\\{v_{j_{1}},\dots,v_{j_{k}}\\})\coloneqq
OPT_{v}(v_{j_{1}},\dots,v_{j_{k}})$.

######  Claim 14.

For each $v\in A\cup B$, $f_{v}$ is submodular.

###### Proof.

Our goal is to show that for any set $X\subseteq U\cup W$ and any two distinct
elements $x,y\in(U\cup W)\setminus X$, we have $f_{v}(X+x+y)+f_{v}(X)\leq
f_{v}(X+x)+f_{v}(X+y)$. If the left hand side is $+\infty$, then $v$ must be
unsaturated by $M$ and $X\cup\\{x,y\\}$ must contain a vertex from
$\\{v_{1},\dots,v_{\ell_{v}}\\}$, hence the right hand side is also $+\infty$.
Thus, we may assume that the left hand side is finite.

If $x\notin\\{v_{1},\dots,v_{\ell_{v}}\\}$, then the inequality holds by
$f_{v}(X+x+y)=f_{v}(X+y)$ and $f_{v}(X+x)=f_{v}(X)$, while if
$y\notin\\{v_{1},\dots,v_{\ell_{v}}\\}$, then the inequality holds by
$f_{v}(X+x+y)=f_{v}(X+x)$ and $f_{v}(X+y)=f_{v}(X)$.

It only remains to consider the case when
$x,y\in\\{v_{1},\dots,v_{\ell_{v}}\\}$. Let $e$ and $f$ be the edges of $H$
incident to $x$ and $y$, respectively. By symmetry, we may assume that
$p_{v}(e)\leq p_{v}(f)$. Let $z_{1}$ be an optimal solution for
$LP_{v}((X+x)\cap\\{v_{1},\dots,v_{\ell_{v}}\\})$ and $z_{2}$ be an optimal
solution for $LP_{v}((X+y)\cap\\{v_{1},\dots,v_{\ell_{v}}\\})$. If one of them
is a feasible solution for
$LP_{v}((X+x+y)\cap\\{v_{1},\dots,v_{\ell_{v}}\\})$, then since the other is a
feasible solution of $LP_{v}(X\cap\\{v_{1},\dots,v_{\ell_{v}}\\})$, we get
$f_{v}(X+x+y)+f_{v}(X)\leq f_{v}(X+x)+f_{v}(X+y)$.

Otherwise, $f$ is not dominated when the edge values are set to $z_{1}$, and
$e$ is not dominated when the edge values are set to $z_{2}$. Since
$p_{v}(e)\leq p_{v}(f)$, this means that $z_{2}(f)=\min_{g\in
M(v)}z_{2}(g)<z_{2}(e)=p_{v}(e)\leq p_{v}(f)$. To see this, observe that
$p_{v}(f)\geq\min_{g\in M(v)}p_{v}(g)$ as non-blocking edges were deleted
during the preprocessing step, and that setting the value of $z_{2}(f)$ below
$\min_{g\in M(v)}z_{2}(g)$ or setting $z_{2}(e)\neq p_{v}(e)$ would be
suboptimal. An analogous reasoning shows $z_{1}(e)=\min_{g\in
M(v)}z_{1}(g)<z_{1}(f)=p_{v}(f)$. We distinguish two cases.

If $z_{1}(e)\leq z_{2}(f)$, then $z_{1}(e)\leq z_{2}(f)=\min_{g\in
M(v)}z_{2}(g)<z_{2}(e)=p_{v}(e)\leq z_{1}(f)$. Consider $z_{1}^{\prime}$ that
is obtained from $z_{1}$ by changing $z_{1}^{\prime}(e)$ to $p_{v}(e)$ and
$z_{2}^{\prime}$ that is obtained from $z_{2}$ by changing $z_{2}^{\prime}(e)$
to $z_{2}(f)$. Then $z_{1}^{\prime}$ is a feasible solution for
$LP_{v}(X\cap\\{v_{1},\dots,v_{\ell_{v}}\\})$, while $z_{2}^{\prime}$ is a
feasible solution for $LP_{v}((X+x+y)\cap\\{v_{1},\dots,v_{\ell_{v}}\\})$. As
the sum of the objective values is at most as much as for $z_{1}$ and $z_{2}$,
we get that $f_{v}(X+x+y)+f_{v}(X)\leq f_{v}(X+x)+f_{v}(X+y)$.

If $z_{2}(f)\leq z_{1}(e)$, then $z_{2}(f)\leq z_{1}(e)\leq
z_{2}(e)=p_{v}(e)\leq z_{1}(f)=p_{v}(f)$. Consider $z_{1}^{\prime}$ that is
obtained from $z_{1}$ by changing $z_{1}^{\prime}(f)$ to $z_{1}(e)$ and
$z_{2}^{\prime}$ that is obtained from $z_{2}$ by changing $z_{2}^{\prime}(f)$
to $p_{v}(f)$. Then $z_{1}^{\prime}$ is a feasible solution for
$LP_{v}((X+x+y)\cap\\{v_{1},\dots,v_{\ell_{v}}\\})$, while $z_{2}^{\prime}$ is
a feasible solution for $LP_{v}(X\cap\\{v_{1},\dots,v_{\ell_{v}}\\})$. As the
sum of the objective values is at most as much as for $z_{1}$ and $z_{2}$, we
get that $f_{v}(X+x+y)+f_{v}(X)\leq f_{v}(X+x)+f_{v}(X+y)$. ∎

Let us define a cost function $c$ on the subsets of $U\cup W$ by
$c(X)\coloneqq\sum_{v\in U}f_{v}(X)+\sum_{v\in W}f_{v}(X)$. Clearly, since
each function $f_{v}$ is submodular and the copies of the same vertex are on
the same side, $c$ is bipartite-submodular. Note that the value of $f_{v}(X)$
can be computed in polynomial time by solving the corresponding LP, hence $c$
is also computable in polynomial time. By Theorem 1, we can find a vertex
cover of $H$ of minimum cost efficiently.

By the nonnegativity of $c$ and the fact that each vertex has degree one in
$H$, there exists an optimal vertex cover that covers exactly one endpoint of
each edge. Such a vertex cover has the same cost as dominating each edge at
the chosen endpoint in an optimal way. This implies that the cost of an
optimum vertex cover is equal to the cost of an optimal preference
modification in the original $\ell_{1}$-min-pm instance. Furthermore, given an
optimal vertex cover, the optimal modified preference values can be determined
by solving the corresponding LPs, concluding the proof of the theorem. ∎

The same reduction can be applied even if the original graph is not bipartite.
However, then it is not possible to put each copy of a vertex on the same side
of the auxiliary graph $H$ (which is a perfect matching), therefore the cost
function $c=\sum f_{v}$ cannot be written as the sum of two submodular cost
functions, which means that, though it is submodular, it is not bipartite-
submodular. Therefore, by Theorem 1, we get the following.

######  Theorem 15.

There is a polynomial-time 2-approximation algorithm for the $\ell_{1}$-min-pm
problem. ∎

Note that, assuming the Unique Games Conjecture, the approximation given by
Theorem 15 is best possible by Theorem 12.

######  Remark 16.

If an arbitrary (not necessarily maximal) $q$-matching $M$ is given and the
goal is to modify the preferences in such a way that there exists a stable
$q$-matching containing $M$, then the problem becomes difficult. Indeed,
deciding the existence of a stable matching containing a given edge in the
stable marriage problem with ties is NP-complete, as was proved by Cseh and
Heeger [8].

######  Remark 17.

If the values are not allowed to be changed on the edges of $M$, then the
problem becomes very simple even for hypergraphs. Indeed, in such a case one
only has to go through the hyperedges $f$ not in $M$ and decrease the value of
$p_{v}(f)$ to $\min_{e\in M(v)}p_{v}(e)$ at a vertex $v$ where the cost of
such a change is minimum, that is, $v\in\operatorname*{arg\,min}_{u\in
f}|p_{u}(f)-\min_{e\in M(u)}p_{u}(e)|$.

The technique described in the proof of Theorem 13 can be extended to a more
general setting. Assume that for each vertex-edge pair $v\in V$ and $e\in
E(v)$, nonnegative lower and upper bounds $\ell_{v}(e),u_{v}(e)$ are given for
the target value of $e$ at $v$. We call this problem $\ell_{1}$-min-pmri
(minimum preference modification with restricted intervals).

$\ell_{1}$-min-pmri
Input: A maximal $q$-matching $M$, a matrix $p$ describing the preferences of
the agents, and nonnegative lower and upper bounds $\ell,u$ on the values of
the modified preferences. Goal: Preferences $p^{\prime}$ of minimum cost such
that $M$ is weakly stable with respect to $p^{\prime}$ and $\ell_{v}(e)\leq
p^{\prime}_{v}(e)\leq u_{v}(e)$ for each $v\in V$, $e\in E(v)$.

Note that this extra condition does not make the problem harder. First, one
can apply the following preprocessing step: if $p_{v}(e)\leq\ell_{v}(e)$ for
some vertex $v$ and $e\in E(v)$, then change the value of $p_{v}(e)$ to
$\ell_{v}(e)$, and if $p_{v}(e)\geq u_{v}(e)$ for some vertex $v$ and $e\in
E(v)$, then change the value of $p_{v}(e)$ to $u_{v}(e)$. It is not difficult
to see that this results in an equivalent problem. After the preprocessing
step, the problem can be simply encoded into LPs as before by changing each
$LP_{v}(v_{j_{1}},\dots,v_{j_{k}})$ as follows:

$\begin{array}[]{rll}\min&\displaystyle\sum_{e\in
E(v)}|x(e)-p_{v}(e)|\\\\[15.0pt] \text{s.\,t.}&0\leq
x(e^{v}_{j_{i}})\leq\min_{e\in M(v)}x(e)&\qquad\text{for $1\leq i\leq k$}\\\
&0\leq x(e)\leq u_{v}(e)&\qquad\text{for $e\in M$}\\\ &\ell_{v}(e)\leq
x(e)&\qquad\text{for $e\in E\setminus M$}\end{array}$

As a consequence, we have the following result.

######  Corollary 18.

$\ell_{1}$-min-pmri can be solved in polynomial time in bipartite graphs, and
admits a polynomial-time 2-approximation in general graphs.

######  Remark 19.

The proposed framework can also be extended to more general cases, for example
when the cost for each individual agent might depend not only of the
$\ell_{1}$ norm of the changes, but on the agent itself - e.g., it might be a
lot more difficult to get some agents to cooperate than others. This can be
modeled by a cost function of the form
$\operatorname{cost}(p^{\prime})=\sum_{v\in V}\sum_{u\in
N(v)}\lambda_{v}|p_{v}(u)-p^{\prime}_{v}(u)|$, where $\lambda_{v}$ is a
constant that depends on the agent $v$. Such a cost function can be encoded in
the LP by multiplying the objective of each
$LP_{v}(v_{j_{1}},\dots,v_{j_{k}})$ by $\lambda_{v}$.

##  5 Preference extension problems

###  5.1 Fixed and arbitrary preferences

Now we turn our attention to problems where the preference list of each agent
is either fixed or can be set arbitrarily. Such problems may arise, for
example, when dealing with cheating strategies, where some of the agents might
submit falsified preferences in order to get a desired stable matching.

Similar problems have been considered before, see e.g. [20, 15]. Kobayashi et
al. [20] investigated problems where each preference list has to be complete.
They showed that if the preferences are fixed for each man, then deciding
whether there are preference lists of the women such that a partial matching
$M$ is included in the men-optimal stable matching is NP-complete. On the
positive side, they showed that if the preferences of all the women unmatched
by $M$ are fixed too, then the problem becomes polynomial-time solvable.

The problems that we consider differ from previous results in several aspects:
the completeness of the preference lists is not always assumed, the underlying
graph might be non-bipartite, and some of the edges might be forced or
forbidden to be contained in a stable matching. It should be emphasized that
we are interested not only in men-optimal stable matchings, but in the
existence of a stable matching satisfying the constraints in general.

The problems that are featured in this section are the followings.

K-forced-sm-strat
Input: A bipartite graph $G=(A,B;E)$, strict preferences $>_{a}$ for each man
$a\in A$, strict preferences $>_{b}$ for some women $b\in B$, and a partial
matching $\mu$ with $|\mu|=K$. Question: Are there preferences for the rest of
the women such that there exists a stable matching containing $\mu$?

K-forbidden-sm-strat
Input: A bipartite graph $G=(A,B;E)$, strict preferences $>_{a}$ for each man
$a\in A$, strict preferences $>_{b}$ for some women $b\in B$, and a set of
forbidden edges $\tau$ with $|\tau|=K$. Question: Are there preferences for
the rest of the women such that there exists a stable matching disjoint from
$\tau$?

sr-strat
Input: A graph $G=(V,E)$ and strict preferences $>_{v}$ for some agents $v\in
V$. Question: Are there preferences for the rest of the agents such that there
exists a stable matching $M$?

First we consider the complexities of 1-forced-sm-strat and 1-forbidden-sm-
strat.

######  Theorem 20.

1-forced-sm-strat and 1-forbidden-sm-strat are NP-complete even if the
preference list is fixed for none of the women.

###### Proof.

We start with the proof for 1-forbidden-sm-strat; the problem is clearly in
NP. To show NP-hardness, we reduce from min-pom, see the definition in Section
2.

Given an instance $(G=(A,B;E),>),k$ of min-pom, we construct another bipartite
graph $H=(U,W;F)$, where $U$ is the set of men and $W$ is the set of women as
follows. Let $n\coloneqq|A|$. We extend the original bipartite graph by adding
$n-k$ women $s_{1},\dots,s_{n-k}$ to $B$ that will be called _selectors_.
Finally, we add two men $u$ and $u^{\prime}$ to $A$ and a woman $w$ to $B$. So
$U=A\cup\\{u,u^{\prime}\\}$ is the set of men and
$W=B\cup\\{w\\}\cup\\{s_{1},\dots,s_{n-k}\\}$ is the set of women in the new
instance. The edges are $F=E\cup\\{s_{i}a_{j}\mid i\in[n-k],a_{j}\in
A\\}\cup\\{u^{\prime}s_{i}\mid i\in[n-k]\\}\cup\\{uw,u^{\prime}w\\}$. The
preferences are fixed only for the men:

  * •

$u$: $w$,

  * •

$u^{\prime}$: $s_{1}>\dots>s_{n-k}>w$,

  * •

$a_{i}$: $[N(a_{i})]>s_{1}>\dots>s_{n-k}$,

where $[N(a_{i})]$ denotes the original neighbors of $a_{i}$ as in $G$ ranked
in their original order, see Figure 3. Finally, let $\tau$ consists of the
single forbidden edge $uw$. We claim that there is a Pareto-optimal matching
of size at most $k$ in $G$ if and only if the preferences of the women can be
set in a way such that there is a stable matching not containing $uv$ in
$G^{\prime}$.

(a) An instance of min-pom. Thick edges form a Pareto-optimal matching $M$.

(b) The corresponding 1-forbidden-sm-strat instance. Thick edges form a stable
matching $M^{\prime}$ not containing $uw$.

Figure 3: An illustration of Theorem 20. Higher values correspond to higher
preferences.

We claim that the original min-pom instance has a solution if and only if the
1-forbidden-sm-strat instance thus obtained does. First suppose there exists a
Pareto-optimal matching $M$ in $G$ of size $k$. Then extend this matching by
assigning $s_{1},\dots,s_{n-k}$ to $n-k$ agents in $A$ who are unassigned in
$M$ arbitrarily, and assign $u^{\prime}$ to $w$. Denote this matching by
$M^{\prime}$. Set the preferences of each woman such that they prefer their
partner the most if they have any, and arbitrarily otherwise. Clearly,
$M^{\prime}$ does not contain $uw$. Suppose there is a blocking edge $xy$
where $x\in U$ and $y\in W$. Then $y$ can only be an unassigned woman, that
is, $y\in B$. This implies that $x\in A$ and either $x$ is unmatched, $x$ is
matched with a selector, or $x$ is matched with a $b_{i}$ in $M^{\prime}$ that
is worse than $y$. In the first two cases $M$ is not maximal, while the third
option means that $M$ is not non-wasteful, a contradiction.

For the other direction, suppose there is a preference extension for the women
and a matching $M^{\prime}$ not containing $uw$ that is stable with respect to
those preferences. This is equivalent to the case where each woman’s
preference list is just a tie and there is a weakly stable matching
$M^{\prime}$ not containing $uw$. Since $uw$ does not block, we have
$u^{\prime}w\in M^{\prime}$. Therefore, each selector woman $s_{i}$ is
assigned, since otherwise they would block with $u^{\prime}$. Let $M$ be the
restriction of $M^{\prime}$ to $(A,B;E)$. The size of $M$ is at most $k$,
because each selector is matched to $A$ and $|A|=n$. We claim that $M$ is non-
wasteful and maximal. If it is not maximal, then there is an edge $ab$ that
can be added, but $ab$ would block $M^{\prime}$. Similarly, if an agent $a$
would prefer an unassigned agent $b$ to $M(a)$, then again $ab$ would block
$M$.

We conclude that there is a maximal and non-wasteful matching $M$ for the
original problem of size at most $k$. If $M$ is coalition-free, then we are
done. Otherwise, if there is a coalition $(a_{1},b_{1},\dots,a_{r},b_{r})$,
then by changing $M$ to $(M\setminus\\{a_{i}b_{i}\mid
i\in[r]\\})\cup\\{a_{i}b_{i+1}\mid i\in[r]\\}$, we get another matching that
covers the same set of vertices, each agent weakly improves, and some agents
strictly improve, so it is still maximal and non-wasteful. By iterating this
step we get a matching $M$ covering the same set of vertices that is maximal,
coalition-free, and non-wasteful, so it is a Pareto-optimal matching of size
at most $k$ by theorem 3.

The forced edge case 1-forced-sm-strat can be proved in a similar way, the
only difference being that $u$ is dismissed from the construction and we set
$\mu$ to contain the single forced edge $u^{\prime}w$. ∎

######  Remark 21.

Kobayashi et al. [20] showed hardness of the problem whether there exist
preferences for the women such that the man-optimal stable matching contains a
given matching $M$. Our results imply that if the graph is not complete, then
the problem remains hard even if the matching consists of a single edge. To
see this, observe that in our construction this problem also reduces to
deciding whether there are preferences for women such that the man-optimal
stable matching matches a given set of women. Indeed, the additional man
$u^{\prime}$ proposes to all of them before proposing to his forced pair $w$,
so they all have to reject him, which is only possible if each of them get a
partner that can be set to be the best on the preference list of the given
woman. Since each stable matching covers the same set of agents, this is
equivalent to deciding whether there is a stable matching that matches all the
original women.

In the proof of Theorem 20, the reduction was based on a non-complete
bipartite graph, e.g., it contained a pendant edge $uw$. We show that the
problems remain NP-complete even in complete bipartite graphs. However, in
this case the preference lists of some women might be fixed.

######  Theorem 22.

1-forced-sm-strat and 1-forbidden-sm-strat are NP-complete even if the graph
is a complete bipartite graph.

###### Proof.

We start with the proof for 1-forbidden-sm-strat; the problem is clearly in
NP. To show NP-hardness, we reduce from com-smti, see the definition in
Section 2.

Consider an instance $I=(G=(A,B;E),>)$ of com-smti, where
$A=\\{a_{1},\dots,a_{n}\\}$, $B=\\{b_{1},\dots,b_{n}\\}$, and ties are
restricted to a subset $b_{1},\dots,b_{\ell}$, each of which have two
neighbors. We construct a 1-forbidden-sm-strat instance $I^{\prime}$ as
follows. We extend the original bipartite graph by adding two men $u$ and
$u^{\prime}$ to $A$ and two women $w$ and $w^{\prime}$ to $B$. That is,
$U=A\cup\\{u,u^{\prime}\\}$ and $W=B\cup\\{w,w^{\prime}\\}$. Finally, $H$ is a
complete graph, that is, $F=\\{xy\mid x\in U,y\in W\\}$, see Figure 4 for an
example.

Let $W_{1}=\\{b_{i}\mid i\in[\ell]\\}$ and $W_{2}=\\{b_{i}\mid\ell<i\leq
n\\}$. The fixed preferences are the following. Each $a_{i}$ has the same
preferences as in $I$ as the top of its preference list, followed by $w$, and
then by the remaining women in any order. Each $b_{i}\in W_{2}$ has the same
preferences as in $I$ as the top of her preference list, followed by the
remaining men in any order. The other fixed preference lists are the
following:

  * •

$w$: $u$ is the least preferred, otherwise arbitrary,

  * •

$w^{\prime}$: $u$, followed by $u^{\prime}$, then the rest in arbitrary order,

  * •

$u$: $w$, followed by $w^{\prime}$, then the rest in arbitrary order,

  * •

$u^{\prime}$: $w^{\prime}$, then the rest in arbitrary order.

Finally, let $\tau$ consists of the single forbidden edge $uw^{\prime}$.

(a) An instance of com-smti with ties at $b_{1}$. Thick edges form a weakly
stable matching $M$.

(b) The corresponding 1-forbidden-sm-strat instance. Thick edges form a stable
matching $M^{\prime}$, independently from the missing preference values.

Figure 4: An illustration of Theorem 22. Higher values correspond to higher
preferences.

We claim that there is a perfect weakly stable matching $M$ in $G$ if and only
if the preferences of the remaining women in $H$ can be set in a way such that
there is a stable matching $M^{\prime}$ avoiding $uw^{\prime}$. First suppose
there is a perfect weakly stable matching $M$ in $I$. Let $M^{\prime}$ be the
matching obtained from $M$ by adding $wu$ and $w^{\prime}u^{\prime}$. We set
the preferences of the women in $W_{1}$ such that the best man for them is
their partner in $M$. We claim that $M^{\prime}$ is stable. Suppose indirectly
that there is a blocking edge $xy$. Then $y$ cannot be $w$ since each man
$a_{i}$ is with an original (and hence better) partner, and $u$ is with a
better partner, too. Furthermore, $y$ cannot be $w^{\prime}$ either, since her
only better partner $u$ is with his best choice. Similarly, $y$ cannot be from
$W_{2}$, since they get their most preferred choices. We conclude that
$y=b_{j}\in W_{2}$ for some $\ell<j\leq n$, so her partner is the same as in
$M$. Thus $x=a_{i}$ for some $1\leq i\leq n$, and $a_{i}$ must be a man in $A$
who prefers $b_{j}$ to his partner in $M$. But then $a_{i}b_{j}$ would block
$M$, a contradiction.

For the other direction, suppose that we can set the preferences of the women
in $W_{1}$ such that there is a stable matching $M^{\prime}$ not containing
$uw^{\prime}$. Since $uw^{\prime}$ does not block, we have $uw\in M^{\prime}$.
This implies that $u^{\prime}w^{\prime}$ must be in $M^{\prime}$, too. So the
agents corresponding to the original ones are matched among each other. Also,
$M^{\prime}$ has to be a perfect matching, since a man not covered by
$M^{\prime}$ would block with $w$. Let $M$ be the perfect matching obtained by
restricting $M^{\prime}$ to $H-\\{u,u^{\prime},w,w^{\prime}\\}$. If $M$ is not
weakly stable in the original instance, then there exists a blocking edge
between a woman $b_{j}$ where $j>\ell$ and a man $a_{i}$, but then
$a_{i}b_{j}$ would block $M^{\prime}$ too, a contradiction.

The forced edge case 1-forced-sm-strat can be proved in a similar way, the
only difference being that we set $\mu$ to contain the single forced edge
$uw$. ∎

######  Remark 23.

Note that if the graph is a complete bipartite graph and no woman’s preference
list is fixed, then k-forced-sm-strat and k-forbidden-sm-strat become easily
solvable: we just have to find a perfect matching satisfying the edge
restrictions if one exists, which is an assignment problem.

######  Remark 24.

Theorem 22 also implies NP-hardness of the stable allocation problem with
forced or forbidden edges, where only one side has preferences.

Our results have an interesting consequence for the stable marriage problem
with ties and the incomplete preference lists problem with forced and
forbidden edges.

######  Corollary 25.

1-forced-smti and 1-forbidden-smti are NP-complete even if each man’s
preference list is strict and each woman’s preference list is just a single
tie. The same holds if each man’s preference list is strict, each woman’s
preference list is either strict or a single tie, and all preferences are
complete.

Now we turn to the complexity of sr-strat.

######  Theorem 26.

sr-strat is NP-complete even for complete graphs.

###### Proof.

The problem is clearly in NP. To show NP-hardness, we reduce from x3c, see the
definition in Section 2.

Let $I$ be an instance of the x3c. We construct an instance $I^{\prime}$ of
sr-strat with $G=(V,E)$ as follows. For each set $C_{j}$, we add seven agents
$c_{j}^{1},c^{2}_{j},c_{j}^{3},d_{j}^{1},d_{j}^{2},d_{j}^{3},x_{j}$ called the
_gadget for $C_{j}$_. For each element $a_{i}$, we add an agent also denoted
by $a_{i}$. Finally, we add $2n$ selector agents $s_{1},\dots s_{2n}$, see
Figure 5.

The preference lists are defined as follows:

  * •

the preference lists of agents $a_{i}$ ($1\leq i\leq 3n$) and $s_{j}$ ($1\leq
j\leq 2n$) are not fixed,

  * •

if $C_{j}=(a_{j_{1}},a_{j_{2}},a_{j_{3}})$ is the $j$-th set in $I$, then:
$\displaystyle x_{j}\colon{}$
$\displaystyle{}[S]>c_{j}^{1}>c_{j}^{2}>c_{j}^{3}>d_{j}^{1}>\dots$
$\displaystyle c_{j}^{1}\colon{}$
$\displaystyle{}a_{j_{1}}>x_{j}>c_{j}^{2}>d_{j}^{1}>c_{j}^{3}>\dots$
$\displaystyle c_{j}^{2}\colon{}$
$\displaystyle{}a_{j_{2}}>x_{j}>c_{j}^{3}>c_{j}^{1}>\dots$ $\displaystyle
c_{j}^{3}\colon{}$ $\displaystyle{}a_{j_{3}}>x_{j}>c_{j}^{1}>c_{j}^{2}>\dots$
$\displaystyle d_{j}^{1}\colon{}$
$\displaystyle{}x_{j}>d_{j}^{2}>c_{j}^{1}>d_{j}^{3}>\dots$ $\displaystyle
d_{j}^{2}\colon{}$ $\displaystyle{}d_{j}^{3}>d_{j}^{1}>\dots$ $\displaystyle
d_{j}^{3}\colon{}$ $\displaystyle{}d_{j}^{1}>d_{j}^{2}>\dots$

where $[S]$ denotes $s_{1}>\dots>s_{2n}$ and ‘$>\dots$’ means that the rest of
the agents are ranked in an arbitrary order.

Figure 5: Gadget corresponding to set
$C_{j}=\\{a_{j_{1}},a_{j_{2}},a_{j_{3}}\\}$ in Theorem 26 with the first few
edges on the preference lists of the vertices.

We claim that there is an exact 3-cover in $I$ if and only if the preferences
of the remaining agents can be set in a way such that there is a stable
matching $M$ in $G$. Suppose there is an exact 3-cover
$\mathcal{C}^{\prime}\subseteq\mathcal{C}$. Then, we make construct a matching
$M$ as follows. We match the agents in $S=\\{s_{1},\dots,s_{2n}\\}$ to the
agents $x_{j}$ that correspond to the 3-sets not in $\mathcal{C}^{\prime}$. In
the gadgets for these sets, we add the edges
$c_{j}^{2}c_{j}^{3},d_{j}^{2}d_{j}^{3}$ and $c_{j}^{1}d_{j}^{1}$ to the
matching. In the gadgets of the sets in $\mathcal{C}^{\prime}$, we add the
edges $a_{j_{1}}c_{j}^{1}$, $a_{j_{2}}c_{j}^{2}$, $a_{j_{3}}c_{j}^{3}$,
$xd_{j}^{1}$, and $d_{j}^{2}d_{j}^{3}$ to the matching. Finally, we set the
preferences of the $a_{i}$s and $s_{j}$s such that each prefers its partner in
$M$ the most.

Suppose there is a blocking edge $uv$. It is clear that both $u$ and $v$ must
be from the same set gadget, since each $a_{i}$ and $s_{j}$ is with their best
partner, everyone is matched, and each agent in a set gadget prefers everyone
in their gadget to anyone from another gadget. If $u$ and $v$ are in a gadget
for a set $C_{j}\in\mathcal{C}^{\prime}$, then each $c_{j}^{i}$ and
$d_{j}^{1}$ is with their best partner, so they cannot block. Moreover,
$x_{j}$ is with the best partner from the gadget that is not a $c_{j}^{i}$.
Therefore, only $d_{j}^{2}d_{j}^{3}$ could block, but it is in $M$. If $u$ and
$v$ are in a gadget for a set $C_{j}\notin\mathcal{C}^{\prime}$, then $x_{j}$
is matched with its best partner, so it cannot block with anyone. It is
straightforward to check that the edges $c_{j}^{1}c_{j}^{2}$,
$c_{j}^{3}c_{j}^{1}$, $d_{j}^{1}d_{j}^{2}$, and $d_{j}^{3}d_{j}^{1}$ are all
dominated, so no edge can block.

Now suppose that there are preferences for the elements and selectors such
that there exists a stable matching $M$ in $G$. We can assume that the
elements and selector agents like their partner the most if there exists one.
If a gadget for a set $C_{j}$ would get no selector and no element agent from
outside, then $c_{j}^{1}$ and $x_{j}$ must be matched together. However, then
there is no stable matching among the vertices $d_{j}^{1}$, $d_{j}^{2}$ and
$d_{j}^{3}$. If the gadget for $C_{j}$ gets a selector, then we may assume
that it is matched with $x_{j}$. In this case, there is a stable matching
inside the gadget consisting of the edges $c_{j}^{2}c_{j}^{3}$,
$c_{j}^{1}d_{j}^{1}$, and $d_{j}^{2}d_{j}^{3}$. If the gadget for $C_{j}$ gets
no selector, then it must get all three of the corresponding element agents,
as otherwise neither $x_{j}$ nor $c_{j}^{1}$ is matched to $d_{j}^{1}$,
implying that there is no stable matching among the vertices $d_{j}^{1}$,
$d_{j}^{2}$ and $,d_{j}^{3}$. Indeed, if only one or two element agents would
get matched, then the preferences of $x_{j}$ imply that it must be matched to
a remaining $c_{j}^{i}$ since the remaining $c_{j}^{i}$ prefers $x_{j}$ the
most, and $x_{j}$ does not get a selector. If $x_{j}$ was matched to
$c_{j}^{2}$ or $c_{j}^{3}$, then $x_{j}c_{j}^{1}$ would block, so it is
matched to $c_{j}^{1}$.

In summary, for each set gadget, we must match either at least one selector
agent or all three element agents to it in any stable matching. Therefore, if
there is a stable matching $M$, then all set gadgets in $M$ must get either a
selector or three element agents. But there are $2n$ selectors only, so there
must be at least $n$ set gadgets that can only get element agents. By the
above observation, each must get exactly three of those, so these $n$ sets
must form an exact cover. ∎

The following corollary provides a different interpretation of Theorem 26.

######  Corollary 27.

srt is NP complete even if the graph is complete and each preference list is
either strict or a single tie.

As a positive result, we show that the problem becomes tractable when the
preferences are fixed for agents forming an independent set in the graph.

######  Theorem 28.

If the preferences are only fixed on an independent set, then sr-strat is
polynomial-time solvable.

###### Proof.

Let the agents with fixed preference lists be $v_{1},\dots,v_{k}$. For
$i\in[k]$, we do the following. Let $v_{i}$ choose its best available partner
$u_{i}$ if there is any, add $u_{i}v_{i}$ to $M$, and set $u_{i}$’s preference
such that $v_{i}$ is the best. Then find an inclusionwise maximal matching
among the rest of the vertices, add it to $M$, and set the preference of each
remaining vertex in a way that it prefers its partner the most. It follows
from the construction that the matching thus obtained is stable. ∎

###  5.2 Fixed entries in the preference lists

We move on to problems where the preference lists of the agents have some
fixed places that cannot be modified. The setting we concentrate on is the
following. We are given a graph $G=(V,E)$ with vertex capacities $q(v)$ for
$v\in V$ and an inclusionwise maximal feasible $q$-matching $M\subseteq E$.
For a saturated vertex $v$ and edge $e\in M(v)$, we have a fixed number
$p_{v}(e)$ denoting that $e$ is the $p_{v}(e)$-th worst edge in $v$’s ranking
on the incident edges. Furthermore, a similar $p_{v}(e)$ value might be given
for other vertex-edge pairs as well. Note that the $p_{v}(e)$ values for $e\in
M(v)$ where $v$ is non-saturated are not interesting in the sense that no edge
can be dominated at such a vertex. The task is to determine whether there
exists an extension of these partial preference lists such that the given
$q$-matching $M$ is stable. Such an extension is called a _stable preference
extension_. In a sense, this problem is the inverse of the stable $q$-matching
problem, where the preferences are set in advance and the task is to find a
stable $q$-matching $M$.

inc-max-spe
Input: A graph $G=(V,E)$, vertex capacities $q\in\mathbb{Z}_{+}^{V}$, an
inclusionwise maximal feasible $q$-matching $M\subseteq E$, preference values
$p_{v}(e)$ for each saturated vertex $v\in V$ and $e\in M(v)$, and preference
values for some other vertex-edge pairs. Question: Does there exist a
preference extension for which $M$ is stable?

We show that the problem of finding a stable preference extension can be
reduced to computing a maximum stable matching in a bipartite graph.

######  Theorem 29.

For any graph $G=(V,E)$, $q$-matching $M$ and partial preference $p$ which
fixes $p_{v}(e)$ for each saturated vertex $v$ and each edge $e\in M$
containing $v$, inc-max-spe an be solved in polynomial time.

###### Proof.

We reduce the problem to deciding if there exists a matching that covers a
given side of a bipartite graph $H=(U,W;F)$ entirely. We may assume that there
is no edge $e\in E\setminus M$ whose rank is fixed on both of its vertices in
such a way that $e$ necessarily blocks $M$, as otherwise the answer is clearly
‘NO’. Also, we may assume that no edge $e\in E\setminus M$ has a fixed rank at
a vertex where all edges in $M$ have better rank, because then $e$ is
dominated and can be removed.

We construct a bipartite graph $H=(U,W;F)$ as follows. For each saturated
vertex $v\in V$, we add vertices $v_{1},\dots,v_{p_{v}(f)-1}$ to $U$ where $f$
is the worst edge for $v$ in $M$. If $p_{v}(f)=1$, then we do not include any
copies of $v$. Also, if there is an index $1\leq j\leq p_{v}(f)-1$ such that
$j$ is already assigned to an edge, then we delete that copy of $v$ from the
graph. For each edge $e\notin M$ we add a vertex $v_{e}$ to $W$. Finally, we
add an edge between a copy $v_{j}$ of a vertex $v\in V$ and a vertex $v_{e}$
corresponding to edge $e\in E(v)$ if and only if $p_{v}(e)$ is not yet fixed.

We claim that the preferences can be extended in such a way that $M$ is a
stable $q$-matching if and only if $H$ admits a matching covering the vertices
in $W$. First suppose there is a matching $N$ in $H$ covering all vertices in
$W$. We allocate the unassigned preferences of the saturated vertices that are
worse than its worst edge in any order to the edges that are matched to its
copies in $N$. The remaining preferences are chosen arbitrarily from the free
positions. Then $M$ will become a stable $q$-matching of $G$ with respect to
those preferences, since any edge contains a vertex that is saturated with
strictly better edges.

For the other direction, suppose that it is possible to extend the preferences
in $G$ such that $M$ becomes stable. If we take the matching $M$ in $H$ that
matches $v_{j}$ to the vertex corresponding to its $j$’th worst edge, then $M$
covers all vertices in $W$ as an uncovered vertex would correspond to a
blocking edge.

As a matching covering the vertices in $W$ can be found in polynomial time,
the theorem follows. ∎

As a slightly more general problem, suppose that lower and upper bounds
$\ell_{v}(e)$ and $u_{v}(e)$ are given for each vertex $v\in V$ and edge
incident to $v$. The goal is to extend the preferences in such a way that $M$
is stable and $\ell_{v}(e)\leq p_{v}(e)\leq u_{v}(e)$ holds for each vertex
$v$ and each edge $e$ adjacent to $v$.

######  Theorem 30.

If only lower bounds are given, then inc-max-spe can be solved in polynomial
time.

###### Proof.

We give an algorithm consisting of four phases.

Phase 1: We construct a bipartite graph $H=(U,W;F)$ similarly as in the proof
of the unbounded case (Theorem 29). For each saturated vertex $u\in V$, we add
$p_{u}(f)-k_{u}$ copies of $u$ to $U$, where $f$ is the worst edge for $u$ in
$M$ and $k_{u}$ is the number of fixed values in the first $p_{u}(f)$ places.
Also, for each edge $e\in E\setminus M$ that is not dominated already, we add
a vertex $v_{e}$ to $W$. We add an edge between a copy $u_{j}$ of a vertex
$u\in V$ and a vertex $v_{e}$ corresponding to an edge $e\in E(u)$ if and only
if $p_{u}(e)$ is not yet fixed and $j\geq\ell_{u}(e)$.

We check whether there exists a matching that covers all vertices of $W$; such
a matching corresponds to the domination of the edges in $E\setminus M$ not
yet dominated. If no such matching exists, then the algorithm stops with the
answer ‘NO’, the preferences cannot be extended in such a way that $M$ is a
stable $q$-matching and the lower bounds are met. Otherwise, let $N_{1}$ be a
matching covering $W$.

Phase 2: We extend the bipartite graph $H$ by adding another vertex to $W$ for
each edge that was not dominated originally, and two vertices for every edge
that was not considered in Phase 1. That is, for each edge $e=xy\in E$, there
are two corresponding vertices $v^{x}_{e}$ and $v^{y}_{e}$ in $W$. We modify
the edges of $H$ in such a way that $v^{x}_{e}$ is only connected to the
copies $x_{i}$ of $x$ and $v^{y}_{e}$ is only connected to the copies $y_{j}$
of $y$ where $i\geq\ell_{x}(e)$ an $j\geq\ell_{y}(e)$, respectively. Finally,
we construct a matching $N_{2}$ in the extended bipartite graph by adding
$v^{u}_{e}u_{j}$ to $N_{2}$ for each $v_{e}u_{j}\in N_{1}$.

Phase 3: Starting from the matching $N_{2}$, we check whether there exists a
matching that covers all vertices of $U$ using the Hungarian method [21]. If
no such matching exists, then the preferences cannot be extended in such a way
that $M$ is a stable $q$-matching and the lower bounds are met, and the
algorithm stops with the answer ‘NO’. If there exists such a matching, then a
nice feature of the algorithm is that once a vertex becomes covered, it
remains so throughout. Hence, for each edge $e=xy$, one of the vertices
$v^{x}_{e}$ and $v^{y}_{e}$ is covered. We denote the resulting matching by
$N_{3}$.

Phase 4: We further extend $H$ by adding all the copies of each vertex $u\in
V$ to $U$ that have not been added in Phase 1. Also, we extend the set of
edges such that there is an edge $u_{j}v^{u}_{e}$ for each $u\in V$, $e\in
E(u)\setminus M(u)$ and $j\geq\ell_{u}(e)$. Consider the vertices
corresponding to edges $e$ that were isolated until the addition of the new
edges, that is, satisfied $\ell_{u}(e)\geq\min\\{p_{u}(f)\mid f\in M(u)\\}$.
We check if these vertices can all be matched to vertices not covered by
$N_{3}$ by running the Hungarian algorithm. If no such matching exists, then
there is no preference extension satisfying the lower bounds at all, and the
algorithm outputs ‘NO’.

Otherwise, let $N_{4}$ denote the matching obtained. We claim that the
matching $N_{3}\cup N_{4}$ can be extended to a matching in such a way that it
covers all vertices in $H$. To see this, observe that only lower bounds are
given and for each remaining copy $v^{u}_{e}$ of an edge, the lower bound
$\ell_{u}(e)$ is smaller than the indices of the uncovered copies of $u$.
Indeed, all $v^{u}_{e}$ vertices with $l_{u}(e)\geq\min\\{p_{u}(f)\mid f\in
M(u)\\}$ are matched by $N_{4}$, and for each $u\in V$ the copies $u_{j}$ with
$j\leq\min\\{p_{u}(f)\mid f\in M(u)\\}$ are matched by $N_{3}$. Therefore, the
graph induced by the unmatched vertices consists of a union of complete
bipartite graphs with equal sized color classes, so it admits a perfect
matching $N_{5}$.

Setting the preferences according to $N_{3}\cup N_{4}\cup N_{5}$ gives a
preference extension that satisfies all conditions. ∎

######  Remark 31.

Theorems 29 and 30 can be straightforwardly extended to hypergraphs. That is,
given a hypergraph $H=(V,\mathcal{E})$, vertex capacities
$q\in\mathbb{Z}_{+}^{V}$, a feasible $q$-matching $M\subseteq\mathcal{E}$,
preference values $p_{v}(f)$ for $v\in V$ and $f\in M(v)$, preference values
for some other vertex-hyperedge pairs, and lower bounds $\ell_{v}(f)$ for
$v\in V$, $f\in E(v)$, one can decide in polynomial time if there exists a
preference extension for which $M$ is stable.

A further extension would be to consider $q$-matchings $M$ that are not
necessarily inclusionwise maximal. Let $M$ be an arbitrary $q$-matching and
suppose that the places in the preference lists of the agents are fixed for
the edges of $M$ for each saturated vertex and maybe on some other vertex-edge
pairs, too. The goal is to set the remaining preferences in such a way that
there exists a stable $q$-matching $M^{\prime}$ containing $M$.

forced-spe
Input: A graph $G=(V,E)$, vertex capacities $q\in\mathbb{Z}_{+}^{V}$, a
feasible $q$-matching $\mu\subseteq E$, preference values $p_{v}(e)$ for each
saturated vertex $v\in V$ and $e\in\mu(v)$, and preference values for some
other vertex-edge pairs. Question: Does there exist a preference extension
together with a stable $q$-matching $M$ for which $\mu\subseteq M$?

Surprisingly, this problem becomes NP-complete even for the stable marriage
case.

######  Theorem 32.

forced-spe is NP complete even for bipartite graphs with capacity one on each
vertex.

###### Proof.

The problem is clearly in NP. To show NP-hardness, we reduce from x3c, see the
definition in Section 2.

Let $I$ be an instance of x3c. We construct an instance $I^{\prime}$ with
$H=(U,W;F)$ of forced-spe as follows. Let $P=\\{p_{1},\dots,p_{3n}\\}$ be a
set of agents corresponding to the ground set $S$, and
$Q=\\{q_{1},\dots,q_{m}\\}$ be a set of agents corresponding to the 3-sets.
These two sets of agents form one color class of the bipartite graph which
will be referred to as men. Agents in $X=\\{x_{1},\dots,x_{m}\\}$,
$Y=\\{y_{1},\dots,y_{m}\\}$ and $Z=\\{z_{1},\dots,z_{3n}\\}$ form the other
color class of the bipartite graph which will be referred to as women.
Finally, we add a special agent $u$ to the set of men and a special agent $w$
to the set of women. So $U=P\cup Q\cup\\{u\\}$, $W=X\cup Y\cup Z\cup\\{w\\}$.

The forced matching is $\mu=\\{uw,p_{i}z_{i}\mid i\in[3n]\\}$. The fixed
preferences of the agents on the edges of $\mu$ are the following:

  * •

for $u$, the rank of $M(u)$ is $m-n+1$,

  * •

for a man $p_{i}$, the rank of $M(p_{i})$ is $2$,

  * •

for a woman $z_{i}$, the rank of $M(z_{i})$ is set arbitrarily.

We further add the edges $\\{ux_{i},x_{i}q_{i},q_{i}y_{i}\mid i\in[m]\\}$ to
$F$, and for each 3-set $C_{j}=\\{s_{i_{1}},s_{i_{2}},s_{i_{3}}\\}$ of $I$ we
add the edges $y_{j}p_{i_{1}}$, $y_{j}p_{i_{2}}$ and $y_{j}p_{i_{3}}$.

We claim that there is an exact 3-cover in $I$ if and only if the preferences
can be extended in a way that there is a stable matching $M$ containing $\mu$.
Let us first suppose that $C_{i_{1}},\dots,C_{i_{n}}$ is a solution of the x3c
instance $I$. Let $M$ be the matching obtained by adding the edges
$\\{x_{i_{j}}q_{i_{j}}\mid j\in[n]\\}$ and the edges $\\{q_{k}y_{k}\mid
k\notin\\{i_{1},\dots,i_{n}\\}\\}$ to $\mu$. The preferences are set such that
the $m-n$ places worse than that of $uw$ for $u$ are given to the edges
$\\{ux_{k}\mid k\notin\\{i_{1},\dots,i_{n}\\}\\}$. For
$k\notin\\{i_{1},\dots,i_{n}\\}$, we set $q_{k}$ to prefer $y_{k}$ to $x_{k}$.
For $j\in[n]$, we set $q_{i_{j}}$ to prefer $x_{i_{j}}$ to $y_{i_{j}}$ and
$x_{i_{j}}$ to prefer $q_{i_{j}}$ to $u$. Also for each $i=1,\dots 3n$, we set
the worst position of $p_{i}$ to be the $y_{j}$ corresponding to the set
$C_{j}\in\\{C_{i_{1}},\dots C_{i_{n}}\\}$ containing the element $a_{i}$.
Since $C_{i_{1}},\dots,C_{i_{n}}$ is a partition, there is no collision when
doing this. Then, all edges not in $M$ are dominated: each edge of type
$ux_{j}$ is dominated at either $u$ or $x_{j}$, each edge $q_{j}x_{j}\notin M$
is dominated at $q_{j}$, each edge $q_{j}y_{j}\notin M$ is dominated at
$q_{j}$, and each edge $p_{i}y_{j}$ is dominated at either $y_{j}$ or $p_{i}$.

For the other direction, suppose there is a preference extension and a
matching $M$ with $\mu\subseteq M$ that satisfy the conditions. For any triple
$x_{i}$, $q_{i}$, and $y_{i}$, one of these vertices must be uncovered in $M$
since the only possible partner of both $x_{i}$ and $y_{i}$ is $q_{i}$ as the
other neighbors are already matched in $\mu$. There are $m-n$ women $x_{i}$
such that $x_{i}$ is worse for $u$ than $w$. At the same time, there must be
$n$ women $x_{i_{1}},\dots,x_{i_{n}}$ that are better, so for the edges
$ux_{i_{j}}$ to be dominated we must have $x_{i_{j}}q_{i_{j}}\in M^{\prime}$.
Then $y_{i_{j}}$ cannot be matched for $j=1,\dots n$, hence the edges that
join these vertices to $P$ must be dominated at the vertices of $P$. But there
are at least $n$ such $y_{i_{j}}$-s with altogether $3n$ edges incident to
them and each $p_{i}\in P$ can dominate at most one such edge, therefore
$C_{i_{1}},\dots,C_{i_{n}}$ is necessarily a partition. ∎

######  Remark 33.

If the size of the maximal matching $M$ containing $\mu$ is larger than the
size of $\mu$ only by a constant, then the problem can be solved in polynomial
time.

######  Remark 34.

The proof of Theorem 32 implies that the bipartite variant of forced-spe when
the preferences are set on $M$ only for one class of the agents is also NP-
complete.

######  Remark 35.

If the graph is a complete bipartite graph, or a complete graph and the
preferences are only set on the edges of $\mu$, then the problem can be solved
in polynomial time. First, check whether the edges that connect vertices
matched by $\mu$ can all be dominated as we did before. If this is possible,
then find a perfect matching $M$ containing $\mu$ and set the edges of
$M\setminus\mu$ as the best edges for every agent. Then $M$ is clearly a
stable matching.

Now suppose that a set $\tau$ of forbidden edges is given instead of forced
ones while some preferences of the agents are fixed. The question is whether
the preference lists can be extended such that there exists a stable matching
$M$ disjoint from $\tau$.

forbidden-spe
Input: A graph $G=(V,E)$, vertex capacities $q\in\mathbb{Z}_{+}^{V}$, a set
$\tau\subseteq E$, and preference values for some other vertex-edge pairs.
Question: Does there exist a preference extension together with a stable
$q$-matching $M$ for which $\tau\cap M=\emptyset$?

Interestingly, forbidden-spe turns out to be NP-hard even if there are no
predefined preferences, each capacity is one and the graph is bipartite. In
that case the problem is equivalent to the following: Given a bipartite graph
$G=(A,B;E)$ where $E$ is partitioned into red edges $E_{r}$ and blue edges
$E_{b}$, decide if there is a matching $M$ in the subgraph $G_{r}=(A,B;E_{r})$
such that the vertices of $M$ cover every blue edge. We call this problem red-
blue-edge-cover.

red-blue-edge-cover
Input: A bipartite graph $G=(A,B;E)$, with $E=E_{b}\cup E_{r}$, $E_{b}\cap
E_{r}=\emptyset$. Question: Is there a matching $M\subseteq E_{r}$, such that
for each $e=uv\in E_{b}:$ $M(u)\neq\emptyset$ or $M(v)\neq\emptyset$?

######  Theorem 36.

red-blue-edge-cover is NP-complete.

###### Proof.

The problem is clearly in NP. To show NP-hardness, we reduce from 3sat.

Let $\Phi$ be a 3sat instance with clauses $C_{1},\dots,C_{m}$ and variables
$x_{1},\dots,x_{n}$. We construct a bipartite graph $G=(A,B;E)$ as follows.
For each clause $C_{j}$, we add two vertices $c_{j}^{\prime}$ and
$c_{j}^{\prime\prime}$ to $A$. For each literal $x_{i}$ or
$\overline{x}_{i}\in C_{j}$, we add a vertex $y_{j}^{i}$ or $z_{j}^{i}$,
respectively, to $B$. We connect these five vertices with red edges, that is,
a red $K_{2,3}$ subgraph is added for every clause. For each variable $x_{i}$,
we add two vertices $y_{i}$ and $z_{i}$ to $A$, a selector vertex $s_{i}$ to
$B$, and two red edges $y_{i}s_{i}$ and $z_{i}s_{i}$. Finally, for $i\in[n]$
we add blue edges between $y_{i}$ and $y_{j}^{i}$ for the values of $j$ for
which $x_{i}\in C_{j}$, and between $z_{i}$ and $z_{j}^{i}$ for the values of
$j$ for which $\overline{x}_{i}\in C_{j}$.

We claim that $\Phi$ has a satisfying assignment if and only if $G$ admits a
matching $M$ consisting of red edges whose end vertices cover every blue edge.
Suppose there exists a satisfying assignment for $\Phi$. Then for each $i$, we
add the red edge $y_{i}s_{i}$ to $M$ if $x_{i}$ was true, otherwise the edge
$z_{i}s_{i}$. For each clause $C_{j}$, we pick a literal that is true and add
two red edges from $a_{i}^{\prime}$ and $a_{i}^{\prime\prime}$ to the vertices
corresponding to the other two literals. This way each blue edge will be
covered. Indeed, if a blue edge is not covered at its vertex in $A$, then it
corresponds to a false literal. However, in such a case the edge is covered in
one of the $K_{2,3}$s.

For the other direction, let $M$ be a red matching that covers every blue
edge. In every red $K_{2,3}$, there is a blue edge from one of its vertices in
$B$ that is not covered by edges of the $K_{2,3}$, hence it has to be covered
by an edge $y_{i}s_{i}$ or $z_{i}s_{i}$, and only one of these two edges can
be in $M$. If we set the values of the variables such that $x_{i}$ is true if
and only if $y_{i}s_{i}\in M$, then we get a satisfying assignment. ∎

#### Acknowledgement.

The work was supported by the Lendület Programme of the Hungarian Academy of
Sciences – grant number LP2021-1/2021 and by the Hungarian National Research,
Development and Innovation Office – NKFIH, grant numbers FK128673 and
TKP2020-NKA-06.

## References

  * [1] D. J. Abraham, P. Biró, and D. F. Manlove.  “almost stable” matchings in the roommates problem.  In International Workshop on Approximation and Online Algorithms, pages 1–14. Springer, 2005.
  * [2] D. J. Abraham, K. Cechlárová, D. F. Manlove, and K. Mehlhorn.  Pareto optimality in house allocation problems.  In International Symposium on Algorithms and Computation, pages 3–15. Springer, 2004.
  * [3] H. Aziz, H. G. Seedig, and J. K. von Wedel.  On the susceptibility of the deferred acceptance algorithm.  arXiv preprint arXiv:1502.06318, 2015.
  * [4] P. Biró, D. F. Manlove, and S. Mittal.  Size versus stability in the marriage problem.  Theoretical Computer Science, 411(16-18):1828–1841, 2010.
  * [5] N. Boehmer, R. Bredereck, K. Heeger, and R. Niedermeier.  Bribery and control in stable marriage.  Journal of Artificial Intelligence Research, 71:993–1048, 2021\.
  * [6] K. Cechlárová and T. Fleiner.  Stable roommates with free edges.  Technical Report TR-2009-01, Egerváry Research Group, Budapest, 2009\.  egres.elte.hu.
  * [7] J. Chen, P. Skowron, and M. Sorge.  Matchings under preferences: Strength of stability and tradeoffs.  ACM Transactions on Economics and Computation, 9(4):1–55, 2021\.
  * [8] Á. Cseh and K. Heeger.  The stable marriage problem with ties and restricted edges.  Discrete Optimization, 36:100571, 2020.
  * [9] A. Cseh and D. F. Manlove.  Stable marriage and roommates problems with restricted edges: complexity and approximability.  Discrete Optimization, 20:62–89, 2016.
  * [10] M. Demange and J. Monnot.  An introduction to inverse combinatorial problems.  In V. T. Paschos, editor, Paradigms of Combinatorial Optimization: Problems and New Approaches, pages 547–586. Wiley, London-Hoboken, 2010.
  * [11] V. M. Dias, G. D. Da Fonseca, C. M. De Figueiredo, and J. L. Szwarcfiter.  The stable marriage problem with restricted pairs.  Theoretical Computer Science, 306(1-3):391–405, 2003.
  * [12] E. Eiben, G. Gutin, P. R. Neary, C. Rambaud, M. Wahlström, and A. Yeo.  Preference swaps for the stable matching problem.  arXiv preprint arXiv:2112.15361, 2021.
  * [13] D. Gale and L. S. Shapley.  College admissions and the stability of marriage.  The American Mathematical Monthly, 69(1):9–15, 1962.
  * [14] M. R. Garey and D. S. Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [15] S. Gupta and S. Roy.  Stable matching games: manipulation via subgraph isomorphism.  Algorithmica, 80(9):2551–2573, 2018.
  * [16] D. S. Hochbaum.  Complexity and approximations for submodular minimization problems on two variables per inequality constraints.  Discrete Applied Mathematics, 250:252–261, 2018.
  * [17] H. Hosseini, F. Umar, and R. Vaish.  Two for one and one for all: Two-sided manipulation in matching markets.  arXiv preprint arXiv:2201.08774, 2022.
  * [18] R. W. Irving.  An efficient algorithm for the “stable roommates” problem.  Journal of Algorithms, 6(4):577–595, 1985.
  * [19] S. Khot and O. Regev.  Vertex cover might be hard to approximate to within 2- $\varepsilon$.  Journal of Computer and System Sciences, 74(3):335–349, 2008.
  * [20] H. Kobayashi and T. Matsui.  Cheating strategies for the Gale-Shapley algorithm with complete preference lists.  Algorithmica, 58(1):151–169, 2010.
  * [21] H. W. Kuhn.  The hungarian method for the assignment problem.  Naval research logistics quarterly, 2(1-2):83–97, 1955.
  * [22] D. Manlove.  Algorithmics of matching under preferences, volume 2.  World Scientific, 2013.
  * [23] D. F. 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.
  * [24] M. Richter.  Inverse problems: Basics, theory and applications in geophysics.  Springer Nature, 2021.
  * [25] A. E. Roth.  The economics of matching: Stability and incentives.  Mathematics of operations research, 7(4):617–628, 1982.
  * [26] W. Shen, P. Tang, and Y. Deng.  Coalition manipulation of Gale-Shapley algorithm.  Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), 2018.
  * [27] J. J. Tan.  A maximum stable matching for the roommates problem.  BIT Numerical Mathematics, 30(4):631–640, 1990.
  * [28] J. J. Tan.  A necessary and sufficient condition for the existence of a complete stable matching.  Journal of Algorithms, 12(1):154–178, 1991.