National University of Singapore, Singapore<EMAIL_ADDRESS>Chennai
Mathematical Institute<EMAIL_ADDRESS>Kushagra Chatterjee and
Prajakta Nimbhorkar [100]Mathematics of Computing Graph Algorithms

# Popular Edges with Critical Nodes

Kushagra Chatterjee111Work was done when the author was a Master’s student in
Chennai Mathematical Institute222supported in part by an MoE AcRF Tier 2 grant
(WBS No. A-8000416-00-00) and an ODPRT grant (WBS No. A-0008078-00-00)
Prajakta Nimbhorkar333Supported in part by SERB Award CRG/2019/004757.

###### Abstract

In the popular edge problem, the input is a bipartite graph $G=(A\cup B,E)$
where $A$ and $B$ denote a set of men and a set of women respectively, and
each vertex in $A\cup B$ has a strict preference ordering over its neighbours.
A matching $M$ in $G$ is said to be popular if there is no other matching
$M^{\prime}$ such that the number of vertices that prefer $M^{\prime}$ to $M$
is more than the number of vertices that prefer $M$ to $M^{\prime}$. The goal
is to determine, whether a given edge $e$ belongs to some popular matching in
$G$. A polynomial-time algorithm for this problem appears in [3].

We consider the popular edge problem when some men or women are prioritized or
critical. A matching that matches all the critical nodes is termed as a
feasible matching. It follows from [13, 18, 23, 22] that, when $G$ admits a
feasible matching, there always exists a matching that is popular among all
feasible matchings.

We give a polynomial-time algorithm for the popular edge problem in the
presence of critical men or women. We also show that an analogous result does
not hold in the many-to-one setting, which is known as the Hospital-Residents
Problem in literature, even when there are no critical nodes.

###### keywords:

Matching, Stable Matching, Popular feasible Matching

##  1 Introduction

The stable marriage problem is well-studied in literature. The input instance
is a bipartite graph $G=(A\cup B,E)$ where $A$ and $B$ denote the sets of men
and women respectively, and each vertex has a strict preference ordering on
its neighbors. The preference ordering is referred to as the preference list
of the vertex. Such an instance is referred to as a marriage instance. A
matching $M$ in $G$ is said to be stable if there is no pair $(a,b)\in E$ such
that both $a$ and $b$ prefer each other over their respective partners in $M$,
denoted as $M(a)$ and $M(b)$ respectively. A matching is called unstable if
such a pair $(a,b)$ exists, and such a pair $(a,b)$ is called a blocking pair.
In their seminal paper, Gale and Shapley showed that stable matchings always
exist and can be computed in linear time [6]. However, all the stable
matchings match the same set of vertices [7] and they can be as small as half
the size of a maximum matching [11]. Hence popularity has been considered as
an alternative to stability.

######  Definition 1.1 (Popular Matching).

A matching $M$ is said to be popular in a marriage instance $G$ if, for all
matchings $N$ in $G$, the number of vertices that prefer $N$ over $M$ is no
more than the number of vertices that prefer $M$ over $N$.

In other words, $M$ is popular if it does not lose a head-to-head election
with any other matching $N$ where votes are cast by vertices. This notion was
introduced by Gärdenfors [8] and has been well-studied since then (see Section
1.3). Popular matchings always exist since stable matchings are popular, in
fact, stable matchings are minimum size popular matchings [11]. A subclass of
maximum size popular matchings called dominant matchings was identified in
[3].

######  Definition 1.2 (Dominant Matching).

A matching $M$ in a marriage instance $G$ is called a _dominant matching_ if
$M$ is popular, and for each $N$ such that $|N|>|M|$, the number of vertices
that prefer $M$ to $N$ is more than the number of vertices that prefer $N$ to
$M$.

Informally, a matching $M$ is a dominant matching if $M$ is popular and $M$
wins against any other matching $N$ which is larger than $M$. Note that a
dominant matching is clearly a maximum size popular matching but a maximum
size popular matching need not be a dominant matching.

Cseh and Kavitha [3] addressed the problem of determining whether there is a
popular matching containing a given edge $e$, referred to as the popular edge
problem. They gave a polynomial-time algorithm for this problem. This is
surprising since, in [5], it was shown that stable matchings and dominant
matchings are the only two tractable subclasses of popular matchings, and it
is NP-hard to find a popular matching which is neither stable nor dominant.

Popular matchings find applications in situations where certain nodes are
prioritized or critical and they are required to be matched. A real-life
example of this scenario is assignment of sailors to billets in the US Navy
[24, 27, 18] where certain billets are required to be matched. Rural hospitals
often face the problem of understaffing in the National Resident Matching
Program in the USA [25, 26]. Thus marking some positions in these hospitals as
critical and finding a critical matching provides a way to address this issue.
While matching students to mentors, it may be required to assign mentors to
all the students whose past performance is below a certain threshold. In
several other applications, a subset of people needs to be prioritized based
on their economic, ethnic, geographic, or medical backgrounds. A matching that
matches all the prioritized or critical nodes is termed as a feasible
matching. Such a scenario has been considered in [22] and [23] in the many-to-
one setting, and it is shown that there always exists a matching that is
popular within the set of feasible matchings. In [18], a matching that matches
as many critical nodes as possible has been referred to as a critical
matching. It is shown in [18] that a matching that is popular in the set of
critical matchings, called a popular critical matching, always exists and a
polynomial time algorithm is given for the same. A special case of this is
addressed in [13], where all the nodes are critical, and hence a critical
matching is a matching that is popular amongst all maximum size matchings. A
polynomial-time algorithm is given in [13] for this problem.

In the presence of critical men or women, popular edge problem for feasible
matchings is a natural question that arises in this context. Thus, given a
marriage instance $G=(A\cup B,E)$, a set of critical nodes $C\subseteq A$, and
an edge $e$, the problem is to determine whether there is a feasible matching
containing $e$ that is popular within the set of feasible matchings. We call
this the popular feasible edge problem.

######  Definition 1.3 (Popular feasible matching).

Given a marriage instance $G=(A\cup B,E)$, and a set of critical nodes $C$, a
feasible matching that is popular among all the feasible matchings is called a
popular feasible matching.

We also define dominant feasible matchings below.

######  Definition 1.4 (Dominant feasible matching).

Given a marriage instance $G=(A\cup B,E)$ and a set of critical nodes $C$, a
matching $M$ is called a dominant feasible matching if $M$ is a popular
feasible matching, and for all the feasible matchings $N$ such that $|N|>|M|$,
$M$ gets strictly more votes than $N$.

###  1.1 Our contributions

We show the following main result in this paper:

######  Theorem 1.5.

Given a marriage instance $G=(A\cup B,E)$ along with a set of critical nodes
$C\subseteq A$, an edge $e\in E$ belongs to a popular feasible matching in $G$
if and only if $e$ belongs to a minimum size popular feasible matching or a
dominant feasible matching in $G$.

Theorem 1.5, along with the following results, leads to a polynomial-time
algorithm for the popular critical edge problem.

######  Theorem 1.6.

There are polynomial-time reductions from a given instance $G$ with a set of
critical men $C$ to marriage instances $G^{\prime}$ and $G^{\prime\prime}$
such that there is a surjective map from stable matchings in $G^{\prime}$ to
minimum size popular feasible matchings in $G$ and there is a surjective map
from stable matchings in $G^{\prime\prime}$ to dominant feasible matchings in
$G$.

The reductions are similar to those in [22, 23, 18], however, the surjectivity
of the maps is not shown there. In [19], a similar reduction is given and the
surjectivity of the map is shown using dual certificates, whereas our proofs
of surjectivity are combinatorial.

Counter-example for the many-to-one setting:  We show that a result analogous
to Theorem 1.5 does not generalize to the many-to-one setting referred to as
the Hospital-Residents problem in literature, even when there are no critical
nodes. Figure 1 shows such an example. Informally, popularity in the many-to-
one setting is defined as follows. To compare two matchings $M$ and $N$, a
hospital casts as many votes as its upper quota. It compares the sets of
residents $M(h)$ and $N(h)$ that it gets in the matchings $M$ and $N$
respectively by fixing any correspondence function between $M(h)\setminus
N(h)$ and $N(h)\setminus M(h)$. For the formal definition of popularity in the
many-to-one setting in the presence of critical nodes, we refer the reader to
[23, 22], where it is shown that the respective algorithms output a matching
that is popular under any choice of the correspondence function.

Figure 1: Here $H$ and $R$ are the sets of hospitals and residents
respectively, $h$ has upper quota or capacity $2$, other hospitals have upper
quota $1$. The only stable matching is $M=\\{(p,h),(q,h)\\}$ of size $2$
whereas the only dominant matching is $M_{2}$, of size $4$. The edge
$(q,h^{\prime})$ belongs to a popular matching $M_{1}$ of size $3$, but does
not belong to the stable matching $M$ or to the dominant matching $M_{2}$.
Thus Theorem 1.5 does not hold for this instance.

###  1.2 Overview of our algorithm

We give a brief outline of our algorithm. After proving Theorem 1.5, the
algorithm to determine whether an edge $e$ belongs to a popular feasible
matching goes as follows:

  1. (i)

Check whether $e$ belongs to a minimum size popular feasible matching. If so,
output yes and stop, otherwise go to the next step.

  2. (ii)

Check whether $e$ belongs to a dominant feasible matching. If so, then output
yes and stop. If not, then conclude that $e$ does not belong to a popular
feasible matching in that instance by Theorem 1.5.

For steps (i) and (ii) above, we use the reductions mentioned in Theorem 1.6.
For an edge $e$ in $G$, there are multiple edges in $G^{\prime}$ and
$G^{\prime\prime}$ corresponding to $e$. The stable edge algorithm of [21] can
be used to determine whether any of the edges that correspond to $e$ in
$G^{\prime}$ or $G^{\prime\prime}$ is contained in some stable matching in
$G^{\prime}$ or $G^{\prime\prime}$. The details are given in Section 3.

To prove Theorem 1.5, we assume that $e$ is contained in a popular feasible
matching $M$ which is neither a minimum size popular feasible matching nor a
dominant feasible matching. We give a _Partition Method_ in Section 3.1 which
partitions the given instance into three parts. We call the restrictions of
$M$ on the three parts as $M_{d}$, $M_{m}$ and $M_{r}$. Since $e$ is contained
in $M$, $e$ must belong to one of the three parts viz. $M_{d}$, $M_{m}$ and
$M_{r}$. If $e\in(M_{d}\cup M_{r})$, we convert the matching $M_{m}$ to
another matching $M^{\prime}_{d}$ which is a dominant feasible matching in
that part, and show that $M^{*}_{d}=(M_{d}\cup M^{\prime}_{d}\cup M_{r})$ is a
dominant feasible matching in the whole instance. Thus $e$ is contained in a
dominant feasible matching, namely $M^{*}_{d}$. Similarly, if $e\in(M_{m}\cup
M_{r})$ then we convert the matching $M_{d}$ to another matching
$M_{m}^{\prime}$ which is a minimum size popular feasible matching in the
respective part, and moreover, $M^{*}_{m}=(M_{m}^{\prime}\cup M_{m}\cup
M_{r})$ is a minimum size popular feasible matching in the whole instance.
Thus $e$ belongs to the minimum size popular feasible matching $M^{*}_{m}$.

###  1.3 Related Results

Gale and Shapley proposed an algorithm to find a stable matching in a marriage
instance in their seminal paper [6]. The notion of popular matching was
introduced by Gärdenfors [8]. Popular matchings in the marriage instance have
been considered first in [11, 13]. An $O(m)$-time algorithm to find a dominant
matching in a marriage instance is given in [13]. In [13], a size-popularity
tradeoff has been considered, and a polynomial-time algorithm for finding a
maximum matching that is popular among all maximum matchings is given. The
popular edge problem is inspired by the _stable edge problem_. The stable edge
problem involves deciding whether a given edge $e$ belongs to a stable
matching in a Stable Marriage instance. A polynomial-time algorithm for the
stable edge problem is given in the book by Knuth[21].

Cseh and Kavitha [3] addressed the popular edge problem and gave an $O(m)$
time algorithm for the same. Later, Faenza et. al [5] show that the problem of
deciding whether an instance admits a popular matching containing a set of two
or more edges is NP-Hard. In that paper, the authors also show that finding a
popular matching in a stable marriage instance, which is neither stable nor
dominant is NP-Hard.

In [22], the authors showed that a popular feasible matching always exists in
an HRLQ instance. This has been further generalized by Nasre et al. [23] to
the HRLQ case with critical residents. While our work and [22, 23] deal with
instances that admit a feasible matching, the work of Kavitha [18] contains an
algorithm to find a popular critical matching i.e., a matching that matches
maximum possible number of critical nodes and is popular among all such
matchings. Problems related to HRLQ have also been considered in [10] and [1]
in different settings. Besides this, there has been a lot of recent work on
various aspects of popular matchings and their generalizations e.g. weighted
popular matchings, quasi-popular matchings, extended formulations, popular
matchings with one-sided bias, dual certificates to popularity, popular
matchings polytope and its extension complexity, hardness and algorithms for
popular matchings in case of ties in preferences etc. [19, 16, 17, 20, 4, 15,
12, 14, 2, 9].

A comparison with [3]: Cseh and Kavitha in their paper [3] presented an
$O(m)$-time algorithm for the popular edge problem. Our result follows a
similar template as theirs, although unlike that in [3] where nodes are
divided into two levels, we have nodes divided into a number of levels
proportional to the number of critical nodes. Also, we need to partition the
given instance into three parts, all of which can have blocking pairs, whereas
in [3], all the blocking pairs can be put into only one of the two parts
straight away.

###  1.4 Organization of the paper

In Section 2, we give the reductions from a marriage instance with critical
men to marriage instances without critical nodes. In Section 3, we prove
Theorem 1.5 and discuss the popular edge algorithm.

##  2 The Reductions

We describe the reductions from a marriage instance $G=(A\cup B,E)$ with a
critical node set $C\subseteq A$ to marriage instances $G^{\prime}$ and
$G^{\prime\prime}$ such that there is a surjective map from the set of stable
matchings in $G^{\prime}$ to the set of minimum size popular feasible
matchings in $G$, and a surjective map from the set of stable matchings in
$G^{\prime\prime}$ to the set of dominant feasible matchings in $G$, thereby
proving Theorem 1.6.

We recall some notation below, that is standard in popular matchings
literature (e.g. [11, 13, 3] etc.)

######  Definition 2.1 (Edge labels).

Given a matching $M$ in $G$, a vertex $u$ assigns a label $+1$ (respectively
$-1$) to an edge $(u,v)$ incident on it if $(u,v)\notin M$ and $u$ prefers $v$
over its partner in $M$ denoted by $M(u)$ (respectively $M(u)$ over $v$). Thus
each edge $(u,v)$ gets two labels, one from $u$ and the other from $v$.

By above definition, an edge not present in a given matching $M$ can get one
of the four labels $(+1,+1),(+1,-1),(-1,+1),(-1,-1)$. We use the convention
that the first label in the pair is from a vertex in $A$ and the second label
is from a vertex in $B$. Any vertex prefers to be matched to one of its
neighbors over remaining unmatched.

###  2.1 Reduction from $G$ to $G^{\prime}$

Given an instance $G$, the instance $G^{\prime}$ is constructed as follows.
Let $C\subseteq A$ be the set of critical nodes and $\ell=|C|$.

  * •

The set $A^{\prime}$:  For each $m\in C$, $A^{\prime}$ has $(\ell+1)$ copies
of $m$, denoted by the set $A^{\prime}_{m}=\\{m^{0},m^{1},...,m^{\ell}\\}$. We
refer to $m^{i}\in A^{\prime}$ as the level $i$ copy of $m\in A$. For each
$m\in A\setminus C$, $A^{\prime}$ has only one copy of $m$, denoted
$A^{\prime}_{m}=\\{m^{0}\\}$. Now, $A^{\prime}=\bigcup\limits_{m\in
A}A^{\prime}_{m}$.

  * •

The set $B^{\prime}$:  All the women in $B$ are present in $B^{\prime}$.
Additionally, corresponding to each $m\in C$, $B^{\prime}$ contains $\ell$
dummy women denoted by the set
$D_{m}=\\{d_{m}^{1},d_{m}^{2},d_{m}^{3},...,d_{m}^{\ell}\\}$. We call
$d_{m}^{i}$ as the level $i$ dummy woman for $m$. For $m\in A\setminus C$,
$D_{m}=\emptyset$. Now, $B^{\prime}=B\cup\bigcup\limits_{m\in A}D_{m}$.

We denote by Pref($m$) and Pref($w$) the preference lists of $m\in A$ and
$w\in B$ respectively. Let Pref($w$)i be the list of level $i$ copies of men
present in Pref($w$), if these copies exist.

We now describe the preference lists in $G^{\prime}$. Here $\circ$ denotes the
concatenation of two lists.

$m^{0}$ s.t. $m\in A\setminus C$ | : | Pref($m$)
---|---|---
$m\in C$, $i\in\\{0,\dots,\ell\\}$: |  |
$m^{0}$ | : |  Pref($m$), $d_{m}^{1}$
$m^{i}$ | : |  $d_{m}^{i}$, Pref($m$), $d_{m}^{i+1}$, $i\in\\{1,\ell-1\\}$)
$m^{\ell}$ | : |  $d_{m}^{\ell}$, Pref($m$)
$w$ s.t. $w\in B$ | : |  Pref($w$)${}^{\ell}\circ$ Pref($w$)${}^{\ell-1}\circ\ldots\circ$Pref($w$)0
$d^{i}_{m}$,$i\in\\{1,\dots,\ell\\}$ | : |  $m^{i-1}$, $m^{i}$

###  2.2 Correctness of the reduction

After constructing $G^{\prime}$, the mapping of a stable matching $M^{\prime}$
in $G^{\prime}$ to a minimum size popular feasible matching $M$ in $G$ is a
simple and natural one: For $m\in A$, define the set
$M(m)=B\cap\bigcup\limits_{m\in A}M^{\prime}(m^{i})$, which is the set of non-
dummy women matched to any copy of $m$ in $A^{\prime}$. In the rest of this
section, the term image always refers to the image under this map.

It remains to prove that $M$ is a minimum size popular feasible matching i.e.,
$M$ is a matching in $G$, it is feasible, popular, and no matching smaller
than $M$ is popular. We define some terminology first. A man $m\in A$ and his
matched partner $w\in B$ in $M$ are said to be at level $i$ if $(m^{i},w)\in
M^{\prime}$. A man $m\in A$ which is unmatched in $M$ is said to be at level
$i$ if $m^{i}$ in $A^{\prime}$ is unmatched in $M^{\prime}$. All unmatched
women are said to be at level $0$. Now we give a sufficient condition for a
minimum size popular feasible matching in $G$.

######  Theorem 2.2.

The image $M$ of a stable matching $M^{\prime}$ in $G^{\prime}$ is a minimum
size popular feasible matching in $G$ and it satisfies the following
conditions. Moreover, any matching $M$ that satisfies the following conditions
for some assignment of levels to vertices of $G$ is a minimum size popular
feasible matching.

  1. 1.

All $(+1,+1)$ edges are present in between a man at level $i$ and a woman $w$
at level $j$ where $j>i$.

  2. 2.

All edges between a man at level $i$ and a woman at level $(i-1)$ are
$(-1,-1)$ edges.

  3. 3.

No edge is present between a man at level $i$ and a woman at level $j$ where
$j\leq(i-2)$, and all the edges of $M$ are between vertices at the same level.

  4. 4.

All unmatched men are at level $0$.

######  Proof 2.3.

Here we need to show that if $M$ satisfies the four conditions, then $M$ is a
minimum size popular feasible matching. So, to prove this we show at first $M$
is a popular feasible matching and then we show that, for all feasible
matchings $N$ such that $|N|<|M|$, we have $\phi(N,M)<\phi(M,N)$.

First we prove that $M$ is a feasible matching. Suppose $M$ is not a feasible
matching and there exists a feasible matching $N$ in that marriage instance
with critical men. Recall that we are only concerned with those instances
which have at least one feasible matching. Suppose $m$ is a critical man who
is unmatched in $M$. So, the graph $M\oplus N$ must contain an alternating
path $\rho$ which starts from $m$. Now $\rho$ can end in a man $m^{\prime}$ or
in a woman $w^{\prime}$.

CASE 1: $\rho$ ends in $m^{\prime}$: Let
$\rho=(m,w,m_{1},w_{1},....,m^{\prime})$. Since $\rho$ ends in $m^{\prime}$,
$m^{\prime}$ must be unmatched in $N$. Since $N$ is a feasible matching
$m^{\prime}$ must be a non critical man and hence will be at level $0$. Since
$m$ is unmatched in $M$, it has to be in the level $\ell$ otherwise if $m$ is
at level $i$ where $i<\ell$ then $(m^{i},d_{m}^{i+1})$ would be a $(+1,+1)$
edge in $M^{\prime}$ because $m^{i}$ is unmatched in $M^{\prime}$ and
$d_{m}^{i+1}$ prefers $m^{i}$ the most in $G^{\prime}$. Again no woman $w$
which is adjacent to $m$ can be at level $\ell-1$ because then $(m^{\ell},w)$
would form a $(+1,+1)$ edge in $M^{\prime}$ as $m^{\ell}$ is unmatched and $w$
prefers $m^{\ell}$ more than her matched partner which is at level $\ell-1$.
Hence, in $\rho$, $w$ is at level $\ell$ again $M(w)=m_{1}$ is also at level
$\ell$ because the level of a woman and her matched partner are same. Now,
$w_{1}$ cannot be at level less than $(\ell-1)$ due to Condition $3$ of
Theorem 2.2. Hence the alternating path $\rho$ can go only one level down that
is from a man at level $i$ to a woman at level $i-1$. Note that all the men
who are at level greater than $0$ are critical men because there is no copy of
a non-critical man of level greater than $0$ in $G^{\prime}$. Since $\rho$ can
go only one level down, hence there must exist at least one critical man at
each level from $1$ to $\ell-1$ and there are at least two critical men ($m$
and $m_{1}$) at level $\ell$. Hence, the number of critical men in $G$ is at
least $\ell+1$. This is a contradiction because we know the number of critical
men in $G$ is $\ell$.

CASE $2$: $\rho$ ends in $w^{\prime}$. Since $\rho$ ends in $w^{\prime}$,
$w^{\prime}$ has to unmatched in $M$ and thus the level of $w^{\prime}$ is $0$
as the level of each unmatched woman is defined to be $0$. Hence $\rho$ starts
from a man at level $\ell$ and ends at a woman at level $0$. Since $\rho$ can
only go one level down, hence using the same arguments as used in case $1$, we
get that there are at least $\ell+1$ critical men in $G$. This is a
contradiction because we know the number of critical men in $G$ is $\ell$.
Hence $M$ is a feasible matching.

Now, we prove that $M$ is a popular feasible matching.

Consider any feasible matching $N$ in $G$. We need to show that
$\phi(N,M)\leq\phi(M,N)$. Consider the graph $M\oplus N$. The graph $M\oplus
N$ is a disjoint union of alternating paths and cycles. If
$\phi(N,M)>\phi(M,N)$ then at least one of the following three conditions must
be satisfied in the graph $M\oplus N$ when we label the edges of $N$ with
respect to $M$.

  1. (a)

There is an alternating cycle with more $(+1,+1)$ edges than $(-1,-1)$ edges.

  2. (b)

There is an alternating path which has at least one end point unmatched in $M$
where the number of $(+1,+1)$ edges is more than the number of $(-1,-1)$
edges.

  3. (c)

There is an alternating path which has both the end points matched in $M$ and
the number of $(+1,+1)$ edges is at least two more than the number of
$(-1,-1)$ edges in that alternating path, and the path ends in a man $m\notin
P$.

Now, we show that none of the above conditions are satisfied which implies
that $\phi(N,M)\leq\phi(M,N)$ for all feasible matchings $N$ in the marriage
instance with critical men. Hence $M$ is a popular feasible matching.

Condition (a): From Condition $1$ of theorem 2.2 we get that a $(+1,+1)$ is
present in between a lower level man $m$ and a higher level woman $w$. Let us
assume the level of $m$ is $i$ and the level of $w$ is $j$, hence $j>i$. So,
if an alternating cycle $\rho$ in $M\oplus N$ has a $(+1,+1)$ edge in between
$m$ to $w$ then $\rho$ must return to $m$ again. Now, from the Condition $3$
of theorem 2.2 we get that an edge in $\rho$ can go only one level down that
is from a man at level $i$ to a woman at level $(i-1)$ (not below $(i-1)$) and
from condition $2$ we get that all edges in between a man at level $i$ and a
woman at level $(i-1)$ are $(-1,-1)$ edges. Hence we get that the alternating
subpath of $\rho$ from $w$ to $m$ must contain $(j-i)$ $(-1,-1)$ edges. Hence,
for one $(+1,+1)$ edge we get $(j-i)$ edges in $\rho$. Since, $(j-i)\geq 1$
(equality occurs when $i=(j-1)$) we get that the number of $(+1,+1)$ edges is
less than or equal to the number of $(-1,-1)$ edges in $\rho$. Hence,
condition (a) is not satisfied in $M\oplus N$.

Condition (b): CASE 1: Alternating path $\rho$ starts from an unmatched man
$m$: Since $m$ is unmatched in $M$ level of $m$ is 0 due to Condition $4$ of
theorem 2.2. Hence $\rho$ starts with an edge present in $N$. If $\rho$ ends
in a man $m^{\prime}$ then $m^{\prime}$ is unmatched in $N$ and hence
$m^{\prime}$ is a non-critical man and hence is at level 0. Let $j$ be the
highest level of a man $m^{j}$ present in $\rho$. Since $\rho$ starts from an
unmatched man $m$ which is at level 0, hence due to Condition $1$ we get that
the alternating sub path of $\rho$ from $m$ to $m^{j}$ can contain at most $j$
$(+1,+1)$ edges. Again due to conditions $2$ and 3 we get the alternating sub
path of $\rho$ from $m^{j}$ to $m^{\prime}$ must contain $j$ $(-1,-1)$ edges.
Hence $\rho$ has more $(-1,-1)$ edges than $(+1,+1)$ edges. Now, if $\rho$
ends in a woman $w^{\prime}$ then $w^{\prime}$ is unmatched in $M$ and hence
the level of $w^{\prime}$ is 0. So, $\rho$ starts at a level 0 man $m$ and
ends at a level 0 woman $w^{\prime}$. So, arguing similarly as we argued when
$\rho$ ends in $m^{\prime}$ we get that $\rho$ has more $(-1,-1)$ edges than
$(+1,+1)$. CASE $2$: Since $w$ is unmatched in $M$, hence $\rho$ starts with
an edge in $N$. Alternating path $\rho$ starts from an unmatched woman $w$: If
$\rho$ ends in a man $m^{\prime\prime}$ then $m^{\prime\prime}$ is unmatched
in $M$ and hence due to CASE 1 we get that $\rho$ has more $(-1,-1)$ edges
than $(+1,+1)$ edges. When $\rho$ ends in a woman $w^{\prime\prime}$ then
$w^{\prime\prime}$ is at unmatched in $N$. If the level of $w^{\prime\prime}$
is $i$ then due to conditions $2$ and 3 we get that $\rho$ has $i$ more
$(-1,-1)$ edges than $(+1,+1)$ edges. Hence, condition (b) is not satisfied.

Condition (c): Consider an alternating path $\rho$ which starts from a man $m$
matched in $M$ and ends in a woman $w$ matched in $M$. Since $m$ is the
endpoint of $\rho$ we get that $m$ is unmatched in $N$. Hence, $m$ is a non-
critical man and thus is at level 0. Let $w$ is at level $i$ and
$\rho=(m,w_{1},m_{1},w_{2},m_{2},....,w)$. Since, $M(m)=w_{1}$ hence $w_{1}$
is at level 0. Now, from the conditions $2$ and 3 we get that $m_{1}$ is
either at level 0 or at level 1. So, the alternating path $\rho$ can go up by
only one level (that is from a woman at level $i$ to a man at level $i+1$) and
if it goes up then it has to take a $(-1,-1)$ edge. Since $w$ is at level $i$
and $w_{1}$ is at level 0, $\rho$ will have $i$ more $(-1,-1)$ edges than
$(+1,+1)$ because to go from $w_{1}$ to $w$ $\rho$ needs to take $i$ $(-1,-1)$
edges. Hence, condition (c) is not satisfied.

Since none of the above conditions are satisfied, it shows that $M$ is a
popular feasible matching .

$\mathbf{M}$ is a minimum size popular feasible matching: Now we show that for
any feasible matching $N$ such that $|N|<|M|$ we have $\phi(N,M)<\phi(M,N)$.
We take the graph $M\oplus N$, which is the disjoint union of alternating
paths and cycles. There is no alternating path or cycle $\rho$ in $M\oplus N$
such that $\phi((M\oplus\rho),M)>\phi(M,(M\oplus\rho))$ otherwise $M$ is not a
popular feasible matchingṠo, now we need to show an alternating path or cycle
in $M\oplus N$ such that $\phi((M\oplus\rho),M)<\phi(M,(M\oplus\rho))$ then
only we can say $\phi(N,M)<\phi(M,N)$. Now, since $|N|<|M|$ there must exist
an alternating path which starts from a man $m$ unmatched in $N$ and ends in a
woman $w$ unmatched in $N$. Since $m$ is unmatched in $N$ it is a non-critical
man and hence has level 0. Suppose $\rho=(m,w_{1},m_{1},w_{2},m_{2}...,w)$ and
the level of $w$ be $i$. Let $j$ be the highest level of a man present in
$\rho$. Note that the edges $(w_{i},m_{i})$ are all edges present in $N$.
Since $m$ is at level 0, hence $M(m)=w_{1}$ is also at level 0. Now from
Condition $3$ of theorem 2.2 we get that $m_{1}$ can be either at level 0 or
at level 1. Hence, the alternating path $\rho$ can go up by only one level.
Condition $2$ of theorem 2.2 says that all the edges from a woman at level $i$
to a man at level $i+1$ is a $(-1,-1)$ edge. Since the highest level of a man
in $\rho$ is $j$, hence in $\rho$ there must be $j$ $(-1,-1)$ edges. Since
$\rho$ ends in a woman $w$ which is at level $i$, hence there can be at most
$j-i$ $(+1,+1)$ edges as from Condition $1$ of theorem 2.2 we get that
$(+1,+1)$ edges are only present in between a higher level woman and a lower
level man. Since $j\geq(j-i)$, hence the number of $(-1,-1)$ edges is greater
than or equal to the number of $(+1,+1)$ edges in $\rho$. Hence,
$\phi((M\oplus\rho),M)<\phi(M,(M\oplus\rho))$. Note that even if the number of
$(-1,-1)$ edges equal to the number of $(+1,+1)$ edges in $\rho$, we have
$\phi((M\oplus\rho),M)<\phi(M,(M\oplus\rho))$ because $M\oplus\rho$ loses the
votes of $m$ and $w$ (the end vertices) and does not get any extra vote from
the intermediate vertices as the number of $(-1,-1)$ edges equal to the number
of $(+1,+1)$ edges. Hence, $M$ is a minimum size popular feasible matching.

Now we show that any $M$ that is an image of a stable matching $M^{\prime}$ in
$G^{\prime}$ satisfies all the four conditions.

Condition $1$: Suppose there is $(+1,+1)$ edge in between a man $m$ at level
$i$ and woman $w$ at level $j$ such that $j\leq i$ in the matching $M$. Hence
$m$ prefers $w$ more than his matched partner in $M$. Now,
$M^{\prime}(m^{i})=M(m)$ and since the preference list of $m^{i}$ in the
$G^{\prime}$ instance is same as the preference list of $m$ in the marriage
instance with critical men (except the dummy women in the beginning and end of
the preference list of $m^{i}$), $m^{i}$ prefers $w$ more than
$M^{\prime}(m^{i})$. So, in $M^{\prime}$ the edge $(m^{i},w)$ will be a
$(+1,+1)$ edge because $m^{i}$ prefer $w$ more than $M^{\prime}(m^{i})$ and
$w$ prefers $m^{i}$ more than $M^{\prime}(w)$ because her matched partner is
at level $j$ and $j\leq i$. In the $G^{\prime}$ instance $w$ prefers a level
$i$ man more than a level $j$ man if $i>j$ and if $i=j$ then $w$ prefers
$m^{i}$ more than $M^{\prime}(w)$ because $w$ prefers $m$ more than $M(w)$ in
the matching $M$. This contradicts the fact that $M^{\prime}$ is stable
matching. Hence, $M$ satisfies Condition $1$.
Condition $2$: Suppose there is a man $m$ at level $i$ which is adjacent to a
woman at level $(i-1)$ but the edge $(m,w)$ is not labelled $(-1,-1)$. $(m,w)$
cannot be labelled $(+1,+1)$ due to Condition $1$. So, it has to be labelled
$(+1,-1)$ and $(-1,+1)$. CASE 1: If $(m,w)$ is labelled $(+1,-1)$ then $m$
prefers $w$ more than $M(m)$. Hence $m^{i}$ prefers $w$ more than
$M^{\prime}(m^{i})$ and $w$ prefers $m^{i}$ more than its matched partner in
$M^{\prime}$ which is the $(i-1)$ level copy of $M(w)$. Hence the edge
$(m^{i},w)$ is a $(+1,+1)$ edge in the matching $M^{\prime}$. This contradicts
stability of $M^{\prime}$. CASE $2$: Now, if $(m,w)$ is labelled $(-1,+1)$
then $w$ prefers $m$ more than $M(w)$. Now since $m$ is at level $i$ so
$m^{i}$ gets matched to a non dummy woman in the matching $M^{\prime}$. So,
from Corollary LABEL:3.1.2m we get that $m^{i-1}$ is matched to the dummy
woman $d_{m}^{i}$ which is present at the end of his preference list. In this
the edge $(m^{i-1},w)$ would be labelled $(+1,+1)$ because $m^{i-1}$ would
prefer $w$ more than its matched partner in $M^{\prime}$ which is present at
the last of his preference list and $w$ would prefer $m^{i-1}$ more than
$M^{\prime}(w)$, which is a $(i-1)$ level copy of $M(w)$ as $w$ prefers $m$
more than $M(w)$. This again contradicts that $M^{\prime}$ is a stable
matching. Hence $M$ satisfies condition $2$.
Condition $3$: Suppose Condition $3$ is not satisfied, then there is a man
$m$, which at level $i$ is adjacent to a woman $w$ at level $j$ such that
$j\leq(i-2)$. In this case the edge $(m^{i-1},w)$ would be a $(+1,+1)$ edge
because $m^{i-1}$ prefers $w$ over its matched partner in $M^{\prime}$ which
is $d_{m}^{i}$ (Corollary LABEL:3.1.2m) and $w$ prefers $m^{i-1}$ over
$M^{\prime}(w)$ which is a $(i-2)$ level copy of $M(w)$. This contradicts the
fact that $M^{\prime}$ is a stable matching. Hence, $M$ satisfies Condition
$3$.
Condition $4$: Since, $M$ is feasible matching, so the unmatched men are only
the non critical men. They must be at level 0 because there is no other copy
of non critical men in $G^{\prime}$. Hence $M$ satisfies Condition $4$.

Hence any matching $M$ that is an image of a stable matching $M^{\prime}$ in
$G^{\prime}$ is a minimum size popular feasible matching.

###  2.3 Surjectivity of the map

In this section, the goal is to prove the following theorem:

######  Theorem 2.4.

For every minimum size popular feasible matching $M$ in $G$, there exists a
stable matching $M^{\prime}$ in $G^{\prime}$ such that $M$ is the image of
$M^{\prime}$.

To show the surjectivity i.e. the fact that every minimum size popular
feasible matching $M$ in $G$ has a stable matching $M^{\prime}$ in
$G^{\prime}$ as its pre-image, we first assign levels to nodes in $G$ with
respect to $M$. From the assignment of levels to nodes in $G$, the pre-image
$M^{\prime}$ is then immediate. The assignment of levels is described in
Algorithm 1. In the pseudocode for Algorithm 1, we denote the level of a
vertex $v$ by $level(v)$, and the matched partner of $v$ in $M$ as $M(v)$. The
proof of Theorem 2.4 is immediate from the correctness of Algorithm 1, proved
below.

Input: A marriage instance $G$, set of critical nodes $C\subseteq A$, a
minimum size popular feasible matching $M$ in $G$
Output: Assignment of levels to the vertices in $G$ based on the matching $M$.

1:Initially all the men and the women are assigned level $0$

2:flag = true

3:while flag = true do

4: check1 $=0$, check2 $=0$, check3 $=0$

5: while $\exists$ $m\in A,w\in B$ s.t. $level(m)=i$, $level(w)=j$, $j\leq i$,
and $(m,w)$ is a $(+1,+1)$ edge do

6: Set $level(w)=level(M(w))=i+1$ $\triangleright$ Note that $w$ cannot be
unmatched in $M$ because then $M\setminus(m,M(m))\cup(m,w)$ is more popular
than $M$ and hence $M$ would not be a popular feasible matching.

7: check1 $=1$

8: end while

9: while $\exists$ $m\in A,w\in B$, s.t. $level(m)=i$, $level(w)=j$, $j<i$ and
$(m,w)$ is a $(+1,-1)$ or a $(-1,+1)$ edge do

10: Set $level(w)=level(M(w))=i$ $\triangleright$ Note that $w$ cannot be
unmatched in $M$ because then $M$ would not be a popular feasible matching.

11: check2 $=1$

12: end while

13: while $\exists m\in A,w\in B$ s.t. $level(m)=i$, $level(w)=j$,
$j\leq(i-2)$ and $(m,w)$ is a $(-1,-1)$ edge do

14: Set $level(w)=level(M(w))=i-1$ $\triangleright$ Note that $w$ cannot be
unmatched in $M$ because then $M$ would not be a PFM.

15: check3 $=1$

16: end while

17: if check1 $=0$ and check2 $=0$ and check3 $=0$ then

18: flag = false

19: end if

20:end while

Algorithm 1 Leveling Algorithm for minimum size popular feasible matching

In Algorithm 1, the Boolean variables check1, check2 and check3 are used to
check whether the assignment of levels at any point violates one of the
conditions of Theorem 2.2. If not, then we set flag to false and the algorithm
terminates. In Theorem 2.5 below, we show that no level is empty. Since level
of a vertex never reduces during the execution of Algorithm 1, it implies that
the algorithm terminates.

######  Theorem 2.5.

For a man $m$ at level $i$ there exists $(i)$ either a woman $w$ at each level
$j$, where $j<i$, or $(ii)$ an unmatched man $m_{0}$, if $j=0$ such that there
is an alternating path from $w$ to $m$ or from $m_{0}$ to $m$ which consists
of $(i-j)$ more $(+1,+1)$ edges than $(-1,-1)$ edges.

First we show that the image $M$ of a stable matching $M^{\prime}$ in
$G^{\prime}$ is a matching in $G$. We use the following observation: Every
dummy woman is matched in any stable matching of $G^{\prime}$. This is because
each dummy woman $d_{m}^{j}$ is the first choice of $m^{j}$. So if $d_{m}^{j}$
is unmatched in a matching $N^{\prime}$ of $G^{\prime}$, then
$(d_{m}^{j},m^{j})$ forms a $(+1,+1)$ edge, contradicting the stability of
$N^{\prime}$.

######  Lemma 2.6.

In any stable matching $M^{\prime}$ in $G^{\prime}$, at most one copy of any
$m\in A$ gets matched to a non-dummy woman.

######  Proof 2.7.

Suppose $m^{i}$ be the copy of the man $m\in A$ which gets matched to a non-
dummy woman. Then by the observation above, and by the fact that a dummy woman
$d_{m}^{j}$ has only $m^{j-1}$ and $m^{j}$ in her preference list,
$d_{m}^{i+1}$ must be matched to $m^{i+1}$, and inductively, each $d_{m}^{j}$,
$j>i$ must be matched to $m^{j}$.

Lemma 2.6 shows that $M$ is a matching in $G$.

######  Proof 2.8 (Proof of Theorem 2.5).

We prove the statement using induction on the number of iterations of the
outer while loop (line $3$). We refer to the three inner while loops i.e.
Steps $5$ to $7$, Steps $8$ to $10$, and Steps $11$ to $13$ as Phase 1, Phase
$2$, and Phase 3 of an iteration of the outer while loop respectively. In the
remainder of the proof, iteration always refers to an iteration of the outer
while loop, unless stated otherwise.

Base case:

  1. 1.

The statement holds after Phase 1 of the $1$st iteration:

In the Phase 1 of the first iteration, a man $m_{i}$ is assigned level $i$
only when its matched partner $M(m_{i})=w_{i}$ has a $(+1,+1)$ edge to a man
$m_{i-1}$ at level $(i-1)$. Again $m_{i-1}$ is at level $(i-1)$ after Phase 1
of the $1$st iteration because his matched partner $M(m_{i-1})=w_{i-1}$ has a
$(+1,+1)$ edge to a man $m_{i-2}$ at level $(i-2)$. Continuing this way, we
get an alternating path from $m_{i}$ either to a woman $w_{j}$ at level $j$,
where $j<i$, which has $(i-j)$ more $(+1,+1)$ edges than $(-1,-1)$ edges or to
an unmatched man $m_{0}$ at level $0$ which has $i$ more $(+1,+1)$ than
$(-1,-1)$ edges. Hence, the statement holds after Phase 1 of the $1$st
iteration.

  2. 2.

The statement holds after Phase $2$ of the $1$st iteration: A man $m$ gets
promoted to a level $i$ in Phase $2$ from a level $j$ where $j<i$ because his
matched partner $M(m)=w$ has a $(+1,-1)$ or a $(-1,+1)$ edge to a man $m_{i}$
at level $i$. Let $m$ be the first man among all the men who got promoted in
Phase $2$. So, $m_{i}$ got promoted to level $i$ in Phase 1 and thus it has an
alternating path from a woman $w_{j}$ at level $j$, where $j<i$, or to a
unmatched man $m_{0}$ at level $j=0$.

Note that $w_{j}\neq w$ because, in that case, the alternating path from
$w_{j}$ to $m_{i}$ concatenated with the $(+1,-1)$ or $(-1,+1)$ edge
$(m_{i},w)$ forms an alternating cycle $\rho$ with $(i-j)$ more $(+1,+1)$
edges than $(-1,-1)$ edges, and thus $M\oplus\rho$ would become a more popular
feasible matching than $M$. Now, this alternating path from $w_{j}$ to $m_{i}$
or from $m_{0}$ to $m_{i}$ concatenated with the path $(m_{i},w,m)$ forms an
alternating path from $w_{j}$ to $m$ or from $m_{0}$ to $m$ which has $(i-j)$
more $(+1,+1)$ edges than $(-1,-1)$ edges. Hence, there exists an alternating
path from $w_{j}$ or from $m_{0}$ at level $j$ or at level $0$ respectively to
the man $m$ at level $i$ with $(i-j)$ more $(+1,+1)$ edges than $(-1,-1)$
edges. Now, if $m$ is not the first man to get promoted to level $i$ during
Phase $2$ then it might happen that $m$ gets promoted to level $i$ because his
matched partner $M(m)=w$ has a $(+1,-1)$ edge or a $(-1,+1)$ to a man
$m^{\prime}$ at level $i$ who got promoted to level $i$ before $m$ during
Phase $2$. In this case too there is an alternating path from a woman $w_{j}$
at level $j$ or from unmatched man $m_{0}$ at level $0$ to $m^{\prime}$ which
has $(i-j)$ more $(+1,+1)$ edges than $(-1,-1)$ edges (note here also
$w_{j}\neq w$ due to the same reason). This alternating path concatenated with
the path $(m^{\prime},w,m)$ will give an alternating path from a woman $w_{j}$
at level $j$ or from $m_{0}$ at level $j=0$ to $m$ which has $(i-j)$ more
$(+1,+1)$ edges than $(-1,-1)$ edges. Hence, there exists an alternating path
from $w_{j}$ at level $j$ or from $m_{0}$ at level $0$ to the man $m$ at level
$i$ with $(i-j)$ more $(+1,+1)$ edges than $(-1,-1)$ edges. Hence, S is true
after the Phase $2$ of the 1st iteration.

  3. 3.

The statement is true after Phase 3 of the 1st iteration:  A man $m$ gets
promoted to level $i$ in Phase 3 from level $j$ where $j<i$ because his
matched partner $M(m)=w$ has a $(-1,-1)$ edge to a man $m_{i+1}$ at level
$(i+1)$. Let $m$ be the first man among all the men who got promotions in
Phase 3. So, $m_{i+1}$ got promoted to level $i$ either in Phase 1 or in Phase
$2$ and thus it has an alternating path from a woman $w_{j}$ at level $j$
where $j<i$ or from an unmatched man $m_{0}$ at level $0$ which has $i+1-j$
more $(+1,+1)$ edges than $(-1,-1)$ edges. Note that $w_{j}\neq w$ because in
that case the alternating path from $w_{j}$ to $m_{i+1}$ concatenated with the
$(-1,-1)$ edge $(m_{i+1},w)$ forms an alternating cycle $\rho$ with $(i-j)$
more $(+1,+1)$ edges than $(-1,-1)$ edges and thus $M\oplus\rho$ would become
a more popular feasible matching than $M$. Now, this alternating path from
$w_{j}$ to $m_{i+1}$ or from $m_{0}$ to $m_{i+1}$ concatenated with the path
$(m_{i+1},w,m)$ forms an alternating path from $w_{j}$ to $m$ or from $m_{0}$
to $m$ which has $(i-j)$ more $(+1,+1)$ edges than $(-1,-1)$ edges because the
edge $(m_{i+1},w)$ is a $(-1,-1)$ edge. Hence, there exists an alternating
path from $w_{j}$ at level $j$ or from an unmatched man $m_{0}$ at level $j=0$
to the man $m$ at level $i$ with $(i-j)$ more $(+1,+1)$ edges than $(-1,-1)$
edges. Now, if $m$ is not the first man to get promoted to level $i$ during
Phase 3 then it might happen that $m$ gets promoted to level $i$ because his
matched partner $M(m)=w$ has a $(-1,-1)$ edge to a man $m^{\prime}$ at level
$(i+1)$ who got promoted to level $(i+1)$ before $m$ during Phase 3. In this
case too there is an alternating path from a woman $w_{j}$ at level $j,j<i$ or
from an unmatched man $m_{0}$ at level $0$ to $m^{\prime}$ which has $(i+1-j)$
more $(+1,+1)$ edges than $(-1,-1)$ edges (note that $(w_{j}\neq w)$ due to
same reason) . This alternating path concatenated with the path
$(m^{\prime},w,m)$ will give an alternating path from a woman $w_{j}$ at level
$j,j<i$ or from an unmatched man $m_{0}$ at level $j=0$ to $m$ which has
$(i-j)$ more $(+1,+1)$ edges than $(-1,-1)$ edges because the edge
$(m^{\prime},w)$ is a $(-1,-1)$ edge. Hence, there exists an alternating path
from $w_{j}$ at level $j$ to the man $m$ at level $i$ with $(i-j)$ more
$(+1,+1)$ edges than $(-1,-1)$ edges. Hence, S is true after the Phase 3 of
the 1st iteration.

Now, since the statement holds after all the three Phases of the first
iteration, it holds at the end of the first iteration.

Inductive step: Suppose the theorem statement is true after the $j^{th}$
iteration for all $j\leq k$. We prove below that it holds after the
$(k+1)^{th}$ iteration.

The statement holds after Phase 1 of the $(k+1)^{th}$ iteration: Now, in the
phase 1 of the $(k+1)^{th}$ iteration, a man $m_{i}$ is assigned level $i$
only when its matched partner $M(m_{i})=w_{i}$ has a $(+1,+1)$ edge to a man
$m^{i-1}$ at level $(i-1)$. Now, suppose $m_{i}$ be the first man who gets a
promotion during Phase 1 of the $(k+1)^{th}$ iteration. So $m^{i-1}$ gets
promoted to level $(i-1)$ in the previous iterations. Hence, due to inductive
hypothesis we get that there exists a woman $w_{j}$ at level $j$ where $j<i$
or from an unmatched man $m_{0}$ at level $j=0$ such that there is an
alternating path from $w_{j}$ or from $m_{0}$ to $m^{i-1}$ with $(i-1-j)$ more
$(+1,+1)$ edges than $(-1,-1)$ edges. Now, concatenating this path with
$(m^{i-1},w_{i},m_{i})$ we get that there is an alternating path either from
$w_{j}$ or from $m_{0}$ to $m_{i}$ with $(i-j)$ more $(+1,+1)$ edges than
$(-1,-1)$ edges. Now, if $m_{i}$ is not the first man who gets a promotion
during Phase 1 of the $(k+1)^{th}$ iteration then it might happen that
$m^{i-1}$ gets promoted to level $(i-1)$ before $m_{i}$ during Phase 1 of
$(k+1)^{th}$ iteration. In this case also there exists a woman $w_{j}$ at
level $j$ where $j<i$ or an unmatched man $m_{0}$ at level $j=0$ such that
there is an alternating path either from $w_{j}$ or from $m_{0}$ to $m^{i-1}$
with $(i-1-j)$ more $(+1,+1)$ edges than $(-1,-1)$ edges. Now, concatenating
this path with $(m^{i-1},w_{i},m_{i})$ we get that there is an alternating
path either from $w_{j}$ or from $m_{0}$ to $m_{i}$ with $(i-j)$ more
$(+1,+1)$ edges than $(-1,-1)$ edges. Hence, S is true after Phase 1 of the
$(k+1)^{th}$ iteration.

For the remaining two phases, the proof is similar to the respective proofs of
the 1st iteration. This completes the proof of the theorem.

######  Theorem 2.9.

The matching $M^{\prime}$ is a stable matching in $G^{\prime}$.

######  Proof 2.10.

Suppose $M^{\prime}$ is not a stable matching. Then there exists a pair
$(a,b)$ such that $(a,b)$ is a $(+1,+1)$ edge where $a\in A^{\prime}$ and
$b\in B^{\prime}$.

Case 1: The woman $b$ is a dummy woman: Let $b=d_{m}^{i}$. Now, the only two
neighbors of $d_{m}^{i}$ are $m^{i}$ and $m^{i-1}$. If
$M^{\prime}(d_{m}^{i})=m^{i-1}$ then $(m^{i},d_{m}^{i})$ cannot be a $(+1,+1)$
edge because $d_{m}^{i}$ prefers $m^{i-1}$ the most. If
$M^{\prime}(d_{m}^{i})=m^{i}$ then $(m^{i-1},d_{m}^{i})$ cannot be a $(+1,+1)$
edge because $m^{i-1}$ prefers $d_{m}^{i}$ the least and by our mapping of $M$
to $M^{\prime}$, $M^{\prime}(m^{i-1})$ is either $d_{m}^{i+1}$ or a non-dummy
woman. So a dummy woman cannot participate in a blocking pair with respect to
$M^{\prime}$.

Case $2$: The woman $b$ is a non-dummy woman: Let $M^{\prime}(b)=m^{i}$ By the
execution of Algorithm 1, $b$ does not have an edge to a man at level $i+2$ or
higher. So the man $a$ cannot be at level $i+2$ or higher. Moreover, $a$
cannot be at a level $j<i$ since, in $G^{\prime}$, $b$ prefers any man at
level $i$ over any man at a level $j<i$. If $a$ is at level $i$, then the edge
$(a,b)$ is also a $(+1,+1)$ edge with respect to $M$ in $G$. But then
Algorithm 1 would have moved $b$ to a higher level. So $a$ cannot be at level
$i$. If $a$ is at level $i+1$, then the edge $(a,b)$ is a $(-1,-1)$ edge in
$G$ by the execution of Algorithm 1. Since $a$ has the same preference list
except possibly for the addition of dummy women, $a$ does not prefer $b$ over
$M(a)$ and hence over $M^{\prime}(a)$. So $(a,b)$ cannot be a blocking pair
with respect to $M^{\prime}$.

Since no woman can participate in a blocking pair with respect to
$M^{\prime}$, stability of $M^{\prime}$ follows.

The following corollary is a straight forward consequence of Theorem 2.5 and
the fact that $M$ is a minimum size popular feasible matching.

######  Corollary 2.11.

All non-critical men are assigned level zero and the critical men are assigned
level less than or equal to $|C|$ by Algorithm 1.

######  Proof 2.12.

Suppose there is a non-critical man $m_{i}$ at level $i,i>0$. Now, from
Theorem 2.5, there is an alternating path, say $\rho$, from a woman $w_{0}$ at
level $0$ or from an unmatched man $m_{0}$ to $m_{i}$ which has $i$ more
$(+1,+1)$ edges than $(-1,-1)$ edges. Let $N=M\oplus\rho$. Observe that
Algorithm 1 assigns level $0$ to all the unmatched men in $M$, so $m_{i}$ is
matched. Now, it is easy to see that $N$ is also a popular feasible matching.
But $|N|<|M|$, so this contradicts the assumption that $M$ is a minimum size
popular feasible matching. After assigning levels to the vertices in $G$, the
pre-image of $M$ i.e. a stable matching $M^{\prime}$ in $G^{\prime}$ is
constructed as follows. If a man $m$ in $G$ gets assigned level $i$ then
$M^{\prime}(m_{i})=M(m)$. If $m$ is unmatched in $M$, then $m\notin C$ by
feasibility of $M$, and $m$ gets level $0$ by Corollary 2.11. Then we leave
$m$ unmatched in $M^{\prime}$ as well. For $j<i$, $m^{j}$ gets matched to the
dummy woman $d_{m}^{j+1}$ and for $j>i$, $m^{j}$ gets matched to the dummy
woman $d_{m}^{j}$.

The reduction and proofs for dominant feasible matching are similar, and are
given in Appendix for the sake of completeness.

##  3 The Popular Edge Algorithm

Now we are ready to prove Theorem 1.5, from which, the popular edge algorithm
is as follows. For a given edge $e=(m,w)$, we construct
$G^{\prime},G^{\prime\prime}$ using reductions from Section 2 and check if any
of the edges $(m^{i},w)$ in $G^{\prime}$ or $G^{\prime\prime}$ belong to a
stable matching in the respective instance using Knuth’s algorithm for stable
edges [21].

If there is a minimum size popular feasible matching or a dominant feasible
matching containing $e$ then there is nothing to prove. So we need to prove
the theorem for an edge $e$ that is contained in a popular feasible matching
$M$ that is neither a minimum size popular feasible matching nor a dominant
feasible matching, and show that there is also a minimum size popular feasible
matching or a dominant feasible matching containing $e$. The proof of Theorem
1.5 involves the following two results:

######  Theorem 3.1.

If $M$ is neither a minimum size popular feasible matching or a dominant
feasible matching, then $A\cup B$ can be partitioned into three parts
$A_{d}\cup B_{d}$, $A_{m}\cup B_{m}$ and $A_{r}\cup B_{r}$ such that no edge
of $M$ is present in $A_{i}\times B_{j}$, $i\neq j,$ where
$i,j\in\\{d,m,r\\}$.

We prove Theorem 3.1 in Section 3.1. Because of Theorem 3.1, it follows that
the partition of $A\cup B$ also induces a partition of $M$ into three parts,
say $M_{d},M_{m},M_{r}$ respectively. The following theorem shows that either
$M_{d}$ or $M_{m}$ can be transformed into another matching so that the
resulting matching is a minimum size popular feasible matching or a dominant
feasible matching in $G$.

######  Theorem 3.2.

There exist algorithms to transform:

  1. 1.

the matching $M_{d}$ to another matching $M^{\prime}_{m}$ in $A_{d}\cup B_{d}$
such that $M^{*}_{m}=M^{\prime}_{m}\dot{\cup}M_{m}\dot{\cup}M_{r}$ is a
minimum size popular feasible matching in $G$

  2. 2.

the matching $M_{m}$ to another matching $M^{\prime}_{d}$ in $A_{m}\cup B_{m}$
such that $M^{*}_{d}=M_{d}\dot{\cup}M^{\prime}_{d}\dot{\cup}M_{r}$ is a
dominant feasible matching in $G$.

A proof of Theorem 3.2 is given in Section 3.3. From Theorems 3.1 and 3.2,
Theorem 1.5 follows:

######  Proof 3.3 (Proof of Theorem 1.5).

Depending on the part that contains the given edge $e$, one of the two
transformations mentioned in Theorem 3.2 can be applied: If $e\in M_{m}$
(respectively $e\in M_{d}$), apply the first (respectively, second)
transformation from Theorem 3.2 i.e. convert the matching $M_{d}$ to
$M^{\prime}_{m}$ ($M_{m}$ to $M^{\prime}_{d}$). Then, by Theorem 3.2, the
resulting matching $M^{*}_{m}$ ($M^{*}_{d}$) is a minimum size popular
feasible matching (dominant feasible matching) in $G$ containing $e$. If $e\in
M_{r}$, we can apply any one of the two transformations mentioned in Theorem
3.2. Thus, in all the three cases, we get a minimum size popular feasible
matching or a dominant feasible matching containing $e$. This completes the
proof of Theorem 1.5.

###  3.1 Partition Method

We prove Theorem 3.1 now. For partitioning $A\cup B$ and $M$, we first assign
levels to the vertices of $A\cup B$ using Algorithm 1 described in Section
2.1. We refer to the level of a vertex $u\in A\cup B$ as $level(u)$. Since $M$
is a popular feasible matching but not a minimum size popular feasible
matching by assumption, all the non-critical men may not be at level $0$.
However, the following holds:

######  Lemma 3.4.

After applying Algorithm 1 on a popular feasible matching $M$ all non-critical
men are assigned levels $0$ or $1$.

######  Proof 3.5.

If there is a non-critical man $m$ who is assigned level $i\geq 2$, then
according to Theorem 2.5 there exists a woman at level $0$ such that $m$ has
an alternating path $\rho$ from $w$ with $i$ more $(+1,+1)$ edges than
$(-1,-1)$ edges. Since $i\geq 2$, the matching $M\oplus\rho$ is feasible and
is more popular than $M$, contradicting the assumption that $M$ is a popular
feasible matching . Hence, all non-critical men are assigned levels $0$ or
$1$.

The following notions will be used in the partitioning procedure.

######  Definition 3.6 (Size Reducing Alternating Path (SRAP)).

: An alternating path $\rho$ with respect to a matching $M$ is called as SRAP
if the following conditions are satisfied:

  1. 1.

The number of $(+1,+1)$ edges in $\rho$ is one more than the number of
$(-1,-1)$ edges in $\rho$,

  2. 2.

It starts in a matched woman at level $0$.

  3. 3.

It ends in a non-critical man at level $1$.

######  Definition 3.7 (Size Increasing Alternating Path (SIAP)).

: An alternating path $\rho$ with respect to a matching $M$ is called an SIAP
if the following conditions are satisfied.

  1. 1.

There are an equal number of $(+1,+1)$ and $(-1,-1)$ edges in $\rho$.

  2. 2.

Its end-points are an unmatched man and an unmatched woman.

Intuitively, if $\rho$ is an SIAP (respectively an SRAP), then $M\oplus\rho$
gives a larger (respectively, smaller) popular feasible matching. Theorem 3.8
below shows that an SRAP and an SIAP must exist if $M$ is not a minimum size
popular feasible matching or a dominant feasible matching.

######  Theorem 3.8.

If a popular feasible matching $M$ is neither a minimum size popular feasible
matching nor a dominant feasible matching, then $G$ must contain an SRAP and
an SIAP with respect to $M$.

######  Proof 3.9.

Suppose $M_{min}$ is a minimum size popular feasible matching. Consider
$M\oplus M_{min}$ which is a disjoint union of alternating paths and cycles.
Since $|M_{min}|<|M|$, there exists an alternating path $\rho$ in $M\oplus
M_{min}$ whose both end-points are matched in $M$. By popularity of $M$ and
$M_{min}$, $\rho$ must have one more $(+1,+1)$ edge than $(-1,-1)$ edges so
that $\phi(M\oplus\rho,M)=\phi(M,M\oplus\rho)$. By feasibility of $M_{min}$,
$\rho$ must have a non-critical man $m$ as one of its end-points, since $m$ is
unmatched in $M_{min}$. The level assigned to $m$ has to be $1$ because non-
critical men can only be assigned levels $0$ or $1$ by Lemma 3.4. Moreover,
since $\rho$ has $1$ more $(+1,+1)$ edge than $(-1,-1)$ edges,the level
assigned to the other end-point $w$ is $0$. Recall that $w$ is matched in $M$
and unmatched in $M_{min}$. Hence $\rho$ is an SRAP.

Now suppose $M_{d}$ is a dominant feasible matching in $G$. The graph $M\oplus
M_{d}$ is a disjoint union of alternating paths and cycles. Since
$|M|<|M_{d}|$, there must exist an alternating path $\rho$ in $M\oplus M_{d}$
whose end-points are unmatched in $M$ and matched in $M_{d}$. Here, $\rho$
must have an equal number of $(+1,+1)$ and $(-1,-1)$ edges, otherwise
$(M\oplus\rho)$ becomes a more popular matching than $M$. Hence $M$ has an
SIAP.

The partitioning is based on SIAP and SRAP, so the following theorem is
essential for the partitioning to be well-defined. Theorem 3.10 below shows
that no vertex belongs to both an SRAP and an SIAP:

######  Theorem 3.10.

Given a popular feasible matching $M$, no vertex in $G$ belongs to both an
SIAP and an SRAP.

######  Proof 3.11.

Note that if a man $m$ belongs to both an SIAP $\rho$ and an SRAP $\sigma$,
then his matched partner $M(m)$ must belong to both $\rho$ and $\sigma$ too.
Also note that no man or woman unmatched in $M$ can belong to both $\rho$ and
$\sigma$ because all the men and women in an SRAP are matched in $M$. Suppose
a matched pair $(m,w)$ in $M$ belongs to both $\rho$ and $\sigma$. Let $m_{I}$
and $w_{I}$ be the end-points of $\rho$ and $m_{R}$ and $w_{R}$ be the end-
points of $\sigma$. Let the level assigned to the pair $(m,w)$ be $i_{(m,w)}$.
Since $m_{I}$ and $w_{I}$ are unmatched in $M$, both of them are assigned
level $0$. Now, the alternating subpath $\rho_{I}$ of $\rho$ from $w_{I}$ to
$m$ must contain $i_{(m,w)}$ more $(-1,-1)$ edges than $(+1,+1)$ edges. This
is because all the adjacent vertices of the women present in level $i$ must be
present at a level $j$ where $j\leq(i+1)$. So, $\rho_{I}$ can go up by only
one level that is from a level $i$ woman it can only go to a level $i+1$ man
and, from the properties of Algorithm 1, we also know that all the edges
between level $i$ women and level $(i+1)$ men are $(-1,-1)$ edges. Now, since
an SIAP has an equal number of $(+1,+1)$ and $(-1,-1)$ edges, we have that the
alternating subpath $\rho_{I^{\prime}}$ of $\rho$ from $m_{I}$ to $m$ must
contain $i_{(m,w)}$ more $(+1,+1)$ edges than $(-1,-1)$ edges.

By a similar argument, the alternating subpath $\sigma_{R}$ of $\sigma$
starting from $m$ to $m_{R}$ consists of $(i_{(m,w)}-1)$ more $(-1,-1)$ edges
than $(+1,+1)$ edges. Thus the path $\beta=\rho_{I^{\prime}}\circ\sigma_{R}$,
where $\circ$ denotes concatenation, contains more $(+1,+1)$ edges than
$(-1,-1)$ edges.This is because $\rho_{I^{\prime}}$ contains $i_{(m,w)}$ more
$(+1,+1)$ edges than $(-1,-1)$ edges, and then $\rho_{R}$ has $(i_{(m,w)}-1)$
more $(-1,-1)$ edges than $(+1,+1)$ edges. The matching $M\oplus\beta$ is more
popular than $M$ because $\beta$ has one more $(+1,+1)$ edge than the number
of $(-1,-1)$ edges, and $M\oplus\beta$ has the same size as that of $M$. This
contradicts the fact that $M$ is a popular feasible matching. Hence, no vertex
in $G$ can belong to both an SIAP and an SRAP for a given matching $M$.

Now we give the method to partition $A\cup B$ below, as required by Theorem
3.1.

####  3.1.1 Partitioning $A\cup B$

  1. (a)

Initialize $A_{d}$, $A_{m}$, $A_{r}$, $B_{d}$, $B_{m}$, $B_{r}$ to empty sets.

  2. (b)

For all unmatched men $(m_{u})$ and unmatched women $(w_{u})$ in $M$ we do:
$A_{m}=A_{m}\cup\\{m_{u}\\}$ and $B_{m}=B_{m}\cup\\{w_{u}\\}$

  3. (c)

From Theorem 3.8, we know that $M$ must have an SRAP and an SIAP. For all men
$m_{d}$ and women $w_{d}$ in each SRAP do: $A_{d}=A_{d}\cup\\{m_{d}\\}$ and
$B_{d}=B_{d}\cup\\{w_{d}\\}$

  4. (d)

For all men $m$ and women $w$ in each SIAP do: $A_{m}=A_{m}\cup\\{m\\}$ and
$B_{m}=B_{m}\cup\\{w\\}$

  5. (e)

While there exists a $(+1,+1$) edge $(m,w)$ such that $m\in
A\backslash(A_{d}\cup A_{m})$, $level(m)=i$, $level(w)=j$, $j\leq i+1$ do:
$A_{d}=A_{d}\cup\\{m\\}$ and $B_{d}=B_{d}\cup\\{M(m)\\}$

  6. (f)

While there exists a $(+1,+1)$ edge $(m,w)$ such that $m\in A_{m}$,
$level(m)=i$, $w\in B\backslash(B_{d}\cup B_{m})$, $level(w)=j$, $j\leq i+1$,
do: $B_{m}=B_{m}\cup\\{w\\}$ and $A_{m}=A_{m}\cup\\{M(w)\\}$

  7. (g)

$A_{r}=A\backslash(A_{d}\cup A_{m})$ and $B_{r}=B\backslash(B_{d}\cup B_{m})$.
Let $M_{d},M_{m},M_{r}$ be the parts of $M$ present in the induced subgraph on
$A_{d}\cup B_{d}$, $A_{m}\cup B_{m}$, and $A_{r}\cup B_{r}$ respectively.

To complete the proof of Theorem 3.1, we need to show that the above procedure
partitions $A\cup B$ i.e., the three sets $A_{d}\cup B_{d},A_{m}\cup
B_{m},A_{r}\cup B_{r}$ are disjoint. The partition procedure always puts a
vertex and its matched partner in the same partition. So it is immediate that
$M_{d},M_{m},M_{r}$ partition $M$.

In the discussion below, we retain the same assignment of levels to all the
vertices as was done before partitioning.

We show that the sets $A_{d}$ and $A_{m}$ are disjoint. This implies that
$B_{d}$ and $B_{m}$ are disjoint as well, since they consist of matched
partners of the men in $A_{d}$ and $A_{m}$ respectively. From Theorem 3.10, a
man $m$ cannot be a part of both an SIAP and an SRAP, and thus $m$ cannot be
added in both $A_{d}$ and $A_{m}$ in the steps c and d. Hence, $A_{d}$ and
$A_{m}$ remain disjoint in these steps. We need to show that the three sets
remain disjoint in steps e, and f. In the following, we show that an analogue
of Theorem 2.5 holds for the induced graphs on $A_{d}\cup B_{d}$ and
$A_{m}\cup B_{m}$.

######  Lemma 3.12.

For a man $m\in A_{m}$ at level $i$, there is an alternating path with $i$
more $(+1,+1)$ edges than $(-1,-1)$ edges which starts at $m_{I}$ and ends in
$m$ where $m_{I}$ is an unmatched man and also an endpoint of an SIAP with
respect to $M$. Analogously, for a woman $w\in B_{d}$ at level $i$ there is an
alternating path with $(i-1)$ more $(-1,-1)$ edges than $(+1,+1)$ edges which
starts at $m_{R}$ and ends in $w$ where $m_{R}$ is a non-critical man and also
an endpoint of an SRAP with respect to $M$.

######  Proof 3.13.

A man $m_{m}$ is added in $A_{m}$ either in step (d) or in step (f) of the
Partition Method. If $m_{m}$ is added in step (d) then $m_{m}$ is a part of a
SIAP $\rho$. Let the level assigned to $m_{m}$ is $i$. Let $m_{I}$ and $w_{I}$
be the endpoints of $\rho$. Hence, $m_{I}$ and $w_{I}$ are unmatched in $M$
and thus the levels of $m_{I}$ and $w_{I}$ are 0. Now, a woman at level $i$ is
adjacent to a man at level $j$ where $j\leq(i+1)$. Let $\rho^{\prime}$ be the
alternating subpath of $\rho$ which starts from $w_{I}$ and ends in $m_{m}$.
So $\rho^{\prime}$ can go up by only one level that is $\rho^{\prime}$ can
traverse from a woman at level $i$ to a man at level $(i+1)$. We know that a
edge from a woman at level $i$ to a man at level $(i+1)$ is a $(-1,-1)$ edge.
Hence, the alternating subpath $\rho^{\prime}$ of $\rho$ which starts from
$w_{I}$ and ends in $m_{m}$ consists of $i$ more $(-1,-1)$ edges than
$(+1,+1)$ edges. Now, since $\rho$ consists of equal number of $(+1,+1)$ and
$(-1,-1)$ edges so the alternating subpath $\rho^{\prime\prime}$ of $\rho$
starting from $m_{I}$ to $m_{m}$ consists of $i$ more $(+1,+1)$ edges than
$(-1,-1)$ edges.

Let, $m_{1}$ is the first man who is added in $A_{m}$ in step (f). Then
$m_{1}$ is added to $A_{m}$ because his matched partner $M(m_{1})=w_{1}$ is
adjacent to $m_{m}$ which is added to $A_{m}$ in step (d). Let the level of
$m_{m}$ is $i$. Hence, from the arguments given in the previous paragraph we
get that there is an alternating path from $m_{I}$ to $m_{m}$ which has $i$
more $(+1,+1)$ edges than $(-1,-1)$ edges. Now, if the level of $m_{1}$ and
$w_{1}$ is $i$ then the edge $(m_{m},w_{1})$ is either a $(+1,-1)$ or a
$(-1,+1)$ edge. Hence, the alternating path from $m_{I}$ to $m_{m}$
concatenated with the path $(m_{m},w_{1},m_{1})$ is the alternating path from
$m_{I}$ to $m_{1}$ which has $i$ more $(+1,+1)$ edges than $(-1,-1)$ edges, if
the level of $m_{1}$ and $w_{1}$ is $(i-1)$ then the edge $(m_{m},w_{1})$ is a
$(-1,-1)$ edge. Hence, the alternating path from $m_{I}$ to $m_{m}$
concatenated with the path $(m_{m},w_{1},m_{1})$ is the alternating path from
$m_{I}$ to $m_{1}$ which has $(i-1)$ more $(+1,+1)$ edges than $(-1,-1)$ edges
and if the level of $m_{1}$ and $w_{1}$ is $(i+1)$ then the edge
$(m_{m},w_{1})$ is a $(+1,+1)$ edge. Hence, the alternating path from $m_{I}$
to $m_{m}$ concatenated with the path $(m_{m},w_{1},m_{1})$ is the alternating
path from $m_{I}$ to $m_{1}$ which has $(i+1)$ more $(+1,+1)$ edges than
$(-1,-1)$ edges.

Now if $m_{k}$ be the $k^{th}$ man added to $A_{m}$ in step (f) (where $k\geq
1$) and for all $j\leq k$ we assume that if the level of $m_{j}$ is $i$ then
there exists an alternating path from $m_{I}$ to $m_{j}$ which has $i$ more
$(+1,+1)$ edges than $(-1,-1)$ edges. Now if $m_{k+1}$ is the $(k+1)^{th}$ man
who is added in $A_{m}$ in step (f). Then $m_{k+1}$ is added to $A_{m}$
because his matched partner $M(m_{k+1})=w_{k+1}$ is adjacent to $m_{m}$ which
is added to $A_{m}$ in step (d) or in step (f). Let the level of $m_{m}$ is
$i$. Hence, we get that there is an alternating path from $m_{I}$ to $m_{m}$
which has $i$ more $(+1,+1)$ edges than $(-1,-1)$ edges. Now, if the level of
$m_{k+1}$ and $w_{k+1}$ is $i$ then the edge $(m_{m},w_{k+1})$ is either a
$(+1,-1)$ or a $(-1,+1)$ edge. Hence, the alternating path from $m_{I}$ to
$m_{m}$ concatenated with the path $(m_{m},w_{k+1},m_{k+1})$ is the
alternating path from $m_{I}$ to $m_{k+1}$ which has $i$ more $(+1,+1)$ edges
than $(-1,-1)$ edges, if the level of $m_{k+1}$ and $w_{k+1}$ is $(i-1)$ then
the edge $(m_{m},w_{k+1})$ is a $(-1,-1)$ edge. Hence, the alternating path
from $m_{I}$ to $m_{m}$ concatenated with the path $(m_{m},w_{k+1},m_{k+1})$
is the alternating path from $m_{I}$ to $m_{k+1}$ which has $(i-1)$ more
$(+1,+1)$ edges than $(-1,-1)$ edges and if the level of $m_{k+1}$ and
$w_{k+1}$ is $(i+1)$ then the edge $(m_{m},w_{k+1})$ is a $(+1,+1)$ edge.
Hence, the alternating path from $m_{I}$ to $m_{m}$ concatenated with the path
$(m_{m},w_{k+1},m_{k+1})$ is the alternating path from $m_{I}$ to $m_{k+1}$
which has $(i+1)$ more $(+1,+1)$ edges than $(-1,-1)$ edges.

Hence, for a man $m\in A_{m}$ which is at level $i$ there is an alternating
path with $i$ more $(+1,+1)$ edges than $(-1,-1)$ edges which starts at
$m_{I}$ and ends in $m$ where $m_{I}$ is an unmatched man and also an endpoint
of a SIAP in the PFM $M$.

Now we prove the statement for a woman $w_{d}\in B_{d}$. A woman $w_{d}$ is
added in $B_{d}$ either in step (c) or in step (e) of the Partition Method. If
$w_{d}$ is added in step (c) then $w_{d}$ is a part of a SRAP $\rho$. Let the
level assigned to $w_{d}$ is $i$. Let $m_{R}$ and $w_{R}$ be the endpoints of
$\rho$. Hence, $m_{R}$ is a non-critical man and $w_{R}$ is a woman matched in
$M$ and the levels of $m_{R}$ and $w_{R}$ are 1 and 0 respectively (according
to the definition of SRAP). Now, a woman at level $i$ is adjacent to a man at
level $j$ where $j\leq(i+1)$. Let $\rho^{\prime}$ be the alternating subpath
of $\rho$ which starts with the matched edge $(m_{R},M(m^{R})$ and ends in
$w_{d}$. So $\rho^{\prime}$ can go up by only one level that is
$\rho^{\prime}$ can traverse from a woman at level $i$ to a man at level
$(i+1)$. We know that a edge from a woman at level $i$ to a man at level
$(i+1)$ is a $(-1,-1)$ edge. Hence, the alternating subpath $\rho^{\prime}$ of
$\rho$ which starts from $m_{R}$ and ends in $w_{d}$ consists of $(i-1)$ more
$(-1,-1)$ edges than $(+1,+1)$ edges because $m^{R}$ is at level 1 and $w_{d}$
is at $i$.

Let, $w_{1}$ is the first woman who is added in $B_{d}$ in step (e). Then
$w_{1}$ is added to $B_{d}$ because her matched partner $M(w_{1})=m_{1}$ is
adjacent to $w_{d}$ which is added to $B_{d}$ in step (c). Let the level of
$m_{1}$ is $i$. Now, if the level of $w_{d}$ is $i$ then there is an
alternating path from $m_{R}$ to $w_{d}$ which has $(i-1)$ more $(-1,-1)$
edges than $(+1,+1)$ edges and the edge $(m_{1},w_{d})$ is either a $(+1,-1)$
or a $(-1,+1)$ edge. Hence, the alternating path from $m_{R}$ to $w_{d}$
concatenated with the path $(w_{d},m_{1},w_{1})$ is the alternating path from
$m_{R}$ to $w_{1}$ which has $(i-1)$ more $(-1,-1)$ edges than $(+1,+1)$
edges, if the level of $w_{d}$ is $(i-1)$ then there is an alternating path
from $m_{R}$ to $w_{d}$ which has $(i-2)$ more $(-1,-1)$ edges than $(+1,+1)$
edges.the edge $(m_{1},w_{d})$ is a $(-1,-1)$ edge. Hence, the alternating
path from $m_{R}$ to $w_{d}$ concatenated with the path $(w_{d},m_{1},w_{1})$
is the alternating path from $m_{R}$ to $w_{1}$ which has $(i-1)$ more
$(-1,-1)$ edges than $(+1,+1)$ edges and if the level of $w_{d}$ is $(i+1)$
then there is an alternating path from $m_{R}$ to $w_{d}$ which has $i$ more
$(-1,-1)$ edges than $(+1,+1)$ edges and the edge $(m_{1},w_{d})$ is a
$(+1,+1)$ edge. Hence, the alternating path from $m_{R}$ to $w_{d}$
concatenated with the path $(w_{d},m_{1},w_{1})$ is the alternating path from
$m_{R}$ to $w_{1}$ which has $(i-1)$ more $(-1,-1)$ edges than $(+1,+1)$
edges.

Now if $w_{k}$ be the $k^{th}$ woman added to $B_{d}$ in step (e) (where
$k\geq 1$) and for all $j\leq k$ we assume that if the level of $w_{j}$ is $i$
then there exists an alternating path from $m_{R}$ to $w_{j}$ which has
$(i-1)$ more $(-1,-1)$ edges than $(+1,+1)$ edges. Now if $w_{k+1}$ is the
$(k+1)^{th}$ woman who is added in $B_{d}$ in step (e). Then $w_{k+1}$ is
added to $B_{d}$ because her matched partner $M(w_{k+1})=m_{k+1}$ is adjacent
to $w_{d}$ which is added to $B_{d}$ in step (c) or in step (e). Let the level
of $m_{k+1}$ is $i$. Now, if the level of $w_{d}$ is $i$ then there is an
alternating path from $m_{R}$ to $w_{d}$ which has $(i-1)$ more $(-1,-1)$
edges than $(+1,+1)$ edges and the edge $(m_{k+1},w_{d})$ is either a
$(+1,-1)$ or a $(-1,+1)$ edge. Hence, the alternating path from $m_{R}$ to
$w_{d}$ concatenated with the path $(w_{d},m_{k+1},w_{k+1})$ is the
alternating path from $m_{R}$ to $w_{k+1}$ which has $(i-1)$ more $(-1,-1)$
edges than $(+1,+1)$ edges, if the level of $w_{d}$ is $(i-1)$ then then there
is an alternating path from $m_{R}$ to $w_{d}$ which has $(i-2)$ more
$(-1,-1)$ edges than $(+1,+1)$ edges and the edge $(m_{k+1},w_{d})$ is a
$(-1,-1)$ edge. Hence, the alternating path from $m_{R}$ to $w_{d}$
concatenated with the path $(w_{d},m_{k+1},w_{k+1})$ is the alternating path
from $m_{R}$ to $w_{k+1}$ which has $(i-1)$ more $(-1,-1)$ edges than
$(+1,+1)$ edges and if the level of $w_{d}$ is $(i+1)$ then there is an
alternating path from $m_{R}$ to $w_{d}$ which has $i$ more $(-1,-1)$ edges
than $(+1,+1)$ edges and the edge $(m_{k+1},w_{d})$ is a $(+1,+1)$ edge.
Hence, the alternating path from $m_{R}$ to $w_{d}$ concatenated with the path
$(w_{d},m_{k+1},w_{k+1})$ is the alternating path from $m_{R}$ to $w_{k+1}$
which has $(i+1)$ more $(+1,+1)$ edges than $(-1,-1)$ edges.

Hence, for a woman $w\in B_{d}$ which is at level $i$ there is an alternating
path with $(i-1)$ more $(-1,-1)$ edges than $(+1,+1)$ edges which starts at
$m_{R}$ and ends in $w$ where $m_{R}$ is an unmatched man and also an endpoint
of a SRAP in the PFM $M$.

######  Lemma 3.14.

For an edge $(m,w)\in A_{m}\times B_{d}$ in $G$ we have the following

  1. (i)

If $m$ is at level $i$ and $w$ is at level $(i+1)$ then the edge $(m,w)$ is
not a $(+1,+1)$ edge.

  2. (ii)

If $m$ is at level $i$ then $w$ cannot be at level $(i-1)$ or below.

  3. (iii)

If $m$ is at level $i$ and $w$ is at level $i$ then $(m,w)$ is a $(-1,-1)$
edge.

######  Proof 3.15.

Condition (i): Suppose such a pair $(m,w)$ exists. From Lemma 3.12, there is
an alternating path $\rho_{I}$ from $m$ to $m_{I}$ with $i$ more $(+1,+1)$
edges than $(-1,-1)$ edges, where $m_{I}$ is an unmatched man and also an
endpoint of an SIAP, and there is an alternating path $\rho_{R}$ from $w$ to
$m_{R}$ with $i$ more $(-1,-1)$ edges than $(+1,+1)$ edges, where $m_{R}\in
A\setminus P$ and $m_{R}$ is an endpoint of an SRAP. Hence the alternating
path $\rho$ = $\rho_{I}\circ\rho_{R}$ has more $(+1,+1)$ edges than $(-1,-1)$
edges. Here $\circ$ denotes concatenation.

Condition (ii): If $(m,w)$ is an edge in $G$ and level of $m$ is $i$ then the
level of $w$ cannot be less than $(i-1)$. Suppose there is a man $m\in A_{m}$
at level $i$ adjacent to a woman $w\in B_{d}$ at level $(i-1)$. Note that
$(m,w)$ is a $(-1,-1)$ edge because all edges between a man at level $i$ and a
woman at level $(i-1)$ are $(-1,-1)$ edges. So, from Lemma 3.12, there is an
alternating path $\rho_{I}$ from $m$ to $m_{I}$ (where $m_{I}$ is an unmatched
man and also an endpoint of a SIAP) with $i$ more $(+1,+1)$ edges than
$(-1,-1)$ edges. Again from Lemma 3.12 we get that there is an alternating
path $\rho_{R}$ from $w$ to $m_{R}$ (where $m_{R}$ is a non-critical man and
also an endpoint of a SRAP) which has $(i-2)$ more $(-1,-1)$ edges than
$(+1,+1)$ edges. Hence the alternating path $\rho$ = $\rho_{I}\hskip
5.69054pto\hskip 5.69054pt\rho_{R}$ has more $(+1,+1)$ edges than $(-1,-1)$
edges (where $o$ denotes the concatenation of two paths). Here $\rho$ is an
alternating path which starts from $m_{I}$ then it goes to $m$ which has $i$
$(+1,+1)$ edges then it takes the edge $(m,w)$ which is a $(-1,-1)$ edge and
then it takes the alternating path from $w$ to $m_{R}$ which has $(i-2)$
$(-1,-1)$ edges. Hence, $\rho$ has $i$ $(+1,+1)$ edges and $(i-1)$ $(-1,-1)$
edges. Hence, $M\oplus\rho$ is a more popular matching than $M$, which is a
contradiction. Hence, $m\in A_{m}$ at level $i$ cannot be adjacent to a woman
$w\in B_{d}$ at level $(i-1)$.

Condition (iii): Suppose there is a man $m\in A_{m}$ at level $i$ which is
adjacent to a woman $w\in B_{d}$ at level $i$ such that $(m,w)$ is not a
$(-1,-1)$ edge. So, from Lemma 3.12 we get that there is an alternating path
$\rho_{I}$ from $m$ to $m_{I}$ (where $m_{I}$ is an unmatched man and also an
endpoint of a SIAP) with $i$ more $(+1,+1)$ edges than $(-1,-1)$ edges. Again
from Lemma 3.12 we get that there is an alternating path $\rho_{R}$ from $w$
to $m_{R}$ (where $m_{R}$ is a non-critical man and also an endpoint of a
SRAP) which has $(i-1)$ more $(-1,-1)$ edges than $(+1,+1)$ edges. Hence the
alternating path $\rho$ = $\rho_{I}\hskip 5.69054pto\hskip 5.69054pt\rho_{R}$
has more $(+1,+1)$ edges than $(-1,-1)$ edges (where $o$ denotes the
concatenation of two paths). Here $\rho$ is an alternating path which starts
from $m_{I}$ then it goes to $m$ which has $i$ $(+1,+1)$ edges then it takes
the edge $(m,w)$ which is not a $(-1,-1)$ edge and then it takes the
alternating path $w$ to $m_{R}$ which has $(i-1)$ $(-1,-1)$ edges. Hence,
$\rho$ has $i$ $(+1,+1)$ edges and $(i-1)$ $(-1,-1)$ edges. Hence,
$M\oplus\rho$ is a more popular matching than $M$, which is a contradiction.
Hence, if $m\in A_{m}$ at level $i$ is adjacent to a woman $w\in B_{d}$ at
level $i$ then $(m,w)$ is a $(-1,-1)$ edge.

######  Lemma 3.16.

For an edge $(m,w)\in A_{r}\times B_{d}$ in $G$ we have the following

  1. (i)

If $m$ is at level $i$ and $w$ is at level $(i+1)$ then the edge $(m,w)$ is
not a $(+1,+1)$ edge.

  2. (ii)

If $m$ is at level $i$ then $w$ cannot be at level $(i-1)$ or below.

  3. (iii)

If $m$ is at level $i$ and $w$ is at level $i$ then $(m,w)$ is a $(-1,-1)$
edge.

######  Proof 3.17.

Condition (i): If $m$ is at level $i$ and $w$ is at level $(i+1)$ such that
the edge $(m,w)$ is a $(+1,+1)$ edge then in step (e) of the partition method
$m$ and his matched partner are added to $A_{d}\cup B_{d}$. Hence $m\notin
A_{r}$.

Conditions (ii) and (iii): These two conditions are vacuously true because
according to construction of the sets defined in the partition method there
are no edges $(m,w)\in A_{r}\times B_{d}$ such that $m$ is at level $i$ and
$w$ is at level $j$ where $j\leq i$. This is because if level of $m$ is $i$
where $j\leq i$ then in step (e) of the partition method $m$ and his matched
partner are added to $A_{d}\cup B_{d}$

######  Lemma 3.18.

For a pair $(m,w)\in A_{m}\times B_{r}$ we have the following

  1. (i)

If $m$ is at level $i$ and $w$ is at level $(i+1)$ then the edge $(m,w)$ is
not a $(+1,+1)$ edge.

  2. (ii)

If $m$ is at level $i$ then $w$ cannot be at level $(i-1)$ or below.

  3. (iii)

If $m$ is at level $i$ and $w$ is at level $i$ then $(m,w)$ is a $(-1,-1)$
edge.

######  Proof 3.19.

Condition (i): If $m$ is at level $i$ and $w$ is at level $(i+1)$ such that
the edge $(m,w)$ is a $(+1,+1)$ edge then in step (f) of the partition method
$w$ and her matched partner are added to $A_{m}\cup B_{m}$. Hence $w\notin
B_{r}$.

Conditions (ii) and (iii): These two conditions are vacuously true because
according to construction of the sets defined in the partition method there
are no edges $(m,w)\in A_{m}\times B_{r}$ such that $m$ is at level $i$ and
$w$ is at level $j$ where $j\leq i$. This is because if level of $w$ is $j$
where $j\leq i$ then in step (f) of the partition method $w$ and her matched
partner are added to $A_{m}\cup B_{m}$

###  3.2 Transformation of $M_{m}$ to $M^{\prime}_{d}$

  1. (a)

All the men unmatched in $M_{m}$ are assigned level $1$ and they start
proposing from the beginning of their preference lists. A woman prefers a man
at level $j$ more than a man at level $i$ where $j>i$. If a man $m$ proposes a
woman $w$ then $w$ will accept $m$’s proposal iff $w$ is unmatched or if $w$
prefers $m$ more than her matched partner.

  2. (b)

If a critical man $m$ at level $i$ where $i<|C|$ exhausts his preference list
while proposing and remains unmatched then we assign level $(i+1)$ to $m$ and
$m$ starts proposing again from the beginning of his preference list.

  3. (c)

If a non-critical man $m$ at level $0$ exhausts his preference list while
proposing and remains unmatched then we assign level $1$ to $m$ and $m$ starts
proposing again from the beginning of his preference list.

Let $M^{\prime}_{d}$ be the matching which we get after applying the above
steps on the induced subgraph on $A_{m}\cup B_{m}$.

###  3.3 Transformation Procedures

We prove Theorem 3.2 now. Recall that, before partitioning $A\cup B$, we have
assigned levels, denoted by $level(u)$ to all the vertices $u\in A\cup B$
according to $M$ using Algorithm 1, and that $level(u)=level(M(u))$. Our
transformation procedures use these levels,

####  3.3.1 Transformation of $M_{d}$ to $M^{\prime}_{m}$:

Following are the steps involved in the transformation, we refer to this as
Transformation $1$.

  1. (a)

For $m\in A_{d},M(m)\in B_{d}$, if $level(m)=level(M(m))=i$, $i\geq 1$, then
set $level(m)=level(M(m))=i-1$

  2. (b)

Mark the matched edges present among level $0$ vertices as unmatched edges. So
all the level $0$ men in $A_{d}$ are not assigned to any partner now.

  3. (c)

Execute a proposal algorithm now. The men at level $0$ start proposing from
the beginning of their preference lists. A woman prefers a man at level $j$
more than a man at level $i$ where $j>i$. If a man $m$ proposes to a woman $w$
then $w$ will accept $m$’s proposal iff $w$ is unmatched or if $w$ prefers $m$
more than her matched partner.

  4. (d)

If a critical man $m$ at level $i$ where $i<|C|$ exhausts his preference list
while proposing and remains unmatched then we assign level $(i+1)$ to $m$ and
$m$ starts proposing again from the beginning of his preference list.

Let $M^{\prime}_{m}$ be the matching obtained after applying the above steps
on the induced subgraph on $A_{d}\cup B_{d}$, and let
$M^{*}_{m}=M^{\prime}_{m}\dot{\cup}M_{m}\dot{\cup}M_{r}$ be the resulting
matching in $G$.

####  3.3.2 Transformation of $M_{m}$ to $M^{\prime}_{d}$:

This is referred to as Transformation $2$ here onwards, and involves promoting
all the unmatched men to level $1$ and executing a similar proposal algorithm
as above. Men that get unmatched during the course of the proposal algorithm
continue proposing to women further down in their preference list. If they
exhaust their preference list without getting matched, then they are promoted
to the next higher level and continue proposing, however, non-critical men are
not promoted beyond level $1$.Let the resulting matching in $G$ be
$M^{*}_{d}=M^{\prime}_{m}\dot{\cup}M_{d}\dot{\cup}M_{r}$.

The following property is crucially used in proving that $M^{*}_{m}$ is a
minimum size popular feasible matching in $G$ whereas $M^{*}_{d}$ is a
dominant feasible matching in $G$.

######  Lemma 3.20.

For a man $m\in A_{d}$, if $level(m)=i,i>0$ before applying Transformation $1$
on $A_{d}\cup B_{d}$ then, after applying Transformation $1$,
$level(m)\in\\{i-1,i\\}$. The same holds for a woman $w\in B_{d}$. Similarly,
for a man $m\in A_{m}$, if $level(m)=i$ before applying Transformation $2$ on
$A_{m}\cup B_{m}$ then, after applying Transformation $2$,
$level(m)\in\\{i,i+1\\}$. The same holds for a woman $w\in B_{m}$.

######  Proof 3.21.

We prove the property for Transformation $2$. The proof for Transformation $1$
is analogous.

Suppose there exists a man $m\in A_{m}$ who was assigned level $i$ before
applying Transformation $2$ on $A_{m}\cup B_{m}$ but after applying
Transformation $2$ suppose $m$ is assigned level $(i+2)$ or more. In
Transformation $2$ we convert the matching $M_{m}$ to $M_{d}^{*}$. If $m$ is
unmatched in $M_{m}$ then the level of $m$ in $M_{m}$ was 0 and it can be at
most at level 1 in $M_{d}^{*}$ because $m$ is a non-critical man. So, $m$
cannot be an unmatched man because it contradicts our assumption that the
level of $m$ in $M_{d}^{*}$ is $(i+2)$ or more. Suppose $m$ is matched to a
woman $w$ in $M_{m}$ and the level of $m$ is $i$. While applying
Transformation $2$ $w$ rejected $m$ because $w$ got a proposal from some man
$m^{\prime}$ who is better than $m$ and is at level $i$. Note that $w$ must
have rejected $m$ while applying Transformation $2$ because after applying
Transformation $2$ level of $m$ changes to $(i+2)$ or more from $i$. Now,
since $m$ is assigned level $(i+2)$ or more so $m$ exhausts his preference
list while proposing and remains unmatched at level $i$. So, $m$ gets promoted
to level $(i+1)$ and he starts proposing from the beginning of his preference
list. Again since $m$ is assigned level $(i+2)$ or more so $m$ exhausts his
preference list while proposing and remains unmatched at level $i+1$ but this
is not possible because in the worst case $m$ can propose to $w$ and get
matched to her. This is because $w$ would reject $m^{\prime}$ which is at
level $i$ and $m$ is at level $(i+1)$. Hence $w$ would accept $m$’s proposal
and the level of $w$ changes to $(i+1)$. Note that no man $m^{\prime\prime}$
can get promoted from level $i$ to level $(i+1)$ and breaks the engagement of
$m$ and $w$ because if this happens then in $M_{m}$ the edge
$(m^{\prime\prime},w)$ is a $(+1,+1)$ edge but since both $m^{\prime\prime}$
and $w$ are in the same level $i$ in $M_{m}$ hence $(m^{\prime\prime},w)$
cannot be a $(+1,+1)$ edge. Hence, $m$ does not exhaust his preference list
while proposing at level $i+1$. So, after applying Transformation $2$ the
level of $m$ can be either $i$ or $(i+1)$.

Theorems 3.22 and 3.24 show that the matchings output by the transformations
are a minimum size popular feasible matching and a dominant feasible matching
in $G$ respectively.

######  Theorem 3.22.

$M^{*}_{m}$ = $(M_{m}^{\prime}\cup M_{m}\cup M_{r})$ is a minimum size popular
feasible matching.

######  Proof 3.23.

The four conditions given in Theorem 2.2 are sufficient to show that a
matching is a minimum size popular feasible matching. We show that
$M^{\prime}$ satisfies all of them.

Before applying the Transformation $1$, $M$ satisfied conditions $1$ to $3$ of
Theorem 2.2 because of the way Algorithm 1 assigns levels.]

After applying Transformation $1$, the matching $M_{d}$ changes to
$M_{m}^{\prime}$ and the levels of the vertices in $A_{d}\cup B_{d}$ decrease
by at most $1$ (Lemma 3.20). So, if $M^{\prime}$ does not satisfy conditions
$1-3$ of Theorem 2.2 then it has to be because of the pairs present in
$A_{m}\times B_{d}$ and $A_{r}\times B_{d}$. Now we show that the conditions
are still satisfied.

Below the proofs are given only for the pairs in $A_{m}\times B_{d}$. Proofs
for the pairs in $A_{r}\times B_{d}$ are similar.

Let $(m,w)$ be an edge in $A_{m}\times B_{d}$. From Lemma 3.14 (ii), if the
level of $w$ is $i$ with respect to $M$, then $m$ has level $j\leq i$. Now,
after applying the Transformation 1, the level of $w$ either remains $i$ or
becomes $(i-1)$. In the former case, the first condition of Theorem 2.2 is
satisfied. In the later case, we have three possibilities: (a) either
$j<(i-1)$ or (b) $j=(i-1)$, or (c) $j=i$. In case (b), $(m,w)$ is not a
$(+1,+1)$ edge (Lemma 3.14 (i)), in case (c), $(m,w)$ is a $(-1,-1)$ edge
(Lemma 3.14 (iii)). Hence, there is no $(+1,+1)$ edge in between a pair
$(m,w)\in A_{m}\times B_{d}$ in the matching $M^{\prime}$ where $m$ is at
level $j$ and $w$ is at level $i$ such that $j\leq i$. Hence, condition $1$ is
satisfied.

From Lemma 3.14 (ii), if the level of $w$ is $i$ in $M$, then $m$ has level
$j\leq i$. If level of $w$ changes to $(i-1)$ after applying the
Transformation $1$, and if level of $m$ is $i$, then due to Lemma 3.14(iii),
$(m,w)$ is a $(-1,-1)$ edge. Thus the condition $2$ of Theorem 2.2 is
satisfied.

From Lemma 3.14 (i), if $w$ is at level $i$ with respect to $M$, then level of
$m$ is $j\leq i$. If level of $w$ changes to $(i-1)$, the conditions of
Theorem 2.2 are still satisfied because no man in $A_{m}$ adjacent to $w$ is
present at level $(i+1)$ or above.

We know that all the unmatched men are non-critical men. In the first step of
Transformation $1$, we decrease the level of each vertex by $1$. Since the
level of a non-critical man is at most $1$ to begin with, and they are never
promoted to a higher level in the Transformation $1$, all the vertices
unmatched in $M^{*}_{m}$ remain at level $0$. Since all the conditions of
Theorem 2.2 are satisfied, $M^{*}_{m}$ is a minimum size popular feasible
matching.

The following is an analogous result for Transformation $2$.

######  Theorem 3.24.

$M^{*}_{d}$ = $(M_{d}\cup M^{\prime}_{d}\cup M_{r})$ is a dominant feasible
matching in $G$.

######  Proof 3.25.

Recall the 4 conditions given in Theorem A.7 which were sufficient to show
that a matching is a dominant feasible matching . So, now, we will show that
$M^{*}_{d}$ satisfies all the 4 conditions given in Theorem A.7. Hence,
$M^{*}_{d}$ is a dominant feasible matching.

Before applying Transformation $2$ the conditions 1 to 3 of Theorem A.7 were
already satisfied in the matching $M$ because the levelling algorithm for
minimum size popular feasible matching assigns levels to the vertices in such
a manner that the conditions 1 to 3 gets satisfied (recall the three phases of
an iteration of the Levelling Algorithm for minimum size popular feasible
matching , each phase ensures each condition from 1 to 3 of Theorem A.7 gets
satisfied). But after applying Transformation $2$ the matching $M_{m}$ changes
to $M_{d}^{*}$ and the level of the vertices present in $A_{m}\cup B_{m}$
increases by at most 1 (Lemma 3.20). So, if the conditions 1 to 3 of Theorem
A.7 are not satisfied in $M^{*}_{d}$ then it has to be because of the pairs
present in $A_{m}\times B_{d}$ and $A_{m}\times B_{r}$. So, now we show that
the pairs in $A_{m}\times B_{d}$ and $A_{m}\times B_{r}$ in the matching
$M^{*}_{d}$ will also satisfy the conditions 1 to 3. Below the proofs are
given only for the pairs present in $A_{m}\times B_{d}$. Proofs for the pairs
present in $A_{m}\times B_{r}$ are similar to the proofs given for the pairs
in $(A_{m}\times B_{d})$.

Condition $1$: For a pair $(m,w)\in A_{m}\times B_{d}$ if $(m,w)$ is an edge
in $G$ then from Lemma 3.14 (ii) we get that before applying Transformation
$2$ if the level of $m$ is $i$ then $w$ is present at an level $i$ or higher.
Now, after applying Transformation $2$ the level of $m$ either remains $i$ or
becomes $(i+1)$. So, if the level of $m$ remains $i$ after applying
Transformation $2$ then the Condition $1$ of Theorem A.7 is satisfied because
$w$ is present either at a level higher than $i$ or at level $i$ in that case
the edge $(m,w)$ is a $(-1,-1)$ edge (Lemma 3.14 (iii)). Now, if the level of
$m$ becomes $(i+1)$ after applying Transformation $2$ then we have three cases
either $w$ is at level higher than $(i+1)$ or $w$ is at level $i$ in that case
$(m,w)$ is a $(-1,-1)$ edge (Lemma 3.14 (iii)) or $w$ is at level $(i+1)$ in
that case $(m,w)$ is not a $(+1,+1)$ edge (Lemma 3.14 (i)). Hence, there is no
$(+1,+1)$ edge in between a pair $(m,w)\in A_{m}\times B_{d}$ in the matching
$M^{*}_{d}$ where $m$ is at level $i$ and $w$ is at level $j$ such that $j\leq
i$. Hence, Condition $1$ is satisfied.

Condition $2$: For a pair $(m,w)\in A_{m}\times B_{d}$ if $(m,w)$ is an edge
in $G$ then from Lemma 3.14 (ii) we get that before applying Transformation
$2$ if the level of $m$ is $i$ then $w$ is present at an level $i$ or higher.
Hence, no man at level $i$ is adjacent to a woman at level $(i-1)$. Hence,
Condition $2$ is vacuously satisfied when $m$ remains at level $i$ after
applying Transformation $2$. If level of $m$ changes to $(i+1)$ after applying
Transformation $2$ and if level of $w$ is $i$ then due to Lemma 3.14 (iii) we
get that $(m,w)$ is a $(-1,-1)$ edge. Hence, Condition $2$ is satisfied.

Condition $3$: For a pair $(m,w)\in A_{m}\times B_{d}$ if $(m,w)$ is an edge
in $G$ then from lemma 3.14 (i) we get that before applying Transformation $2$
if $m$ is at level $i$ then level of $w$ is $i$ or more. If level of $m$
remains $i$ after applying Transformation $2$ then Condition $3$ of Theorem
A.7 is satisfied because no woman in $B_{d}$ adjacent to $m$ is present at
level $(i-2)$ or below. If level of $m$ changes to $(i+1)$ then also Condition
$3$ of Theorem A.7 is satisfied because no woman in $B_{d}$ adjacent to $m$ is
present at level $(i-1)$ or below.

Condition $4$: We know that the set of unmatched men are non-critical men.
While applying Transformation $2$ if a non-critical man $m$ exhausts its
preference list while proposing and remains unmatched at level 0 then we
assign level 1 to $m$ and $m$ starts proposing again from the beginning of his
preference list. Now if $m$ again exhausts his preference list while proposing
and remains unmatched at level 1 then $m$ remains unmatched in the matching
$M^{*}_{d}$. Hence, if a man $m$ is unmatched in $M^{*}_{d}$ it has to be at
level 1. Hence Condition $4$ of Theorem A.7 is satisfied.

Since all the conditions of Theorem A.7 are satisfied. Hence, $M^{*}_{d}$ is a
dominant feasible matching .

## References

  * [1] Péter Biró, Tamás Fleiner, Robert W Irving, and David F Manlove.  The college admissions problem with lower and common quotas.  Theoretical Computer Science, 411(34-36):3136–3153, 2010.
  * [2] Ágnes Cseh, Chien-Chung Huang, and Telikepalli Kavitha.  Popular matchings with two-sided preferences and one-sided ties.  SIAM J. Discret. Math., 31(4):2348–2377, 2017.
  * [3] Ágnes Cseh and Telikepalli Kavitha.  Popular edges and dominant matchings.  Mathematical Programming, 172(1):209–229, 2018.
  * [4] Yuri Faenza and Telikepalli Kavitha.  Quasi-popular matchings, optimality, and extended formulations.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 325–344. SIAM, 2020.
  * [5] Yuri Faenza, Telikepalli Kavitha, Vladlena Powers, and Xingyu Zhang.  Popular matchings and limits to tractability.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2790–2809. SIAM, 2019.
  * [6] David Gale and Lloyd Stowell Shapley.  College admissions and the stability of marriage.  The American Mathematical Monthly, 69(1):9–15, 1962.
  * [7] David Gale and Marilda Sotomayor.  Some remarks on the stable matching problem.  Discret. Appl. Math., 11(3):223–232, 1985.
  * [8] Peter Gärdenfors.  Match making: assignments based on bilateral preferences.  Behavioral Science, 20(3):166–173, 1975.
  * [9] Kavitha Gopal, Meghana Nasre, Prajakta Nimbhorkar, and T. Pradeep Reddy.  Many-to-one popular matchings with two-sided preferences and one-sided ties.  In Ding-Zhu Du, Zhenhua Duan, and Cong Tian, editors, Computing and Combinatorics - 25th International Conference, COCOON 2019, volume 11653 of Lecture Notes in Computer Science, pages 193–205. Springer, 2019.
  * [10] Koki Hamada, Kazuo Iwama, and Shuichi Miyazaki.  The hospitals/residents problem with lower quotas.  Algorithmica, 74(1):440–465, 2016.
  * [11] Chien-Chung Huang and Telikepalli Kavitha.  Popular matchings in the stable marriage problem.  Information and Computation, 222:180–194, 2013.
  * [12] Chien-Chung Huang and Telikepalli Kavitha.  Popularity, mixed matchings, and self-duality.  Math. Oper. Res., 46(2):405–427, 2021.
  * [13] Telikepalli Kavitha.  A size-popularity tradeoff in the stable marriage problem.  SIAM J. Comput., 43(1):52–71, 2014.
  * [14] Telikepalli Kavitha.  Popular half-integral matchings.  In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, volume 55 of LIPIcs, pages 22:1–22:13, 2016\.
  * [15] Telikepalli Kavitha.  Popular matchings of desired size.  In Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, volume 11159 of Lecture Notes in Computer Science, pages 306–317. Springer, 2018.
  * [16] Telikepalli Kavitha.  Min-cost popular matchings.  In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, volume 182 of LIPIcs, pages 25:1–25:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [17] Telikepalli Kavitha.  Popular matchings with one-sided bias.  In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, volume 168 of LIPIcs, pages 70:1–70:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [18] Telikepalli Kavitha.  Matchings, Critical Nodes, and Popular Solutions.  In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021), volume 213, pages 25:1–25:19, 2021.
  * [19] Telikepalli Kavitha.  Maximum matchings and popularity.  In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 85:1–85:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [20] Telikepalli Kavitha, Tamás Király, Jannik Matuschke, Ildikó Schlotter, and Ulrike Schmidt-Kraepelin.  Popular branchings and their dual certificates.  In Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, volume 12125 of Lecture Notes in Computer Science, pages 223–237. Springer, 2020.
  * [21] Donald Ervin Knuth.  Marriages stables.  Technical report, 1976.
  * [22] Meghana Nasre and Prajakta Nimbhorkar.  Popular matchings with lower quotas.  In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, volume 93 of LIPIcs, pages 44:1–44:15, 2017.
  * [23] Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, and Ankita Sarkar.  Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower Quotas.  In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021), volume 213, pages 30:1–30:21, 2021.
  * [24] A. Robards, Paul.  Applying two-sided matching processes to the united states navy enlisted assignment process, 2001.
  * [25] Alvin 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.  doi:10.1086/261272.
  * [26] Alvin E. Roth.  On the allocation of residents to rural hospitals: A general property of two-sided matching markets.  Econometrica, 54(2):425–427, 1986.
  * [27] Mallory Soldner.  Optimization and measurement in humanitarian operations, 2014.

##  Appendix A Proofs from Section 2

###  A.1 Reduction for dominant feasible matching

The high level idea to find a dominant feasible matching in an marriage
instance with critical men is exactly the same as finding the minimum size
popular feasible matching . The results given in this section are similar to
the results given for minimum size popular feasible matching . At first we
reduce our marriage instance with critical men $G=(A\cup B)$ to a stable
marriage instance ($G^{\prime\prime}$) $G^{\prime\prime}=(A^{\prime\prime}\cup
B^{\prime\prime},E^{\prime\prime})$. Then we show that every stable matching
in $G^{\prime\prime}$ can be mapped to a dominant feasible matching in $G$. We
also show surjectivity of this map.

The reduction for dominant feasible matching is very similar to that for
minimum size popular feasible matching. The only difference with the previous
reduction is the following. In the reduction for minimum size popular feasible
matching, $G^{\prime}$ has only one copy of a man $m\in A\setminus P$. In this
reduction, such men have two copies in the reduced instance
$G^{\prime\prime}$, and there is one dummy woman in $G^{\prime\prime}$
corresponding to such a man. The number of levels in this reduction is one
more than that for minimum size popular feasible matching.

####  A.1.1 Reduction

  * •

The set $A^{\prime\prime}$:  Let $\ell$ be the number of men in $G$ who have
privileges i.e. $\ell=|P|$. For a man $m\in P$, $A^{\prime\prime}$ has
$(\ell+2)$ copies of $m$, denoted by $m^{0},m^{1},...,m^{\ell+1}$. Let
$A^{\prime\prime}_{m}$ denote the set of copies of $m$ in $A^{\prime\prime}$.
We refer to $m^{i}\in A^{\prime\prime}$ as the level $i$ copy of $m\in A$. For
a man $m\in A\setminus P$, $A^{\prime\prime}$ has only two copies of $m$, thus
$A^{\prime\prime}_{m}=\\{m^{0},m^{1}\\}$. Now,
$A^{\prime\prime}=\bigcup\limits_{m\in A}A^{\prime\prime}_{m}$.

  * •

The set $B^{\prime\prime}$:  All the women in $B$ are present in
$B^{\prime\prime}$. Additionally, corresponding to a man $m\in P$,
$B^{\prime\prime}$ contains $\ell+1$ dummy women
$d_{m}^{1},d_{m}^{2},d_{m}^{3},...,d_{m}^{\ell+1}$, denote the set of these
women as $D_{m}$. We call the dummy woman $d_{m}^{i}$ as the level $i$ dummy
woman for $m$. There is one dummy woman $d_{m}^{1}$ corresponding to a man $m$
in $A\setminus P$. Now, $B^{\prime\prime}=B\cup\bigcup\limits_{m\in A}D_{m}$.

We denote by $\langle list_{m}\rangle$ and $\langle list_{w}\rangle$ the
preference lists of $m\in A$ and $w\in B$ respectively. Let $\langle
list_{w}\rangle^{i}$ be the list of level $i$ copies of men present in
$\langle list_{w}\rangle$. Note that, for $m\in A\setminus P$ present in
Pref($w$), the level $i$ copy of $m$ for $i\geq 2$ is not present in
$A^{\prime\prime}$. Then $\langle list_{w}\rangle^{i}$ does not contain the
level $i$ copy of that man for $i\geq 2$. We now describe the preference lists
in $G^{\prime\prime}$. Here $\circ$ denotes the concatenation of two lists.

$m\in A\setminus P$: |  |
---|---|---
$m^{0}$ | : | $\langle list_{m}\rangle\circ d_{m}^{1}$
$m^{1}$ | : | $d_{m}^{1}\circ\langle list_{m}\rangle$
$m\in P$, $i\in\\{0,\ell+1\\}$: |  |
$m^{0}$ | : |  $\langle list_{m}\rangle$, $d_{m}^{1}$
$m^{i}$ | : |  $d_{m}^{i}$, $\langle list_{m}\rangle$, $d_{m}^{i+1}$, $i\in\\{1,\ell\\}$)
$m^{\ell+1}$ | : |  $d_{m}^{\ell+1}$, $\langle list_{m}\rangle$
$w$ s.t. $w\in B$ | : | $\langle list_{w}\rangle^{\ell+1}\circ\langle list_{w}\rangle^{\ell}\circ\ldots\circ\langle list_{w}\rangle^{0}$
$d^{i}_{m}$,$i\in\\{1,\ell+1\\}$ | : |  $m^{i-1}$, $m^{i}$

We refer to the instance $G^{\prime\prime}$ as $G^{\prime\prime}$.

####  A.1.2 Correctness of the reduction

After constructing the instance $G^{\prime\prime}$, our goal is to map a
stable matching $M^{\prime\prime}$ in $G^{\prime\prime}$ to a dominant
feasible matching $M$ in $G$. The mapping is a simple and natural one: For a
man $m\in A$, define $M(m)=B\cap\bigcup\limits_{m\in
A}M^{\prime\prime}(m^{i})$. Note that $M(m)$ denotes the set of non-dummy
women who are matched to any copy of $m$ in $A^{\prime\prime}$. In the rest of
this section, the term image always refers to the image under this map. A man
$m\in A$ in the matching $M$ is unmatched if none of its copies in
$A^{\prime\prime}$ gets matched to a non-dummy woman in the matching
$M^{\prime\prime}$. It remains to prove that $M$ is a dominant feasible
matching. This involves showing that $M$ is a matching, it is feasible,
popular, and all the matchings larger than $M$ does not get strictly more
votes than $M$.

To show that $M$ is a matching in $G$, we need to prove the following theorem.
The proof uses the fact that there are $\ell+2$ copies of a man $m\in P$, and
$\ell+1$ dummy women corresponding to that man $m\in P$, and each dummy woman
is the first choice of some copy of $m$.

######  Theorem A.1.

In any stable matching $M^{\prime\prime}$ in the $G^{\prime\prime}$ instance,
at most one copy of a man $m\in A$ gets matched to a non-dummy woman.

######  Proof A.2.

Suppose $m^{i}$ be the copy of the man $m\in A$ which gets matched to a non-
dummy woman. We prove using induction on $j$ where $j>i$ that $m^{j}$ does not
get matched to a non-dummy woman and it gets matched to the dummy woman
$d_{m}^{j}$.
Base Case: Suppose $j=(i+1)$. According to the theorem $m^{i}$ gets matched to
a non dummy woman. Now, if $m^{j}$ is not matched to $d_{m}^{j}$ then
$d_{m}^{j}$ remains unmatched in $M^{\prime\prime}$ because $m^{i}$ and
$m^{j}$ (note that $j=(i+1)$) are the only vertices adjacent to $d_{m}^{j}$.
In that case the edge $(m^{j},d_{m}^{j})$ forms a $(+1,+1)$ edge in
$M^{\prime\prime}$ because $m^{j}$ prefers $d_{m}^{j}$ the most. This is a
contradiction as $M^{\prime\prime}$ is a stable matching. Hence, $m^{j}$ is
matched to $d_{m}^{j}$.
Inductive Hypothesis: Assume that for $j=k$ (where $k>i$) $m^{j}$ gets matched
to $d_{m}^{j}$
Inductive Step: Now for $j=(k+1)$ we prove that $m^{j}$ gets matched to the
dummy woman $d_{m}^{j}$. According to the inductive hypothesis $m^{j-1}$ gets
matched to the dummy woman $d_{m}^{j-1}$ (note that $j=(k+1)$ here). Now, if
$m^{j}$ is not matched to $d_{m}^{j}$ then $d_{m}^{j}$ remains unmatched in
$M^{\prime\prime}$ because $m^{j-1}$ and $m^{j}$ are the only vertices
adjacent to $d_{m}^{j}$. In that case the edge $(m^{j},d_{m}^{j})$ forms a
$(+1,+1)$ edge in $M^{\prime\prime}$ because $m^{j}$ prefers $d_{m}^{j}$ the
most. This is a contradiction as $M^{\prime\prime}$ is a stable matching.
Hence, $m^{j}$ is matched to $d_{m}^{j}$.

Hence, by induction we get that all the copies of $m$ whose levels are greater
than $i$ cannot get matched to a non-dummy woman and gets matched to the first
dummy woman in his preference list. Since $i$ can be anything in the range
$[0,\ell+1]$,hence we proved that at most one copy of a man $m\in A$ gets
matched to a non dummy woman.

Theorem A.1 shows that $M$ is a matching. Now, we prove the following two
corollaries.

######  Corollary A.3.

If in a stable matching in the $G^{\prime\prime}$ instance $m^{i}$ (where
$i\in[0,\ell+1]$) is matched to a non dummy woman then $m^{j}$ (where $j>i)$
is matched to the dummy woman $d_{m}^{j}$ which is the first dummy woman in
the preference list of $m^{j}$.

######  Proof A.4.

The proof of this would be similar to the inductive proof done in the Theorem
A.1

######  Corollary A.5.

If in a stable matching in the $G^{\prime\prime}$ instance $m^{i}$ (where
$i\in[0,\ell+1]$) is matched to a non dummy woman then $m^{j}$ (where $j<i)$
is matched to the dummy woman $d_{m}^{j+1}$ which is the last dummy woman in
the preference list of $m^{j}$.

######  Proof A.6.

If $i=0$ then the statement is vacuously true. So, if $i\neq 0$ then we get
$m^{0}$ has to be matched to a dummy woman(from Theorem A.1). Now since there
is no dummy woman present in the beginning of the preference list of $m^{0}$,
so $m^{0}$ has to be matched with $d_{m}^{1}$ which is the last dummy woman in
the preference list of $m^{0}$. Again since $m^{0}$ is matched to $d_{m}^{1}$
so $m^{1}$ cannot be matched to $d_{m}^{1}$, it has to be matched with
$d_{m}^{2}$ which is again the last dummy woman in the preference list of
$m^{1}$. This will continue up to $m^{i}$ which gets matched to a non dummy
woman.

######  Theorem A.7.

A matching $M$ in $G$ that is an image of a stable matching $M^{\prime\prime}$
in $G^{\prime\prime}$ is a dominant feasible matching if it satisfies the
following conditions. Moreover, every such matching satisfies the conditions.

  1. 1.

All $(+1,+1)$ edges are present in between a man at level $i$ and a woman $w$
at level j where $j>i$.

  2. 2.

All edges between a man at level $i$ and a woman at level $(i-1)$ are
$(-1,-1)$ edges.

  3. 3.

No edge is present in between a man at level $i$ and a woman at level $j$
where $j\leq(i-2)$.

  4. 4.

All unmatched men are at level 1.

Here we need to show that if $M$ satisfies the four conditions, then $M$ is a
dominant feasible matching. So, to prove this we show at first $M$ is a
popular feasible matching and then we show that, for all feasible matchings
$N$ such that $|N|>|M|$, we have $\phi(N,M)<\phi(M,N)$.

$\mathbf{M}$ is a popular feasible matching : To show $M$ is a popular
feasible matching at first we need to show that $M$ is a feasible matching and
then we need to prove that for any other feasible matching $N$ in $G$ we have
$\phi(N,M)\leq\phi(M,N)$.

So, now we prove $M$ is a feasible matching. The arguments are similar to the
arguments given in the case of minimum size popular feasible matching .

Suppose $M$ is not a feasible matching and there exist a feasible matching $N$
in that marriage instance with critical men. Recall that we are only concerned
with those marriage instance with critical men which has at least one feasible
matching. Suppose $m$ be a critical man who is unmatched in $M$. So, the graph
$M\oplus N$ must contain an alternating path $\rho$ which starts from $m$. Now
$\rho$ can end in a man $m^{\prime}$ or in a woman $w^{\prime}$. CASE 1:
$\rho$ ends in $m^{\prime}$: Let $\rho=(m,w,m_{1},w_{1},....,m)$. Since $\rho$
ends in $m^{\prime}$, hence $m^{\prime}$ must be unmatched in $N$. Since $N$
is a feasible matching $m^{\prime}$ must be a non critical man and hence will
be at level 0 or at level 1. Since $m$ is unmatched in $M$ it has to be in the
level $\ell+1$ otherwise if $m$ is at level $i$ where $i<(\ell+1)$ then
$(m^{i},d_{m}^{i+1})$ would be a $(+1,+1)$ edge in $M^{\prime\prime}$ because
$m^{i}$ is unmatched in $M^{\prime\prime}$ and $d_{m}^{i+1}$ prefers $m^{i}$
the most in $G^{\prime\prime}$. Again no woman $w$ which is adjacent to $m$
can be at level $\ell$ or below because then $(m^{\ell+1},w)$ would form a
$(+1,+1)$ edge in $M^{\prime\prime}$ as $m^{\ell+1}$ is unmatched and $w$
prefers $m^{\ell+1}$ more than her matched partner which is at level $\ell$ or
below. Hence, in $\rho$, $w$ is at level $\ell+1$ again $M(w)=m_{1}$ is also
at level $\ell+1$ because the level of a woman and her matched partner are
same. Now, $w_{1}$ cannot be at level strictly less than $\ell$ due to
Condition $3$ of Theorem A.7. Hence the alternating path $\rho$ can go only
one level down that is from a man at level $i$ to a woman at level $i-1$. Note
that all the men who are at level greater than 1 are critical men because
there is no copy of a non-critical man of level greater than 1 in
$G^{\prime\prime}$. Since $\rho$ can go only one level down, hence there must
exist at least one critical man at each level from $2$ to $\ell$ and there are
at least two critical men ($m$ and $m_{1}$) at level $\ell+1$. Hence, the
number of critical men in $G$ is at least $\ell+1$. This is a contradiction
because we know the number of critical men in $G$ is $\ell$. CASE $2$: $\rho$
ends in $w^{\prime}$. Since $\rho$ ends in $w^{\prime}$ it has to unmatched in
$M$ and thus the level of $w$ is 0 as the level of each unmatched woman is
given 0. Hence $\rho$ starts from a man at level $\ell$ and ends at level 0.
Since $\rho$ can only go one level down, hence using the same arguments as
used in case 1 we get that there are at least $\ell+1$ critical men in $G$.
This is a contradiction because we know the number of critical men in $G$ is
$\ell$. Hence $M$ is a feasible matching.

Now, we prove $M$ is a popular feasible matching.

$\mathbf{M}$ is a popular feasible matching: Proof of this part is exactly
same as the proof given for theorem 2.2.

$\mathbf{M}$ is a dominant feasible matching: Now we show that for any
feasible matching $N$ such that $|N|>|M|$ we have $\phi(N,M)<\phi(M,N)$. We
take the graph $M\oplus N$, which is the disjoint union of alternating paths
and cycles. There is no alternating path or cycle $\rho$ in $M\oplus N$ such
that $\phi((M\oplus\rho),M)>\phi(M,(M\oplus\rho))$ otherwise $M$ is not a
popular feasible matchingṠo, now we need to show an alternating path or cycle
in $M\oplus N$ such that $\phi((M\oplus\rho),M)<\phi(M,(M\oplus\rho))$ then
only we can say $\phi(N,M)<\phi(M,N)$. Now, since $|N|>|M|$ there must exist
an alternating path which starts from a man $m_{1}$ unmatched in $M$ and ends
in a woman $w$ unmatched in $M$. Since $m_{1}$ is unmatched in $M$ it is at
level 1 due to Condition $4$ of theorem A.7. Suppose
$\rho=(m_{1},w_{1},m_{2},w_{2},m_{3},w_{3}...,w)$. The level of $w$ is 0 as
all unmatched women in $M$ are defined to be at level 0. Let $j$ be the
highest level of a man present in $\rho$. Note that the edges $(m_{i},w_{i})$
are all edges present in $N$. Since $m_{1}$ is at level 1 and the highest
level of a man in $\rho$ is $j$, hence we would have at most $(j-1)$ $(+1,+1)$
edges from $m_{1}$ to the $j^{th}$ level man as due to Condition $1$ of
theorem A.7 we get that $(+1,+1)$ edges are only present in between a lower
level man and a higher level woman. Now, from Condition $3$ of theorem A.7 we
get that $\rho$ can go only one level down. Due to condition $2$ we get that
while going $\rho$ can only take $(-1,-1)$ edges. Since level of $w$ is 0,
hence $\rho$ must have $j$ $(-1,-1)$ edges. Since $j\geq(j-1)$, hence the
number of $(-1,-1)$ edges is strictly greater than the number of $(+1,+1)$
edges in $\rho$. Hence, $\phi((M\oplus\rho),M)<\phi(M,(M\oplus\rho))$. Hence,
$M$ is a dominant feasible matching.

Now we show that any $M$ that is an image of a stable matching
$M^{\prime\prime}$ in $G^{\prime\prime}$ satisfies all the four conditions.
Condition $1$: Suppose there is $(+1,+1)$ edge in between a man $m$ at level
$i$ and woman $w$ at level $j$ such that $j\leq i$ in the matching $M$. Hence
$m$ prefers $w$ more than his matched partner in $M$. Now,
$M^{\prime\prime}(m^{i})=M(m)$ and since the preference list of $m^{i}$ in
$G^{\prime\prime}$ is same as the preference list of $m$ in the marriage
instance with critical men (except the dummy women in the beginning and end of
the preference list of $m^{i}$), $m^{i}$ prefers $w$ more than
$M^{\prime\prime}(m^{i})$. So, in $M^{\prime\prime}$ the edge $(m^{i},w)$ will
be a $(+1,+1)$ edge because $m^{i}$ prefers $w$ more than
$M^{\prime\prime}(m^{i})$ and $w$ prefers $m^{i}$ more than
$M^{\prime\prime}(w)$ because her matched partner is at level $j$ and $j\leq
i$. In the SM2 instance $w$ prefers a level $i$ man more than a level $j$ man
if $i>j$ and if $i=j$ then $w$ prefers $m^{i}$ more than $M^{\prime\prime}(w)$
because $w$ prefers $m$ more than $M(w)$ in the matching $M$. This contradicts
the fact that $M^{\prime\prime}$ is stable matching. Hence, $M$ satisfies
Condition $1$.
Condition $2$: Suppose there is a man $m$ at level $i$ which is adjacent to a
woman at level $(i-1)$ but the edge $(m,w)$ is not labelled $(-1,-1)$. $(m,w)$
cannot be labelled $(+1,+1)$ due to Condition $1$. So, it has to be labelled
$(+1,-1)$ and $(-1,+1)$. CASE 1: If $(m,w)$ is labelled $(+1,-1)$ then $m$
prefers $w$ more than $M(m)$. Hence $m^{i}$ prefers $w$ more than
$M^{\prime\prime}(m^{i})$ and $w$ prefers $m^{i}$ more than its matched
partner in $M^{\prime\prime}$ which is the $(i-1)$ level copy of $M(w)$. Hence
the edge $(m^{i},w)$ is a $(+1,+1)$ edge in the matching $M^{\prime\prime}$.
This contradicts the stability of $M^{\prime\prime}$. Case $2$: Now, if
$(m,w)$ is labelled $(-1,+1)$ then $w$ prefers $m$ more than $M(w)$. Now since
$m$ is at level $i$ so $m^{i}$ gets matched to a non dummy woman in the
matching $M^{\prime\prime}$. So, from Corollary A.5 we get that $m^{i-1}$ is
matched to the dummy woman $d_{m}^{i}$ which is present at the end of his
preference list. In this the edge $(m^{i-1},w)$ would be labelled $(+1,+1)$
because $m^{i-1}$ would prefer $w$ more than its matched partner in
$M^{\prime\prime}$ which is present at the last of his preference list and $w$
would prefer $m^{i-1}$ more than $M^{\prime\prime}(w)$, which is a $(i-1)$
level copy of $M(w)$ as $w$ prefers $m$ more than $M(w)$. This again
contradicts that $M^{\prime\prime}$ is a stable matching. Hence $M$ satisfies
Condition $2$.
Condition $3$: Suppose Condition $3$ is not satisfied, then there is a man
$m$, which at level $i$ is adjacent to a woman $w$ at level $j$ such that
$j\leq(i-2)$. In this case the edge $(m^{i-1},w)$ would be a $(+1,+1)$ edge
because $m^{i-1}$ prefers $w$ over its matched partner in $M^{\prime\prime}$
which is $d_{m}^{i}$ (Corollary A.5) and $w$ prefers $m^{i-1}$ over
$M^{\prime\prime}(w)$ which is a $(i-2)$ level copy of $M(w)$. This
contradicts the fact that $M^{\prime\prime}$ is a stable matching. Hence, $M$
satisfies Condition $3$.
Condition $4$: Suppose $M=g(M^{\prime\prime})$ is a feasible matching. So, if
there are unmatched men in $M$ then they are the non critical men. Let, $m$ be
an arbitrary unmatched man in $M$. Now, during the reduction from $M$ to
$M^{\prime\prime}$ we made two copies of $m$ in $A^{\prime\prime}$, they are
$m^{0}$ and $m^{1}$. Since $m$ is unmatched in $M$ we have that one of $m^{0}$
or $m^{1}$ is unmatched in $M^{\prime\prime}$ and the other would get matched
to the dummy woman $d_{m}^{1}$. Now, if $m^{0}$ is unmatched in
$M^{\prime\prime}$ then the edge $m^{0},d_{m}^{1}$ would form a $(+1,+1)$ edge
because in $m^{0}$ is unmatched and $d_{m}^{1}$ prefers $m^{0}$ the most. This
contradicts the fact that $M^{\prime\prime}$ is a stable matching. Hence,
$m^{1}$ is unmatched in $M^{\prime\prime}$ and thus the level of all unmatched
men in $M$ is 1.

Hence, any matching $M$ which is an image of a stable matching
$M^{\prime\prime}$ in $G^{\prime\prime}$ is a dominant feasible matching.
The proof of Theorem A.7 is similar to the proof of Theorem 2.2. Here we need
to show that if a matching $M$ satisfies the four conditions given in theorem
A.7 then $M$ is a dominant feasible matching. So, to prove this we show at
first $M$ is a popular feasible matching and then we show that for all
feasible matchings $N$ such that $|N|>|M|$ we have $\phi(N,M)<\phi(M,N)$.

####  A.1.3 Surjectivity of the map

######  Theorem A.8.

For every dominant feasible matching $M$ in $G$, there exists a stable
matching $M^{\prime\prime}$ in $G^{\prime\prime}$ such that $M$ is the image
of $M^{\prime\prime}$.

######  Proof A.9.

At first we apply a leveling algorithm to $M$ (Algorithm 2). Algorithm 2 takes
a minimum size popular feasible matching $M$ as input and assigns levels to
the vertices in $G$. The levels are used to get the pre-image of $M$ i.e. a
stable matching $M^{\prime\prime}$ in $G^{\prime\prime}$. Once the levels are
assigned by Algorithm 2, the pre-image is obvious - if a man $m$ in $G$ gets
assigned to level $i$, and $M(m)=w$ then $M^{\prime\prime}(m^{i})=w$. For
$j<i$, $M^{\prime\prime}(m^{j})=d_{m}^{j+1}$ which is the least preferred
dummy woman on his list, and for $j>i$, $M^{\prime\prime}(m^{j})=d_{m}^{j}$
which is the most preferred dummy woman on his list.

The proof of the theorem is immediate from the correctness of Algorithm 2,
proved below.

Now, we describe the leveling Algorithm which takes a dominant feasible
matching as input.

Input: A dominant feasible matching $M$ in a marriage instance with critical
men instance.
Output: Assigns level to the vertices in $\mathcal{G}$ based on the matching
$M$.

1:Initially all the unmatched men are assigned level 1 and all the vertices
other than unmatched men are assigned level 0

2:flag = true

3:while flag = true do

4: check1 = 0, check2 = 0, check3 = 0

5: while there exists a man $m$ at level $i$ and a woman $w$ at level $j$ such
that $j\leq i$ and $(m,w)$ is a $(+1,+1)$ edge do

6: Change the level of $w$ and its matched partner $M(w)$ from level $j$ to
level $(i+1)$. Note that $w$ cannot be unmatched in $M$ because then $M$ would
not be a PFM.

7: check1 = 1

8: end while

9: while there exists a man $m$ at level $i$ and a woman $w$ at level $j$ such
that $j<i$ and $(m,w)$ is a $(+1,-1)$ or a $(-1,+1)$ edge do

10: Change the level of $w$ and its matched partner $M(w)$ from level $j$ to
level $i$. Note that $w$ cannot be unmatched in $M$ because then $M$ would not
be a PFM.

11: check2 = 1

12: end while

13: while there exist a man $m$ at level $i$ and a woman $w$ at level $j$ such
that $j\leq(i-2)$ and $(m,w)$ is a $(-1,-1)$ edge do

14: Change the level of $w$ and its matched partner from level $j$ to level
$(i-1)$. Note that $w$ cannot be unmatched in $M$ because then $M$ would not
be a PFM.

15: check3 = 1

16: end while

17: if check1 = 0 and check2 = 0 and check3 = 0 then

18: flag = false

19: end if

20:end while

Algorithm 2 leveling Algorithm for dominant feasible matching

The proof for the termination of Algorithm 2 and the proof of
$M^{\prime\prime}$ is a stable matching is exactly the same as the proof of
the termination of Algorithm 1 and the proof of $M^{\prime}$ is a stable
matching respectively.

######  Theorem A.10.

All non-critical men are assigned level zero or one and the critical men are
assigned level less than or equal to $(l+1)$ (where $l$ is the number of
critical men in the marriage instance with critical men instance).

######  Proof A.11.

Suppose there is a non-critical man $m^{i}$ gets a level $i>1$ then there is
an alternating path from a woman $w^{0}$ at level 0 or from an unmatched man
$m^{0}$ at level 0 (theorem 2.5)to $m^{i}$ which has i more $(+1,+1)$ edges
than $(-1,-1)$ edges. Let this alternating path be $\rho$. In this case
$M\oplus\rho$ is a more popular matching than $M$. Hence contradiction. Hence,
all non critical men are assigned level less than or equal to 1.

Suppose there is a critical man who is assigned level $j$ where $j>(l+1)$.
Now, since there are only $l$ critical men in the marriage instance with
critical men instance. Hence, there exists a level $i<j$ such that $i$ is
empty. This contradicts theorem 2.5. Hence, all critical men are assigned
level less than or equal to $(l+1)$.