# Preference Swaps for the Stable Matching Problem

Eduard Eiben  Department of Computer Science, Royal Holloway, University of
London, TW20 0EX, Egham, Surrey, UK  Gregory Gutin  Department of Computer
Science, Royal Holloway, University of London, TW20 0EX, Egham, Surrey, UK
Philip R. Neary  Department of Economics, Royal Holloway, University of
London, TW20 0EX, Egham, Surrey, UK  Clément Rambaud  DIENS, École normale
supérieure, PSL University, Paris, France  Magnus Wahlström  Department of
Computer Science, Royal Holloway, University of London, TW20 0EX, Egham,
Surrey, UK  Anders Yeo  IMADA, University of Southern Denmark, Odense, Denmark
Department of Mathematics, University of Johannesburg, Auckland Park, 2006
South Africa

###### Abstract

An instance $I$ of the Stable Matching Problem (SMP) is given by a bipartite
graph with a preference list of neighbors for every vertex. A swap in $I$ is
the exchange of two consecutive vertices in a preference list. A swap can be
viewed as a smallest perturbation of $I$. Boehmer et al. (2021) designed a
polynomial-time algorithm to find the minimum number of swaps required to turn
a given maximal matching into a stable matching. We generalize this result to
the many-to-many version of SMP. We do so first by introducing a new
representation of SMP as an extended bipartite graph and subsequently by
reducing the problem to submodular minimization. It is a natural problem to
establish the computational complexity of deciding whether at most $k$ swaps
are enough to turn $I$ into an instance where one of the maximum matchings is
stable. Using a hardness result of Gupta et al. (2020), we prove that this
problem is NP-hard and, moreover, this problem parameterised by $k$ is
W[1]-hard. We also obtain a lower bound on the running time for solving the
problem using the Exponential Time Hypothesis.

##  1 Introduction

We consider the classic stable matching problem of [8] described as follows.
There is a two-sided market with two types of agents: workers on one side and
firms on the other. Workers seek employment while firms have vacancies and so
are looking to hire (let us assume for now that every firm wishes to employ
just one worker and vice versa). Workers have preference lists over firms and
firms have preference lists over workers. This is modeled as a bipartite graph
$G$, where the partite sets are workers $W$ and firms $F$ and there is a
preference list for each $a\in W\cup F$ consisting of all neighbors of $a$ in
$G$. A matching $M$ of workers to firms in $G$ is said to be stable if there
is no edge $wf$ in $G$ ($w\in W$, $f\in F$) such that $w$ is either not
matched in $M$ or matched to a firm less preferable to $w$ than $f$, and $f$
is either not matched in $M$ or matched to a worker less preferable to $f$
than $w$. In the Stable Matching Problem (SMP), given a bipartite graph $G$
and a set $L_{G}$ of preference lists, the goal is to find a stable matching.

The deferred acceptance algorithm of Gale and Shapley [8] confirms that a
stable matching always exists. By definition, every stable matching is
maximal, but in general not every maximal matching is stable. In this paper we
focus on the relationship between maximal matchings and stable matchings. In
particular, when a maximal matching is not a stable matching, how far from
being stable is it?

By virtue of the Rural Hospitals Theorem [17, 18, 19], the set of agents
matched is the same in every stable matching. Therefore, to get a larger
stable matching, the preference lists need to be amended/altered. Consider a
worker who ranks firm $x$ just ahead of firm $y$ in their preference list. A
_swap_ exchanges the relative placing of firms $x$ and $y,$ leaving the
remainder of the preference list unchanged. (A similar statement holds for the
preference lists of firms.) With swaps so defined, we can now address
questions like that above concerning the distance between stable matchings and
maximal matchings, where the unit of distance we employ is that of a swap.

The economic motivation for this paper concerns how a policy maker might amend
an existing two-sided matching market (a so-called market without prices) so
that the resulting stable outcomes are more socially desirable. For example,
when a maximum matching is a stable matching the number of unemployed
individuals and the number of unfilled vacancies is minimised. Historically,
markets with prices were allowed to evolve naturally, with policy makers only
interfering when they saw ways to ‘improve’ outcomes.111Examples of tools
available to policy makers in such markets include taxes, tariffs, quotas,
outright bans, price ceilings, etc. But studies that address how market
interference might improve existing matching markets are surprisingly
scarce.222This should not be confused with the enormous literature on _market
design_ , that seeks to engineer from scratch matching markets with
‘desirable’ properties.

Above for simplicity we assumed that every firm wishes to employ just one
worker and every worker wants only one job. This is an example of so-called
one-to-one SMP. Such a model is restrictive as, for example, it does not allow
us to consider natural situations like that where firms have more than one
vacancy and/or a worker may seek more than one job [18, 19, 12].

Contributions. We study two related problems on using swaps to obtain large
(maximum) stable matchings:

Problem 1:

Decide whether at most $k$ swaps can turn a given maximal matching into a
stable matching.

Problem 2:

Decide whether at most $k$ swaps are enough to have an arbitrary stable
maximum matching.

While the two problems look similar at the first glance, their computational
complexities differ. For Problem 1, we consider many-to-many SMP and obtain a
polynomial-time algorithm, see Theorem 3.2. Our design of the algorithm uses
two tools: (a) a new representation of SMP input as an extended bipartite
graph ${\cal G}_{G}$ which encodes both $G$ and its preference lists and
provides us with a convenient way to study swaps, and (b) a reduction to
submodular function minimization.

Theorem 3.2 may suggest that Problem 2 is also polynomial-time solvable.
Unfortunately, this is highly unlikely as Theorem 4.4 shows that the problem
is NP-hard and moreover if $k$ is the parameter then the problem is
W[1]-hard333For an excellent introduction to parameterized complexity, see
[6]., even if $G$ has a perfect matching. We also obtain a lower bound on the
running time for solving the problem using the Exponential Time Hypothesis
(ETH) [11].

Related work. The classical formulation of SMP uses agents and their
preference lists, or equivalently bipartite graphs and preference lists of the
vertices. Maffray [13] gave another representation of SMP using directed
graphs, which does not use explicit preference lists. Maffray’s representation
is better suitable for some SMP studies than the standard one [1, 2, 10]. Our
new representation of SMP uses extended bipartite graphs and no preference
lists either.

Boehmer et al. [3] give examples of external manipulations which can lead to
changes in one-to-one SMP preference lists, among them the notion of a swap.
They study several problems related to matchings that are stable after the
application of a small number of such manipulations steps, including proving
that Problem 1 is polynomial-time solvable for one-to-one SMP. Thus, Theorem
3.2 generalizes their result.

Chen et al. [5] study the stable matching $k$-robustness problem for one-to-
one SMP, which is the problem of deciding whether $(G,L_{G})$ has a stable
matching remaining stable even after at most $k$ swaps. Surprisingly, the
problem turns out polynomial-time solvable. Chen et al. [5] observed that
Problem 2 is in XP if $k$ is the parameter and proved that Problem 2 is
W[1]-hard if $G$ has a perfect matching and the parameter is $n_{u}$ the
number of vertices unmatched in any stable matching of $G$. By Propositions
4.1 and 4.2, our W[1]-hardness result is strictly stronger than that in [5].

Mai and Vazirani [14, 15] studied one-to-one SMP when the number of vertices
in both partite sets of $G$ is the same, denoted by $n.$ A shift is an
exchange of any two (not necessarily consecutive) vertices in a preference
list. Mai and Vazirani [14] considered a given distribution among all shifts
and studied the effect of a random shift on matching stability. They obtained
a polynomial-time algorithm for finding a matching which is stable in the
input instance of SMP and has the maximum probability of remaining stable
after a random shift took place. This algorithm applies to the problem we
study in this paper only for $k=1$ as a sequence of two swaps may not be a
shift. Mai and Vazirani [15] considered a set $S$ of permutations in a single
preference list and designed an $O(|S|{\rm poly}(n))$-time algorithm for
finding a matching which is stable in the given instance of SMP and remains so
after any permutation in $S$ took place.

Bredereck et al. [4] designed a polynomial-time algorithm for the following
problem: given a bipartite graph $G$, a pair $L$ and $L^{\prime}$ of
preference lists for $G$, a stable matching $M$ of $(G,L)$ and a natural
number $k$, decide whether $(G,L^{\prime})$ has a stable matching $M^{\prime}$
such that the symmetric difference of $M$ and $M^{\prime}$ is at most $k.$

A way to increase the size of stable matchings is to relax the zero blocking
pair condition. Gupta et al. [9] studied the almost stable matching problem,
which is a problem of finding a matching whose size exceeds that of a stable
matching by at least $t$ and has at most $k$ blocking edges. Let $d$ be the
maximum length of a preference list. Gupta et al. [9] proved the following
surprising result: the problem is intractable even when parameterized by the
combined parameter $k+t+d.$ This result demonstrates significant computational
difficulty in solving natural approximating stable matching problems.

##  2 Terminology, Notation and Preliminaries

In this section, we will first give a more formal definition of the Stable
Matching Problem (SMP) using bipartite graphs and preference lists for
vertices and then introduce an equivalent new representation of SMP which also
uses bipartite graphs, but without explicit preference lists. The new
representation gives us a more suitable approach than the standard one for
some SMP problems studied in this paper.

The input of SMP is $(G,L_{G})$, where $G=(A,B;E)$ is a bipartite graph with
partite sets $A$ and $B$ and edge set $E$ and $L_{G}$ is the set of lists
$\ell(v)=(u_{1},\dots,u_{d(v)})$ which order all the neighbors of every $v\in
A\cup B.$ If $i<j$ we say that $v$ prefers $u_{i}$ to $u_{j}.$ Let $M$ be a
matching in $G$. Then an edge $ab\in E\setminus M$ with $a\in A,b\in B$ is a
blocking edge of $M$ if the following two conditions hold simultaneously: (i)
either $a$ is not an endpoint of any edge in $M$ or there is a $b^{\prime}\in
B$ such that $ab^{\prime}\in M$ and $a$ prefers $b$ to $b^{\prime}$ and,
similarly, (ii) either $b$ is not an endpoint of any edge in $M$ or there is
an $a^{\prime}\in A$ such that $a^{\prime}b\in M$ and $b$ prefers $a$ to
$a^{\prime}$. Figure 1(a) shows preference lists for the vertices of the
depicted graph; $a_{1}$ prefers $b_{1}$ to $b_{3}$ and $b_{3}$ to $b_{2}$;
$(1,3,2)$ only includes indexes of the corresponding vertices in $B$. Figure
1(a) also gives examples of blocking edges.

A matching $M$ is stable if it has no blocking edges. It follows from the
definition of a blocking edge that a stable matching $M$ is maximal i.e. no
edge from $G$ can be added to $M$ such that it remains a matching. A matching
$M$ is perfect if $|M|=|A|=|B|.$ The aim of SMP is to find a stable matching
in $G$. The deferred acceptance algorithm of [8] outputs a stable matching in
$G$. In particular, [8] studied the above wherein (i) the bipartite graph $G$
is complete, and (ii) the partite sets are of equal size ($|A|=|B|$). For an
instance of SMP, a swap $\sigma$ is an adjacent transposition in $\ell(v)$ for
some $v\in A\cup B$ i.e. this operation results in exchanging two consecutive
elements $u_{i-1},u_{i}$ of $\ell(v)$ and is denoted by
$u_{i-1}\leftrightarrow u_{i}$. We denote by $\sigma(L_{G})$ the new set of
preference lists after the swap $\sigma$.

Let us now introduce the new SMP representation, which fuses $G$ and $L_{G}$
into a single bipartite graph, called the extended bipartite graph, with
specifically structured partite sets as follows. Let $G=(A,B;E),$ where
$A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{n^{\prime}}\\}.$ Let
$d_{i}$ ($d^{\prime}_{i}$, respectively) be the degree of $a_{i}$ ($b_{i}$,
respectively). Now we construct a new bipartite graph ${\cal G}_{G}$ by
replacing every $a_{i}$ $(i\in[n])$ with a $d_{i}$-tuple
$A_{i}=(a^{i}_{1},\dots,a^{i}_{d_{i}})$ of vertices and every $b_{i}$
$(i\in[n^{\prime}])$ with a $d^{\prime}_{i}$-tuple
$B_{i}=(b^{i}_{1},\dots,b^{i}_{d^{\prime}_{i}})$ of vertices. If $G$ is clear
from the context, we may omit the subscript and write ${\cal G}$ instead of
${\cal G}_{G}$ and $L$ instead of $L_{G}$.

The partite sets of $\cal G$ are ${\cal A}=A_{1}\cup\dots\cup A_{n}$ and
${\cal B}=B_{1}\cup\dots\cup B_{n^{\prime}}$. The edge set $E({\cal G})$ of
${\cal G}$ is defined as follows: $a^{i}_{p}b^{j}_{q}$ is an edge in ${\cal
G}$ if $a_{i}b_{j}\in E$, $b_{j}$ is the $p$’th element of $\ell(a_{i})$ and
$a_{i}$ is the $q$’th element of $\ell(b_{j}).$ Note that the maximum degree
of $\cal G$ is 1. Thus, ${\cal G}=({\cal A},{\cal B};E({\cal G})).$ Figure
1(b) shows $\cal G$ for $(G,L)$ in Figure 1(a).

A _matching_ in $\cal G$ is a subset $M$ of $E({\cal G})$ such that for every
$i\in[n]$, there is at most one edge between $A_{i}$ and $\cal B$ that belongs
to $M$, and for every $i^{\prime}\in[n^{\prime}]$, there is at most one edge
between $\cal A$ and $B_{i^{\prime}}$ that belongs to $M$. A matching $M$ is
said to be _maximal_ if no edge of $\cal G$ can be added to it. A matching $M$
is _stable_ if there is no edge of the form
$a^{i}_{j}b^{i^{\prime}}_{j^{\prime}}\in E({\cal G})\setminus M$ such that:

$\displaystyle j$ $\displaystyle<$ $\displaystyle\min\\{n+1\\}\cup\\{r\mid
a^{i}_{r}\mbox{ is matched in }M\\}{\mbox{ and }}$ $\displaystyle j^{\prime}$
$\displaystyle<$ $\displaystyle\min\\{n^{\prime}+1\\}\cup\\{r^{\prime}\mid
b^{i^{\prime}}_{r^{\prime}}\mbox{ is matched in }M\\}$

Otherwise, such an edge is called a _blocking_ edge. Figure 1(b) illustrates
the notion of a blocking edge in $\cal G$. It is not hard to see that the
blocking edges in $G$ (the stable matchings of $G$, respectively) are in a
one-to-one correspondence to the blocking edges in $\cal G$ (the stable
matchings of $\cal G$, respectively).

A _swap_ $\sigma$ is an adjacent transposition of two vertices in some $A_{i}$
$(i\in[n])$ or $B_{i^{\prime}}$ $({i^{\prime}}\in[n^{\prime}])$. Thus, swaps
can be of the form $a^{i}_{j}\leftrightarrow a^{i}_{j-1}$ in some $A_{i}$, or
$b^{i^{\prime}}_{j^{\prime}}\leftrightarrow b^{i^{\prime}}_{j^{\prime}-1}$ in
some $B_{i^{\prime}}$. We denote by
$\sigma(\mathcal{A},\mathcal{B})=(\mathcal{A}^{\prime},\mathcal{B}^{\prime})$
the resulting values of $\mathcal{A}$ and $\mathcal{B}$.

$a_{1}$$a_{2}$$a_{3}$$b_{1}$$b_{2}$$b_{3}$$(1,3,2)$$(2,1,3)$$(1,2)$$(1,3,2)$$(2,1,3)$$(2,1)$
(a) An example of an SMP instance with the preference lists. A given matching
$M$ is represented by the bold edges and the blocking edges are dashed.

$a_{1}^{1}$$a_{2}^{1}$$a_{3}^{1}$$a_{1}^{2}$$a_{2}^{2}$$a_{3}^{2}$$a_{1}^{3}$$a_{2}^{3}$$A_{1}$$A_{2}$$A_{3}$$b_{1}^{1}$$b_{2}^{1}$$b_{3}^{1}$$b_{1}^{2}$$b_{2}^{2}$$b_{3}^{2}$$b_{1}^{3}$$b_{2}^{3}$$B_{1}$$B_{2}$$B_{3}$
(b) The corresponding new representation, ${\cal G}_{G}$. The higher a vertex
is placed, the higher its preference.

Figure 1: Illustration of the correspondence between the two representations
of an SMP instance.

We also consider the more general capacitated extension of SMP (it is
equivalent to many-to-many SMP), where every vertex of $G$ has a positive
weight given by a capacity function $c:A\cup B\to\mathbb{Z}_{+}.$ Then we are
looking for a stable generalization of a matching, which is a subgraph $S$ of
$G$ where the degree $d_{S}(v)\leq c(v)$ for every $v\in A\cup B.$ The notion
of a blocking edge can be extended from the uncapacited case (where $c(v)=1$
for every $v$) to the capacitated case by saying that $ab\in E\setminus E(S)$
is a blocking edge of $S$ if the following two conditions hold simultaneously:
(i) either $d_{S}(a)<c(a)$ or there is a $b^{\prime}\in B$ such that
$ab^{\prime}\in E(S)$ and $a$ prefers $b$ to $b^{\prime}$ and, similarly, (ii)
either $d_{S}(b)<c(b)$ or there is an $a^{\prime}\in A$ such that
$a^{\prime}b\in E(S)$ and $b$ prefers $a$ to $a^{\prime}.$ A subgraph $S$ is
stable if it has no blocking edges.

##  3 Making a given matching stable

In this section, we show that Problem 1 can be solved in polynomial time, even
in the capacitated case; i.e., given a capacitated SMP instance $I=(G,L_{G})$
and a subgraph $S$ of $G$, there is a polynomial-time algorithm for computing
the minimum number of swaps required to make $S$ stable (if possible). Our
algorithm builds on the extended bipartite graph $\cal G$ defined in the
previous section. In the uncapacitated case, it is possible to show that the
problem reduces to a vertex cover instance on a bipartite graph derived from
$\cal G$; however, an efficient solution for Problem 1 in the uncapacitated
case was already given by Bredereck et al. [4], so we omit the details and
focus on the capacitated case.

Note that the standard method of reducing capacitated matching problems to
uncapacitated problems, by taking $c(v)$ copies of every vertex $v$ (with
capacity $c(v)$), does not work here since the cost of making swaps in
$\ell(v)$ is lost in the translation. Instead we solve the problem using more
powerful tools. We show that the number of swaps required in $\ell(v)$, as a
function of a set of blocking edges to fix at $v$, is _submodular_ , allowing
us to reduce Problem 1 to a case of submodular function minimization. For a
set $X$, a function $f\colon\mathcal{P}(X)\rightarrow\mathbb{N}$ is submodular
if for every $Y,Z\subseteq X$ we have that $f(Y)+f(Z)\geq f(Y\cup Z)+f(Y\cap
Z)$. In our proof it will be convenient to consider also the following
equivalent definition of a submodular function. It is well known that
$f\colon\mathcal{P}(X)\rightarrow\mathbb{N}$ is submodular if and only if for
$Y\subseteq X$ and for every $x_{1},x_{2}\in X\setminus Y$ such that
$x_{1}\neq x_{2}$ it holds that
$f(Y\cup\\{x_{1},x_{2}\\})-f(Y\cup\\{x_{1}\\})\leq f(Y\cup\\{x_{2}\\})-f(Y)$.
Before we proceed to proof our main result of this section, we state the
following result in [20].

######  Theorem 3.1 ([20]).

Let $X$ be a finite set and $f\colon\mathcal{P}(X)\rightarrow\mathbb{N}$ a
submodular function such that for every $Y\subseteq X$ the value $f(Y)$ can be
computed in polynomial time. Then there is a strongly polynomial-time
algorithm minimizing the function $f$.

######  Theorem 3.2.

Let $(G=(A,B,E,c),L_{G})$ be an SMP instance with capacities and $S$ a
subgraph of $G$ such that $d_{S}(v)\leq c(v)$ for every $v\in A\cup B$. There
exists a polynomial-time algorithm that finds a minimum length sequence
$\sigma_{1},\dots,\sigma_{k}$ of swaps such that $S$ is a stable subgraph in
$(G,(\sigma_{k}\circ\dots\circ\sigma_{1}(L_{G})))$.

###### Proof.

Recall that $n=|A|$, $n^{\prime}=|B|$, $A=\\{a_{1},\ldots,a_{n}\\}$, and
$B=\\{b_{1},\ldots,b_{n^{\prime}}\\}$. We first construct the extended graph
$\mathcal{G}_{G}$ with $\mathcal{A}=A_{1}\cup\ldots\cup A_{n}$ and
$\mathcal{B}=B_{1}\cup\ldots\cup B_{n^{\prime}}$. Recall that
$A_{i}=\\{a^{i}_{1},\ldots,a^{i}_{d_{G}(a_{i})}\\}$ corresponds to the vertex
$a_{i}\in A$ and $B_{j}=\\{b^{j}_{1},\ldots,b^{j}_{d_{G}(b_{j})}\\}$
corresponds to the vertex $b_{j}\in B$. Note that $S$ induces a matching in
$\mathcal{G}_{G}$ and we denote this matching $M$.

Our goal is to determine a minimal sequence of swaps making $M$ stable. Let
$E_{b}$ be the set of blocking edges of $M$. Furthermore, let
$E^{A}_{b}\subseteq E_{b}$ be the subset of blocking edges of $M$ such that
for every edge $a^{i}_{p}b^{j}_{q}\in E^{A}_{b}$ it holds that
$d_{S}(a_{i})=c(a_{i})$. Note that if $e=a^{i}_{p}b^{j}_{q}\in E_{b}\setminus
E^{A}_{b}$, then $e$ cannot become non-blocking by permuting $A_{i}$.
Similarly let $E^{B}_{b}\subseteq E_{b}$ be the subset of blocking edges for
$M$ such that for every edge $a^{i}_{p}b^{j}_{q}\in E^{B}_{b}$ it holds that
$d_{S}(b_{j})=c(b_{j})$. Note that if $E^{A}_{b}\cup E^{B}_{b}\neq E_{b}$,
then there is a blocking edge in $E_{b}$ such that both endpoints of the edge
do not have full capacity and $S$ cannot be made stable.

The idea of the proof is that making $M$ stable means unblocking every
blocking edge, where unblocking a blocking edge corresponds to moving at least
one of its endpoints below the vertices matched by $M$. Define a cost function
$h:\mathcal{P}(E^{A}_{b})\to\mathbb{N}$ that maps a set $F\subseteq E_{b}$ of
blocking edge to the minimum number of swaps to fix every edge in $F$ by
moving its endpoint in $\mathcal{A}$ and every other blocking edge by moving
its endpoint in $\mathcal{B}$.

We define for every $i\in\\{1,2,\ldots,n\\}$ the function
$f_{i}\colon\mathcal{P}(E_{b})\to\mathbb{N}$ such that for every $F\subseteq
E_{b}$, the value $f_{i}(F)$ is equal to the minimum number of swaps in
$A_{i}$ moving every vertex in $A_{i}\cap\\{u\mid uv\in F\\}$ below the
matched vertices, i.e., the vertices in $A_{i}\cap\bigcup_{e\in M}e$.
Furthermore, for every $j\in\\{1,2,\ldots,n^{\prime}\\}$ we define the
function $g_{j}\colon\mathcal{P}(E_{b})\to\mathbb{N}$ such that for every
$F\subseteq E_{b}$, the value $g_{i}(F)$ is equal to the minimum number of
swaps in $B_{j}$ moving every vertex in $B_{j}\cap\\{u\mid uv\in F\\}$ below
the matched vertices, i.e., the vertices in $B_{j}\cap\bigcup_{e\in M}e$.

Now, let us consider a minimal sequence of swaps $\sigma_{1},\dots,\sigma_{k}$
making $M$ stable, and let $F$ be the subset of blocking edges that are fixed
using swaps in $\mathcal{A}$; i.e., if $a^{i}_{p}b^{j}_{q}\in F$, then
$d_{S}(a_{i})=c(a_{i})$ and $a^{i}_{p}$ is below every matched vertex in
$A_{i}$ after applying the sequence of swaps $\sigma_{1},\dots,\sigma_{k}$ and
if $a^{i}_{p}b^{j}_{q}\in E_{b}\setminus F$, then $d_{S}(b_{j})=c(b_{j})$ and
$b^{j}_{q}$ is below every matched vertex in $B_{j}$ after applying the
sequence of swaps $\sigma_{1},\dots,\sigma_{k}$. Clearly, $E_{b}\setminus
E^{B}_{b}\subseteq F\subseteq E^{A}_{b}$. It is easy to see that the number of
swaps in the sequence $\sigma_{1},\dots,\sigma_{k}$ that are in $A_{i}$ is at
least $f_{i}(F)$ and the number of swaps that are in $B_{j}$ is at least
$g_{j}(E_{b}\setminus F)$. Therefore, the total number of swaps $k$ is at
least $h(F)=\sum_{i\in[n]}f_{i}(F)+\sum_{j\in[n^{\prime}]}g_{j}(E_{b}\setminus
F)$. On the other hand, it is easy to see that for any $F^{\prime}$ such that
$E_{b}\setminus E^{B}_{b}\subseteq F^{\prime}\subseteq E^{A}_{b}$ it is always
possible to make $M$ stable with at most $h(F^{\prime})$ many swaps. Hence
$k=h(F)$ and to find a minimum length sequence of swaps, it suffices to find
$F$ such that $E_{b}\setminus E^{B}_{b}\subseteq F\subseteq E^{A}_{b}$
minimizing $h(F)$. To avoid the constraint $E_{b}\setminus E^{B}_{b}\subseteq
F$, let $J^{\prime}\subseteq[n^{\prime}]$ be the set of indices such that
$j\in J^{\prime}$ if and only if $d_{S}(b_{j})<c(b_{j})$. For every $j\in
J^{\prime}$ we define a function
$g^{\prime}_{j}\colon\mathcal{P}(E_{b})\rightarrow\mathbb{N}\cup\\{\infty\\}$
such that for every $F\subseteq E_{b}$, we have $g^{\prime}_{j}(F)=0$ if
$B_{j}\cap\\{u\mid uv\in F\\}=\emptyset$ and $g^{\prime}_{j}(F)=\infty$444Here
infinity can be replaced by some large number, e.g., $(nn^{\prime})^{2}$ would
suffice. otherwise. We define
$h^{\prime}\colon\mathcal{P}(E^{A}_{b})\rightarrow\mathbb{N}\cup\\{\infty\\}$
such that $h^{\prime}(F)=h(F)+\sum_{j\in
J^{\prime}}g^{\prime}_{j}(E_{b}\setminus F)$. Note that for every $F$ such
that $E_{b}\setminus E^{B}_{b}\subseteq F\subseteq E^{A}_{b}$, we have
$h^{\prime}(F)=h(F)$. On the other hand if
$a^{i}_{p}b^{j}_{q}\in(E_{b}\setminus E^{B}_{b})\setminus F$, then
$a^{i}_{p}b^{j}_{q}\in E_{b}\setminus F$ and $g^{\prime}_{j}(F)=\infty$
implying $h^{\prime}(F)=\infty$.

We will show that $h^{\prime}$ is submodular and for fixed $F\subseteq E_{b}$
we can compute $h^{\prime}(F)$ in polynomial time. Then we can use Theorem 3.1
to minimise $h^{\prime}$ in polynomial time.

Elementary operations on submodular functions show that it suffices to prove
that every function $f_{i}$ as well as every function $g_{j}$ and every
function $g^{\prime}_{j}$ are submodular. It is easy to see that
$g^{\prime}_{j}$ is submodular and computable in polynomial time. The proof
for a function $g_{j}$ is analogous to the proof of submodularity of function
$f_{i}$ and hence it is omitted. Let us now fix $i\in[n]$ for the rest of the
proof.

For the ease of explanation, we partition $A_{i}$ into three kinds of
vertices:

  1. (i)

the _red_ vertices – the endpoint of a blocking edge in $F$,

  2. (ii)

the _blue_ vertices – the matched vertices in $M$, and

  3. (iii)

the _black_ vertices – the rest.

First, we make some basic observations:

  * •

red vertices never need to go up,

  * •

blue vertices never need to go down,

  * •

two vertices of the same kind never need to be swapped,

  * •

if $a^{i}_{r}$ is red and $a^{i}_{b}$ blue below $a^{i}_{r}$, then $a^{i}_{r}$
and $a^{i}_{b}$ must be swapped.

For any vertex $a^{i}_{j}$, we denote by $B_{F}(j)$ the number of blue
vertices below $a^{i}_{j}$ and $R_{F}(j)$ the number of red vertices above
$a^{i}_{j}$.

The key observation is the following claim.

######  Claim 3.2.1.

$f_{i}(F)=\sum_{a^{i}_{r}\text{ is red}}B_{F}(r)+\sum_{a^{i}_{j}\text{ is
black}}\min\\{B_{F}(j),R_{F}(j)\\}.$

###### Proof.

Let $s(j)$ be the number of swaps with the vertex $a^{i}_{j}$. Observe that

$f_{i}(F)=\sum_{a^{i}_{j}\in A_{i},a^{i}_{j}\text{ is black}}s(j)+N,$

where $N$ is the number of swaps between a red and a blue vertex, but

$N=|\\{(a^{i}_{r},a^{i}_{b})\mid a^{i}_{r}\text{ is red, }a^{i}_{b}\text{ is
blue, and }a^{i}_{r}\text{ is above }a^{i}_{b}\\}|,$

which is equal to

$\sum_{a^{i}_{r}\text{ is red}}B_{F}(r)=\sum_{a^{i}_{b}\text{ is
blue}}R_{F}(b)$

and can be computed in time $\mathcal{O}(n^{2})$. Note that given $F$ the
value $N$ is fixed. Hence, it suffices to minimize $\sum_{a^{i}_{j}\text{
black}}s(j)$.

This is because our goal is to find the minimum length sequence of swaps such
that all red vertices are below the blue vertices. First, it is easy to see
that $s(j)\geq\min\\{B_{F}(j),R_{F}(j)\\}$, because we have either swap with
$a^{i}_{j}$ all the blue vertices below $a^{i}_{j}$, so they end up above
$a^{i}_{j}$ or all the red vertices that are above $a^{i}_{j}$, so they end up
below $a^{i}_{j}$.

It remains to give a sequence of swaps such that
$s(j)=\min\\{B_{F}(j),R_{F}(j)\\}$. One can verify that the following
procedure gives such a sequence: while at least one of the following rules can
be applied, perform it

  * •

if $a^{i}_{r}$ is a red vertex, $a^{i}_{b}$ blue vertex such that $r=b-1$,
that is $a^{i}_{r}$ is a predecessor of $a^{i}_{b}$, swap $a^{i}_{r}$ and
$a^{i}_{b}$,

  * •

if $a^{i}_{j}$ is black, $a^{i}_{j+1}$ is blue, and $B_{F}(j)\leq R_{F}(j)$,
then swap $a^{i}_{j}$ and $a^{i}_{j+1}$,

  * •

if $a^{i}_{j}$ is black, $a^{i}_{j-1}$ red, and $R_{F}(j)<B_{F}(j)$, then swap
$a^{i}_{j}$ and $a^{i}_{j-1}$.

Let us fix a black vertex $a^{i}_{j}$. It is easy to show by induction on
$\min\\{B_{F}(j),R_{F}(j)\\}$ that the number of swaps of this vertex is
exactly $\min\\{B_{F}(j),R_{F}(j)\\}$. Clearly if
$\min\\{B_{F}(j),R_{F}(j)\\}=0$, then $a^{i}_{j}$ never swaps with any vertex
in the above sequence. If $R_{F}(j)<B_{F}(j)$, then $a^{i}_{j}$ might swap
with red vertex at position $a^{i}_{j-1}$. In this case the black vertex we
consider becomes $a^{i}_{j-1}$ and the number of blue vertices below remains
the same and the number of red vertices above decreases by one and
$s(j)=\min\\{B_{F}(j),R_{F}(j)\\}$ by induction. Similarly, if $R_{F}(j)\geq
B_{F}(j)$, $a^{i}_{j}$ might swap with blue vertex at position $a^{i}_{j+1}$
and $s(j)=\min\\{B_{F}(j),R_{F}(j)\\}$ follows by induction as well. It
remains to show that if none of these rules can be applied, then there is no
red vertex above a blue one. For the sake of contradiction let us assume that
none of the rules apply and there is some red vertex above a blue vertex. Let
$a^{i}_{r}$ be a red vertex and $a^{i}_{b}$ a blue vertex such that $r<b$
(i.e., $a^{i}_{r}$ is above $a^{i}_{b}$) and all vertices between $a^{i}_{r}$
be a red vertex and $a^{i}_{b}$ are black. Clearly $a^{i}_{r}\neq
a^{i}_{b-1}$, else the first rule applies. Hence both vertices $a^{i}_{r+1}$
and $a^{i}_{b-1}$ are black (possibly $r+1=b-1$). Now, all vertices between
$a^{i}_{r+1}$ and $a^{i}_{b-1}$ are black and it follows that
$B_{F}(r+1)=B_{F}(b-1)$ and $R_{F}(r+1)=R_{F}(b-1)$. Since the second rule
does not apply, it follows that $B_{F}(b-1)>R_{F}(b-1)$. However that implies
$R_{F}(r+1)<B_{F}(r+1)$ and the third rule applies, which is a contradiction.
∎

Let $N_{F^{\prime}}(j)$ be the number of black vertices $a_{b}^{i}$ below
$a_{j}^{i}$ such that $R_{F^{\prime}}(b)<B_{F^{\prime}}(b)$. From Claim 3.2.1
we can now deduce that if $e,e^{\prime}\in E_{b}$ such that $e^{\prime}\cap
A_{i}=a^{i}_{j}$, then

$\displaystyle f_{i}(F$ $\displaystyle+e+e^{\prime})-f_{i}(F+e)$
$\displaystyle=B_{F+e+e^{\prime}}(j)-\min\\{B_{F+e}(j),R_{F+e}(j)\\}+N_{F+e}(j)$
$\displaystyle=B_{F+e}(j)-\min\\{B_{F+e}(j),R_{F+e}(j)\\}+N_{F+e}(j)$
$\displaystyle=\max\\{0,B_{F+e}(j)-R_{F+e}(j)\\}+N_{F+e}(j)$
$\displaystyle\leq\max\\{0,B_{F}(j)-R_{F}(j)\\}+N_{F}(j)$
$\displaystyle=f_{i}(F+e^{\prime})-f_{i}(F).$

The above inequality follows because $R_{F+e}(j)\geq R_{F}(j)$ and
$B_{F+e}(j)=B_{F}(j)$. Furthermore $N_{F+e}(j)\leq N_{F}(j)$ since
$R_{F}(b)\leq R_{F+e}(b)$ and $B_{F+e}(b)=B_{F}(b)$. It follows that $f$ is
computable in polynomial time and submodular. We can now efficiently minimise
the total cost $h^{\prime}$ by the algorithm of Theorem 3.1 and thus compute
in polynomial time a minimal sequence of swaps making $M$ and hence $S$
stable.∎

##  4 Hardness results

In this section we consider the problem of finding a minimum length sequence
of swaps that leads to an arbitrary maximum stable matching. Note that even
though we can find minimum length sequence for a fixed maximum matching, there
might be exponentially many different maximum matchings, so the algorithms
from the previous section cannot be applied to solve this problem. Indeed, we
will show that the problem of deciding whether there exists a sequence of at
most $k$ swaps that leads to an instance with a perfect stable matching is NP-
hard and W[1]-hard parameterized by $k$. We will call this problem Swap
Distance to Perfect Stable Matching ($\Delta$-PSM). Note that Chen et al. [5]
proved that $\Delta$-PSM is W[1]-hard if $G$ has a perfect matching and the
parameter is $n_{u},$ the number of vertices unmatched in any stable matching
of $G$. The following two propositions show that W[1]-hardness with parameter
$k$ is strictly stronger than the result by Chen et al. [5].

######  Proposition 4.1.

Let $I=(G,L)$ be an SMP instance, $k$ the minimum number of swaps that leads
to an instance with a perfect stable matching and $n_{u}$ the number of
vertices unmatched in any stable matching of $G$, then $n_{u}\leq 2k$.

###### Proof.

Let $M$ be a stable matching in $I$ and $M^{\prime}$ a perfect stable matching
in an instance $I^{\prime}$ obtained from $I$ by exactly $k$ swaps. Note that
$M\cup M^{\prime}$ induces a union of cycles and paths. Moreover, $M\cup
M^{\prime}$ has to contain at least $|M^{\prime}|-|M|=\frac{n_{u}}{2}$ paths
that start and end with an edge in $M^{\prime}$ and the consecutive edges
alternate between an edge in $M$ and an edge in $M^{\prime}$. Note that any
such alternating path starts and ends in a vertex unmatched by $M$. Moreover,
the set of unmatched vertices is the same in any stable matching of $I$ due to
the Rural Hospitals Theorem. Let $P=v_{1}v_{2}v_{3}\ldots v_{q}$ be one such
alternating path, where $v_{1}$ and $v_{q}$ are unmatched by $M$. The edges
$v_{2i-1}v_{2i}$, for $i\in[\frac{q}{2}]$, are in $M^{\prime}$ and the edges
$v_{2i}v_{2i+1}$, for $i\in[\frac{q-2}{2}]$, are in $M$. We show that there is
a swap in a preference list of at least one vertex of $P$. The proposition
then follows from the fact that there are at least $\frac{n_{u}}{2}$ such
paths and these paths are vertex disjoint.

For the sake of contradiction, let us assume that there is no swap in a
preference list of any vertex on $P$. First note that since $v_{1}$ is
unmatched by $M$, the vertex $v_{2}$ prefers $v_{3}$ to $v_{1}$, otherwise
$v_{1}v_{2}$ would be a blocking edge of $M$. We now show by induction that
since there is no swap in a preference list of any vertex of $P$, then $v_{2}$
also prefers $v_{1}$ to $v_{3}$, which is a contradiction. Since, $v_{q}$ is
unmatched by $M$ and $v_{q-2}v_{q-1}\in M$, the vertex $v_{q-1}$ prefers
$v_{q-2}$ to $v_{q}$. As an induction hypothesis assume that for some $i$,
$2<i<q$, the vertex $v_{i}$ prefers $v_{i-1}$ to $v_{i+1}$. Edges
$v_{i-2}v_{i-1}$ and $v_{i}v_{i+1}$ are together in a stable matching. Since
by the induction hypothesis $v_{i}$ prefers $v_{i-1}$ to $v_{i+1}$, if the
vertex $v_{i-1}$ prefers $v_{i}$ to $v_{i-2}$, then the edge $v_{i-1}v_{i}$ is
blocking for this stable matching. We conclude that $v_{i-1}$ prefers
$v_{i-2}$ to $v_{i}$ and the induction step holds. Applying repeatedly the
induction step, we obtain that $v_{2}$ prefers $v_{1}$ to $v_{3}$, which is
the desired contradiction. ∎

######  Proposition 4.2.

For every $n\in\mathbb{N}$, $n\geq 1$, there exists an SMP instance $(G,L)$
such that $G$ is a bipartite graph with $2n+2$ vertices that admits a perfect
matching, only two vertices are unmatched in the unique stable matching of $G$
and the minimum number of swaps that leads to an instance with a perfect
stable matching is at least $n$.

###### Proof.

Let $G$ be a path of length $2n+1.$ That is,
$V(G)=\\{v_{0},v_{1},\ldots,v_{2n+1}\\}$ and
$E(G)=\\{v_{0}v_{1},v_{1}v_{2},v_{2}v_{3},\ldots,v_{2n}v_{2n+1}\\}.$ Assume
that for all $i\in[n]$, $v_{2i}$ prefers $v_{2i-1}$ over $v_{2i+1}$ and
$v_{2i-1}$ prefers $v_{2i}$ over $v_{2i-2}$. Now
$M=\\{v_{1}v_{2},v_{3}v_{4},\ldots,v_{2n-1}v_{2n}\\}$ is the only stable
matching in $G$. If we want
$M^{\prime}=\\{v_{0}v_{1},v_{2}v_{3},\ldots,v_{2n}v_{2n+1}\\}$ to become a
stable matching then we need to change the preference of $v_{2i-1}$ or
$v_{2i}$ for every $i\in[n]$, as otherwise $v_{2i-1}v_{2i}$ would be a
blocking edge. Hence, $k\geq n.$ ∎

Gupta et al. [9] studied a related problem called Almost Stable Marriage
(ASM), which takes as an input an instance $(G,L)$ of SMP and two non-negative
integers $k$ and $t$ and asks whether there is a matching whose size is at
least $t$ more than the size of a stable matching in $G$ such that the
matching has at most $k$ blocking edges. The authors show that ASM is
W[1]-hard parameterized by $k+t$ even when the input graph $G$ has max degree
$3$. While they did not state it explicitly their hardness proof implies the
following result.

######  Theorem 4.3 ([9]).

ASM is NP-hard and W[1]-hard parametrized by $k+t$ even on instances
$\mathcal{I}=(G,L,k,t)$ such that

  1. 1.

$G$ has max degree three,

  2. 2.

$G$ admits a perfect matching and a stable matching of size
$\frac{|V(G)|}{2}-t$, and

  3. 3.

If $\mathcal{I}$ is a YES-instance, then in every perfect matching $M$ with at
most $k$ blocking edges, every blocking edge is incident to a vertex of degree
two.

Moreover, ASM does not admit an $|V(G)|^{o(\sqrt{k+t})}$ algorithm, unless ETH
fails.

To show that $\Delta$-PSM is NP-hard and W[1]-hard parameterized by $k$, we
start with the following observation.

######  Observation 4.3.1.

Let $I=(G=(A,B;E),L)$ be an SMP instance, $M$ a matching such that there are
exactly $k$ blocking edges of $M$ in $E$, and let $\sigma$ be a swap. Then
there are at least $k-1$ blocking edges of $M$ in $E$ in $\sigma(I)$.

###### Proof.

Swap $\sigma$ increases preference of exactly one vertex $v$ in exactly one
list of some vertex $u$. Hence the only blocking edge in the original instance
that can become non-blocking is the edge $uv$. ∎

Now we are ready to show the hardness of $\Delta$-PSM.

######  Theorem 4.4.

$\Delta$-PSM is NP-complete. Moreover, $\Delta$-PSM is W[1]-hard parameterized
by the length $k$ of the sought sequence of swaps.

###### Proof.

Given a sequence of $k$ swaps, it is easy to verify that the instance obtained
by applying the sequence of swaps admits a stable perfect matching. Moreover,
given a perfect matching $M$ of $G$, a polynomial in $n$ many swaps suffices
to make $M$ stable. Hence $\Delta$-PSM is in NP. To show that the problem is
NP-hard and W[1]-hard parameterized by $k$, we reduce from ASM. Let
$\mathcal{I}=(G,L,k,t)$ be an instance of ASM such that

  1. 1.

$G$ has max degree three,

  2. 2.

$G$ admits a perfect matching and a stable matching of size
$\frac{|V(G)|}{2}-t$, and

  3. 3.

If $\mathcal{I}$ is a YES-instance, then in every perfect matching $M$ with at
most $k$ blocking edges, every blocking edge is incident to a vertex of degree
two.

Recall that ASM remains NP-hard and W[1]-hard parameterized by $k+t$ on such
instances by Theorem 4.3. We let $\mathcal{I}^{\prime}=(G,L,k)$ be an instance
of $\Delta$-PSM and we will show that $\mathcal{I}$ is a YES-instance of ASM
if and only if $\mathcal{I}^{\prime}$ is a YES-instance of $\Delta$-PSM.
Since, this construction can be performed in polynomial time (we just take the
same instance) and the reduction is parameter-preserving, this implies that
$\Delta$-PSM is NP-hard and W[1]-hard parameterized by $k$.

Observation 4.3.1 implies that if a graph $G$ does not admit a perfect
matching $M$ with at most $k$ blocking edges, then $\mathcal{I}^{\prime}$ is a
NO-instance of $\Delta$-PSM. As the instance $\mathcal{I}$ of ASM admits a
perfect matching and a stable matching of size $\frac{|V(G)|}{2}-t$, it is
easy to see that if $\mathcal{I}$ is a NO-instance of ASM, then $G$ does not
admit a perfect matching $M$ with at most $k$ blocking edges and
$\mathcal{I}^{\prime}$ is a NO-instance of $\Delta$-PSM. On the other hand, if
$\mathcal{I}$ is a YES-instance of ASM, then $G$ admits a perfect matching $M$
with at most $k$ blocking edges and, by propery 3 of $\mathcal{I}$, every
blocking edge of $M$ is incident to a vertex of degree $2$. It is easy to see
that if $e=uv$ is a blocking edge and $u$ has degree $2$, then it suffices to
transpose the two vertices in $l(u)$. This swap also does not introduce new
blocking edges, as after this swap, vertex $u$ is matched with its most
preferred choice. Therefore, in this case, there is a sequence of at most $k$
swaps that makes $M$ a stable perfect matching and $\mathcal{I}^{\prime}$ is a
YES-instance. ∎

The ETH lower bound for ASM implies that $\Delta$-PSM does not admit an
algorithm of running time of $(n+n^{\prime})^{o(\sqrt{k})}$, where $k$ is the
length of the sought solution. On the other hand, at each step there are only
$2nn^{\prime}$ possible swaps and so there is a simple $O((2nn^{\prime})^{k})$
algorithm enumerating all possible sequences of at most $k$ swaps. By a small
change to the reduction by Gupta et al. [9] one can show that a significant
improvement over the $(2nn^{\prime})^{k}$ algorithm is unlikely.

In what follows we will sketch how to adapt the hardness proof by Gupta et al.
[9] to show that ASM, and hence also $\Delta$-PSM, does not admit an
$(n+n^{\prime})^{o(k/\log k)}$-time algorithm, unless ETH fails, and even
existence of an $(n+n^{\prime})^{o(k)}$-time algorithm would imply a
breakthrough in the area of parameterized algorithms and complexity.

The hardness proof of Gupta et al. [9] is a reduction from Multicolored Clique
(MCQ), where we are given a graph $G$ and a partition of $V(G)$ into $q$ parts
$V_{1},\ldots,V_{q}$; the goal is to decide the existence of a set $S\subseteq
V(G)$ such that $|V_{i}\cap S|=1$, for all $i\in[q]$, and $G[S]$ induces a
clique, that is, there is an edge between every pair of vertices in $G[S]$. It
is well known that MCQ does not admit an $|V(G)|^{o(q)}$ algorithm, unless ETH
fails. The main idea of the reduction is to introduce three types of gadgets -
“vertex set” gadgets, “edge set” gadgets, and “connection” gadgets. They
introduce one “vertex set” gadget for every vertex set $V_{i}$, one “edge set”
gadget for every $1\leq i<j\leq q$ that represents the set of edges between
$V_{i}$ and $V_{j}$. Finally the ”connection” gadgets connect a “vertex set”
gadget for $V_{i}$ with every ”edge set” gadget for edges between $V_{i}$ and
$V_{j}$, $j\neq i$. The parameter $t$ is then the number of “vertex set”
gadgets + the number of “edge set” gadgets and $k$ is the number of “vertex
set” gadgets + 2 times the number of “edge set” gadgets. Hence
$t=q+\binom{q}{2}$ and $k=q^{2}$. Moreover, every perfect matching of “vertex
set” gadget forces at least one blocking edge inside the gadget that depends
on the selected vertex for the clique in the corresponding vertex set. Every
perfect matching of “edge set” gadget forces at least two blocking edges
inside the gadget that depend on the selected edge for the clique in the
corresponding vertex set. Finally, a “connection” gadget is just a set of
edges between a “vertex set” gadget and an “edge set” gadget that contains
blocking edge if the edge selected by the “edge set” gadget is not incident to
the vertex selected by the “vertex set” gadget.

Given this high-level description of the hardness proof of [9] for ASM
parameterized by $k+t$, we sketch how one can adapt it to obtain
$(n+n^{\prime})^{o(k/\log k)}$ lower bound, under ETH. Namely, reduction will
be analogous, but from a different problem. In Partitioned Subgraph
Isomorphism (PSI) we are given on the input two undirected graphs $G$ and $H$
with $|V(H)|\leq|V(G)|$ ($H$ is _smaller_) and a mapping $\psi\colon V(G)\to
V(H)$ and the task is to determine whether $H$ is isomorphic to a subgraph of
$G$ (i.e., is there an injective mapping $\phi\colon V(H)\to V(G)$ such that
$\\{\phi(u),\phi(v)\\}\in E(G)$ for each $\\{u,v\\}\in E(H)$ and
$\psi\circ\phi$ is the identity)? Observe that MCQ is PSI, where the smaller
graph $H$ is a complete graph.

######  Theorem 4.5 (see [16] and [7]).

If there is an algorithm $\mathbb{A}$ and an arbitrary function $f$ such that
$\mathbb{A}$ correctly decides every instance $(G,H)$ of PSI with the smaller
graph $H$ being 3-regular in time $f(|V(H)|)|V(G)|^{o(|V(H)|/\log|V(H)|)}$,
then ETH fails.555We would like to point out that, as far as we know, it is
open whether PSI admits even $f(|V(H)|)|V(G)|^{o(|V(H)|)}$ algorithm.

Note that the mapping $\psi\colon V(G)\to V(H)$ partitions the vertices of
$V(G)$ into $q=|V(H)|$ many parts $V_{1},\ldots,V_{q}$, each corresponding to
a specific vertex of $H$. Moreover, we wish to select in each part $V_{i}$,
$i\in[q]$, exactly one vertex $v_{i}$, such that if $uw\in E(H)$ and $V_{i}$
corresponds to $u$ and $V_{j}$ corresponds to $w$, then $v_{i}v_{j}$ is an
edge in $G$. The reduction from PSI to ASM is precisely the same as the
reduction from MCQ to ASM, with only difference that we have “edge set”
gadgets only for pairs $1\leq i<j\leq q$ such that the sets $V_{i}$ and
$V_{j}$ correspond to adjacent vertices of $H$. If $H$ is $3$-regular, then
the number of “edge set” gadgets is $\frac{3q}{2}$ and hence in the instance
of ASM we obtain in the reduction, we get $t=\frac{5q}{2}$ and $k=4q$,
implying that ASM does not admit $|V(G)|^{o((k+t)/\log(k+t))}$-time algorithm,
unless ETH fails. Following the proof of Theorem 4.4, we then obtain the
following result.

######  Theorem 4.6.

If there is an algorithm that for every instance of SMP with a bipartite graph
on $n+n^{\prime}$ vertices decides whether there is a sequence of at most $k$
swaps that results in an instance of SMP with a perfect matching in time
$(n+n^{\prime})^{o(k/\log k)}$, then ETH fails.

Acknowledgement. We are grateful to the referee for a number of helpful
suggestions.

## References

  * [1] M. Balinski and G. Ratier.  Of stable marriages and graphs, and strategy and polytopes.  SIAM Rev., 39(4):575–604, 1997.
  * [2] M. Balinski and G. Ratier.  Graphs and marriages.  American Mathematical Monthly, 105(5):430–445, 1998.
  * [3] N. Boehmer, R. Bredereck, K. Heeger, and R. Niedermeier.  Bribery and control in stable marriage.  Journal of Artificial Intelligence Research, 71:993–1048, 2021\.
  * [4] R. Bredereck, J. Chen, D. Knop, J. Luo, and R. Niedermeier.  Adapting stable matchings to evolving preferences.  In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 1830–1837. AAAI Press, 2020.
  * [5] J. Chen, P. Skowron, and M. Sorge.  Matchings under preferences: Strength of stability and trade-offs.  ACM Transactions on Economics and Computation, 9(4):1–55, 2021\.
  * [6] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [7] E. Eiben, D. Knop, F. Panolan, and O. Suchý.  Complexity of the steiner network problem with respect to the number of terminals.  In R. Niedermeier and C. Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, volume 126 of LIPIcs, pages 25:1–25:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [8] D. Gale and L. S. Shapley.  College admissions and the stability of marriage.  The American Mathematical Monthly, 69(1):9–15, 1962.
  * [9] S. Gupta, P. Jain, S. Roy, S. Saurabh, and M. Zehavi.  On the (parameterized) complexity of almost stable marriage.  In N. Saxena and S. Simon, editors, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, December 14-18, 2020, BITS Pilani, K K Birla Goa Campus, Goa, India (Virtual Conference), volume 182 of LIPIcs, pages 24:1–24:17, 2020.
  * [10] G. Z. Gutin, P. R. Neary, and A. Yeo.  Unique stable matchings.  CoRR, abs/2106.12977, 2021.
  * [11] R. Impagliazzo and R. Paturi.  Complexity of $k$-SAT.  In Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pages 237–240. IEEE Computer Society, 1999.
  * [12] Y. Kamada and F. Kojima.  Efficient matching under distributional constraints: Theory and applications.  The American Economic Review, 105(1):67–99, 2015.
  * [13] F. Maffray.  Kernels in perfect line-graphs.  J. Comb. Theory Ser. B, 55(1):1?8, 1992.
  * [14] T. Mai and V. V. Vazirani.  Finding stable matchings that are robust to errors in the input.  In Y. Azar, H. Bast, and G. Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 60:1–60:11, 2018.
  * [15] T. Mai and V. V. Vazirani.  An efficient algorithm for fully robust stable matchings via join semi-sublattices.  CoRR, abs/1804.05537v4, 2020.
  * [16] D. Marx.  Can you beat treewidth?  Theory Comput., 6(1):85–112, 2010.
  * [17] D. McVitie and L. Wilson.  Stable marriage assignment for unequal sets.  BIT Numerical Math., 10(3):295–309, 1970.
  * [18] A. E. Roth.  The evolution of the labor market for medical interns and residents: a case study in game theory.  Journal of Political Economy, 92(6):991–1016, 1984.
  * [19] A. E. Roth.  On the allocation of residents to rural hospitals: a general property of two-sided matching markets.  Econometrica, 54(2):425–427, 1986.
  * [20] A. Schrijver.  A combinatorial algorithm minimizing submodular functions in strongly polynomial time.  Journal of Combinatorial Theory, Series B, 80(2):346–355, 2000\.