11institutetext: Hasso-Plattner-Institute, University of Potsdam, Germany
22institutetext: Institute of Economics, Centre for Economic and Regional
Studies, Hungary
22email<EMAIL_ADDRESS>22email<EMAIL_ADDRESS>
33institutetext: TU Berlin, Germany, 33email<EMAIL_ADDRESS>
# Pareto optimal and popular house allocation
with lower and upper quotas

Ágnes Cseh 1122 Tobias Friedrich 11 Jannik Peters 33

###### Abstract

In the house allocation problem with lower and upper quotas, we are given a
set of applicants and a set of projects. Each applicant has a strictly ordered
preference list over the projects, while the projects are equipped with a
lower and an upper quota. A feasible matching assigns the applicants to the
projects in such a way that a project is either matched to no applicant or to
a number of applicants between its lower and upper quota.

In this model we study two classic optimality concepts: Pareto optimality and
popularity. We show that finding a popular matching is hard even if the
maximum lower quota is $2$ and that finding a perfect Pareto optimal matching,
verifying Pareto optimality, and verifying popularity are all -complete even
if the maximum lower quota is $3$. We complement the last three negative
results by showing that the problems become polynomial-time solvable when the
maximum lower quota is $2$, thereby answering two open questions of Cechlárová
and Fleiner [17]. Finally, we also study the parameterized complexity of all
four mentioned problems.

###### Keywords:

house allocation Pareto optimal matchings popular matchings complexity

##  1 Introduction

Many university courses involve team-based project work. In such courses, a
set of projects is offered and each student submits a list of projects she
finds acceptable. Ideally, the student also ranks these projects in order of
her preference. Naturally, the number of students ideally assigned to a
specific project strongly depends on the project itself. The lecturer
responsible for the project thus might restrict the number of students to an
interval. Projects that did not awake sufficient interest in the students are
then dropped, while the other projects start with a number of assigned
students that falls into the prescribed interval. Such quota constraints also
arise in various other contexts involving the centralized formation of groups,
including organizing team-based leisure activities, opening facilities to
serve a community, and coordinating rides within car-sharing systems. In these
and similar applications, the goal is to fulfill some optimality condition
under the assumption that the number of participants for each open activity is
within the prescribed limits of the activity.

###  1.1 Problem formulation and solution concepts

The mathematical formulation of this problem is known as the house allocation
problem with lower and upper quotas. In a house allocation instance, we are
given a two-sided market, where one side $A$ represents applicants, while the
other side $P$ represents projects. Each applicant has a strictly ordered
preference list of the projects she finds acceptable. Furthermore, each
project $p\in P$ has a lower quota $\ell_{p}$ and an upper quota $u_{p}$.

In a feasible matching, a project is either _open_ or _closed_. The central
feasibility requirement is that the number of applicants assigned to an open
project must lie between its lower and upper quota, whilst a closed project
has no assigned applicant. Each applicant is assigned to at most one project.
We define the optimality of a matching with respect to the satisfaction level
of the agents. In this paper, we study two well-known notions from the broad
topic of matchings under preferences: Pareto optimality and popularity.

A matching $M$ is Pareto optimal if there is no matching $M^{\prime}$, in
which no applicant is matched to a project she considers worse, while at least
one applicant is matched to a project she considers better than her project in
$M$. A matching $M$ is popular if there is no matching $M^{\prime}$ that would
win a head-to-head election against $M$, where each applicant casts a vote
based on her preferences on her assigned project in $M$ and in $M^{\prime}$.

###  1.2 Related work

Arulselvan et al. [2] derived several complexity results for the maximum
weight many-to-one matching problem with project closures and lower and upper
quotas. However, their model excludes agent preferences. In Table 1 we display
a structured overview of existing work in the field of matchings under
preferences with lower and upper quotas.

####  1.2.1 Stable matchings

In the classic hospitals residents problem [26, 31], the underlying model is a
bipartite many-to-one matching problem involving preferences on both sides,
and the goal is to find a stable matching, which is a matching where no
hospital-resident pair could improve their situation by being assigned to each
other. This model has been combined with lower and upper quotas in several
papers. Hamada et al. [32] considered a version where hospitals cannot be
closed and presented a polynomial-time algorithm to find a stable solution,
while Mnich and Schlotter [36] studied the fixed parameter tractability of
finding an approximately stable solution in no-instances identified by Hamada
et al. [32]. The model of Biró et al. [8] permitted hospital closures, and was
shown to lead to -hardness. Very recently, the setting of Biró et al. [8] was
further investigated by Boehmer and Heeger [11], who conducted a parameterized
study in the original hospitals residents setting, and also in the house
allocation setting, where hospitals only have a preference for filling their
quota, but do not mind which applicant is assigned to them. They also answered
an open question of Biró et al. [8] by showing that a stable matching in the
hospitals residents problem with lower quota at most 2 can be found in
polynomial time. For a further overview on matchings with quotas and
constraints we refer the reader to a recent survey by Aziz et al. [3].

| Stability | Pareto optimality | Popularity
---|---|---|---
1-sided, no project closures | open | [29] | open
1-sided, project closures | [11] |  [37, 33, 17], our paper | our paper
2-sided, no project closures | [32, 36] | [40] | [34, 38]
2-sided, project closures | [8, 11] | open | open
Table 1: Overview of the existing literature in the most related settings. The
four models differ in how many of the two sides are equipped with preferences,
and in the possibility of project closures. Note that stability is defined for
one-sided preferences such that hospitals do not differentiate between
applicants, but aim to fill their quota.

####  1.2.2 Pareto optimal matchings

Pareto optimality is one of the most studied concepts in coalition formation
and hedonic games [4, 7, 13, 23], and it has also been defined in the context
of various matching markets [16, 15, 6, 9]. As shown by Abraham et al. [1], in
the one-to-one house allocation model, a maximum size Pareto optimal matching
can be found in polynomial time. Pareto optimality of matchings with lower and
upper quotas on projects was studied in four papers. Motivated by a school
choice application with regional constraints, Goto et al. [29] analyzed the
case of so-called hierarchical lower quotas that must be obeyed. Monte and
Tumennasan [37] considered the case of project closures with complete lists,
while the model of Kamiyama [33] allowed incomplete lists as well. In all
three works, it was shown that a Pareto optimal matching can always be found
using a variant of the famous serial dictatorship algorithm. Cechlárová and
Fleiner [17] extended this algorithm to the case when an applicant can be
assigned to more than one project. They also showed for the many-to-one case
with lower and upper quotas that it is -hard to compute a maximum size Pareto
optimal matching if the maximum lower quota is at least $4$, furthermore that
it is -complete to verify if a matching is Pareto optimal if the maximum lower
quota is at least $3$. This lead the authors to ask whether both of these
problems stay intractable if no lower quota exceeds $2$. In this paper we show
that both problems are indeed polynomial-time solvable if the maximum lower
quota is $2$, while finding a maximum size Pareto optimal matching is
-complete if the maximum lower quota is $3$. Regarding two-sided instances,
Sanchez-Anguix et al. [40] conducted experiments to derive an approximate
Pareto optimal solution with workload balance as an additional requirement.

####  1.2.3 Popular matchings

Popularity as an optimality principle has been on the rise recently [19, 25,
30] in the matchings under preferences literature. On instances with two-sided
preferences, Brandl and Kavitha [12] and Gopal et al. [28] studied popularity
for many-to-many and many-to-one matching problems with upper quotas only. For
the model introduced in the latter paper, the complexity of deciding whether a
popular matching exists is still open. Krishnapriya et al. [34] and Nasre and
Nimbhorkar [38] investigated popular matchings in the hospital residents
problem with lower and upper quotas, but without the option to close
hospitals. They proved that whenever a feasible matching exists, a popular
matching has to exist as well. In the house allocation setting, the problem of
computing a popular matching is tractable, even if both upper quotas and
applicant weights are present, as shown by Sng and Manlove [42].

###  1.3 Our contribution and techniques

We provide an analysis of both Pareto optimal and popular matchings in the
setting of the house allocation problem with lower and upper quotas and derive
tractability results for both classic and parameterized complexity. Due to
space restrictions, we only sketch the main idea of most proofs in the body of
the paper, and provide the full proof in the appendix.

Table 2 displays a comprehensive overview of our results for classic
complexity. We answer both open questions of Cechlárová and Fleiner [17] and
show that a Pareto optimal matching can be verified and a perfect Pareto
optimal matching can be found in polynomial time if the maximum lower quota is
$2$. Furthermore, our work initiates the study of the popular house allocation
problem with lower quotas by showing that even if the maximum lower quota is
$2$ it is -hard to find a popular matching. However, we also present a
polynomial time algorithm to verify if a given matching is popular if no lower
quota exceeds $2$, while the same problem is shown to be -hard for maximum
lower quota $3$. We then reduce all three problems to the maximum weight
matching problem of Arulselvan et al. [2], for which we firstly observe a
simple reduction to the general factor problem introduced by Dudycz and Paluch
[21], and secondly design a faster algorithm for our special cases by
combining results from [21] and gadget techniques established by Cornuéjols
[18].

We then identify tractable sub-cases via the power of parameterized
complexity, as demonstrated by Table 3. Here we again use the connection to
maximum weight matchings and show how to use a treewidth-based algorithm of
Arulselvan et al. [2] to get fixed parameter tractability when parameterized
by the number of applicants. Further we give a flow-based algorithm to prove
fixed parameter tractability when parameterized by $m_{\text{quota}}$, the
number of projects with a lower quota greater than $1$. Since these two
algorithms are for the maximum weight matching problem, they also apply to a
recently introduced model in the area of multi-robot task allocation by Aziz
et al. [5]. Finally, by a reduction to the parametric integer programming
problem [22], we also show that the problem of finding a popular matching is
fixed parameter tractable when parameterized by the number of projects.

---
| $l_{\text{max}}\leq 2$ | $l_{\text{max}}\leq 3$ | $P_{\text{open}}$
pop-ha${}_{L}^{U}$ |  -c. Thm. 3 |  -h. Thm. 1 | -h. Cor. 2
perpo-ha${}_{L}^{U}$ | ¶ Cor. 1 | -c. Thm. 1
popv-ha${}_{L}^{U}$ | ¶ Thm. 7
pov-ha${}_{L}^{U}$ |  -c. [17]

Table 2: Overview of our results in classic complexity. The four problems
studied are finding a popular matching, finding a perfect Pareto optimal
matching, verifying popularity, and verifying Pareto optimality. The columns
$l_{\text{max}}\leq 2$ and $l_{\text{max}}\leq 3$ indicate the cases where the
maximum lower quota of any project is $2$ or $3$, respectively. The column
$P_{\text{open}}$ indicates the complexity of deciding whether there is
matching of our desired type that opens exactly the projects in the set
$P_{\text{open}}$.

---
| $n$ | $m$ | $m_{quota}$ | $m_{open}$ | $m_{\text{closed}}$
pop-ha${}_{L}^{U}$ |  [1]-h. Thm. 4 |  Thm. 5 | ? | -h. Thm. 10 | [1]-h. Thm. 11
perpo-ha${}_{L}^{U}$ |  Cor. 2 |  Thm. 8
popv-ha${}_{L}^{U}$ | [1]-h. Thm. 9
pov-ha${}_{L}^{U}$

Table 3: Overview of our parameterized results. The columns are the parameters
we use in the respective cases. The first parameter $n$ is the number of
applicants, $m$ is the number of projects, and $m_{\text{quota}}$ is the
number of projects with a lower quota greater than $1$. The parameter
$m_{\text{open}}$ asks for a matching that opens exactly $m_{\text{open}}$
projects, while $m_{\text{closed}}$ asks for a matching that closes exactly
$m_{\text{closed}}$ projects.

##  2 Preliminaries

In this section we formally introduce our notation and the problems we
consider.

####  2.0.1 Input graph

We are given a set $A$ of $n$ applicants, a set $P$ of $m$ projects, and a
bipartite graph $G=(A\dot{\cup}P,E)$, with $A$ and $P$ being the two sides of
the bipartition. The _neighborhood_ $N_{v}$ of a vertex $v\in A\cup P$ is
defined as the set of vertices $v$ is adjacent to in $G$, and the _degree_
$\deg_{v}$ of a vertex $v$ equals $|N_{v}|$. We define $\Delta_{A}$ to be the
maximum degree of any vertex in $A$ and $\Delta_{P}$ to be the maximum degree
of any vertex in $P$. In our model, each project $p\in P$ is equipped with a
_lower quota_ $\ell_{p}\in\mathbb{N}$ and an _upper quota_
$u_{p}\in\mathbb{N}$. We refer to the maximum lower quota among all projects
as $\ell_{\max}$ and the maximum upper quota as $u_{\max}$.

####  2.0.2 Matching

A _matching_ $M\subseteq E$ is a set of edges so that each applicant $a\in A$
is incident to at most one edge in $M$, while each project $p\in P$ is either
incident to no edge in $M$ or its degree in the graph $(A\dot{\cup}P,M)$ is at
least $\ell_{p}$ and at most $u_{p}$. If applicant $a$ is assigned to project
$p$ in $M$, then we write $M(a)=p$ and $a\in M(p)$. A matching $M$ assigns
each applicant $a$ a project in $N_{a}$ or $a$ itself. The notation $M(a)=a$
serves convenience and it expresses that the applicant $a$ is unmatched.
Conversely, the quota requirement for the projects can be expressed as
$\ell_{p}\leq\lvert M(p)\rvert\leq u_{p}$ or $\lvert M(p)\rvert=0$ for each
project $p\in P$. We call a project $p\in P$ with $\lvert M(p)\rvert=0$
_closed_ and a project $p$ with $\ell_{p}\leq\lvert M(p)\rvert\leq u_{p}$
_open_. A matching $M$ is _perfect_ if $M(a)\neq a$ for all $a\in A$, i.e.,
all applicants are matched to a project in $M$.

####  2.0.3 Preferences

Each applicant $a\in A$ has a strict order $\succ_{a}$ over
$N_{a}\cup\\{a\\}$, which we call the _preference list_ of $a$. For each $a\in
A$ and $p\in N_{a}$ we assume that $p\succ_{a}a$, which translates into
applicant $a$ listing only the projects that are more preferable to her than
staying unmatched. If the applicant is clear from the context, we simply write
$\succ$ for her preference list.

We now introduce our two optimality concepts based on applicants’ preferences.
Given a matching $M$, we say that matching $M^{\prime}$ _dominates_ $M$ if
there is no $a\in A$ with $M(a)\succ_{a}M^{\prime}(a)$ and there is an $a\in
A$ with $M^{\prime}(a)\succ_{a}M(a)$. We call matching $M$ _Pareto optimal_ if
there is no matching that dominates $M$. Adding on to this, we call matching
$M^{\prime}$ _more popular_ than matching $M$ if ${\lvert\\{a\in A\mid
M^{\prime}(a)\succ_{a}M(a)\\}\rvert>\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert}$. Matching $M$ is _popular_ if there is
no other matching that is more popular than $M$.

We are now ready to define the four problems we tackle in this paper. The
first one of these is the standard popular matching problem. For two examples
regarding popularity we refer the reader to Section 7.2 in the appendix.

Popular house allocation with lower and upper quotas (pop-ha${}_{L}^{U}$)

Input: |  Graph $G=(A\dot{\cup}P,E)$, preferences $(\succ_{a})_{a\in A}$, and quotas $\ell,u\colon P\to\mathbb{N}$.
---|---
Question: |  Does $G$ have a popular matching?

Besides this we also study the complexity of verifying whether a given
matching is popular.

Popularity verification in house allocation with lower and upper quotas (popv-
ha${}_{L}^{U}$)

Input: |  Graph $G=(A\dot{\cup}P,E)$, preferences $(\succ_{a})_{a\in A}$, quotas $\ell,u\colon P\to\mathbb{N}$, and matching $M$.
---|---
Question: |  Does $G$ have a matching $M^{\prime}$ that is more popular than $M$?

Thirdly we study the problem of finding a Pareto optimal matching covering all
applicants. We remind the reader that (non-perfect) Pareto optimal matchings
can be found in polynomial time using a variant of the serial dictatorship
method [33, 37, 17].

Perfect Pareto optimal house allocation with lower and upper quotas (perpo-
ha${}_{L}^{U}$)

Input: |  Graph $G=(A\dot{\cup}P,E)$, preferences $(\succ_{a})_{a\in A}$, and quotas $\ell,u\colon P\to\mathbb{N}$.
---|---
Question: |  Does $G$ have a Pareto optimal matching that matches all applicants in $A$?

Finally we also study the verification version of Pareto optimality.

Pareto optimality verification in house allocation with lower and upper quotas
(pov-ha${}_{L}^{U}$)

Input: |  Graph $G=(A\dot{\cup}P,E)$, preferences $(\succ_{a})_{a\in A}$, quotas $\ell,u\colon P\to\mathbb{N}$, and matching $M$.
---|---
Question: |  Does $G$ have a matching $M^{\prime}$ that dominates $M$?

##  3 Connection to weighted matchings

Before diving into the main theorems of our paper, we present three auxiliary
lemmas in this section. These allow us to reduce our problems popv-
ha${}_{L}^{U}$, perpo-ha${}_{L}^{U}$, and pov-ha${}_{L}^{U}$ to the following
weighted many-to-one matching problem, defined by Arulselvan et al. [2].

Weighted bipartite matching with lower and upper quotas (w-ha${}_{L}^{U}$)

Input: |  Graph $G=(A\dot{\cup}P,E)$ with quotas $\ell,u\colon P\to\mathbb{N}$, weight function $w\colon E\to\mathbb{R}$, and a bound $W\in\mathbb{R}$.
---|---
Question: |  Is there a matching $M$ with $\sum_{e\in M}w(e)\geq W$?

First, we present a lemma that allows us to reduce this problem to
w-ha${}_{L}^{U}$.

###### Lemma 1

For each perpo-ha${}_{L}^{U}$ instance $\mathcal{I}$, there is a
w-ha${}_{L}^{U}$ instance $\mathcal{I}^{\prime}$ on the same graph, such that
each maximum weight matching in $\mathcal{I}^{\prime}$ corresponds to a Pareto
optimal matching in $\mathcal{I}$, with a maximum number of matched
applicants. The instance $\mathcal{I}^{\prime}$ can be computed in polynomial
time from $\mathcal{I}$.

###### Proof

Given any $a\in A$ with preference list
$p_{1},\succ_{a},\dots,\succ_{a}p_{k}$, we define the weight of the edge
between $a$ and any $p_{i}$ for $i=1,\dots,k$ to be $(k-i)+mn$. Let $M$ be a
maximum weight matching in this new instance. First $M$ has to be a maximum
matching, since any larger matching would lead to a vertex being matched that
was previously unmatched and thus increasing the weight of the matching by at
least $mn-(n-1)m>0$. Furthermore the matching has to be Pareto optimal, since
any matching dominating it would obviously lead to a matching of larger
weight. ∎

Lemma 1 shows that in order to check if a perfect Pareto optimal matching
exists in $\mathcal{I}$, it is sufficient to find a maximum weight matching in
$\mathcal{I}^{\prime}$ and check if it is perfect. However, we remark that
Lemma 1 does not hold in the reverse direction: not all perfect Pareto optimal
matchings of $\mathcal{I}$ translate into a maximum weight matching in
$\mathcal{I}^{\prime}$.

For popv-ha${}_{L}^{U}$ and pov-ha${}_{L}^{U}$, similar statements as first
observed by Biró et al. [10] for one-to-one popular matchings. Our results
state that a matching is popular / Pareto optimal if and only if it is a
maximum weight matching in a certain weighted graph.

###### Lemma 2

For each popv-ha${}_{L}^{U}$ /pov-ha${}_{L}^{U}$ instance $\mathcal{I}$ with
matching $M$ there is a w-ha${}_{L}^{U}$ instance $\mathcal{I}^{\prime}$ on
the same graph, such that a matching is more popular than $M$ / dominates $M$
in $\mathcal{I}$ if and only if it has a larger weight than $M$ in
$\mathcal{I}^{\prime}$. The instance $\mathcal{I}^{\prime}$ can be computed in
polynomial time from $\mathcal{I}$.

###### Proof

As a sketch, we show the construction for the popv-ha${}_{L}^{U}$ case. The
exact calculations and the pov-ha${}_{L}^{U}$ case are in the appendix. We
start by defining a modified $\operatorname{vote}$ function. For applicant $a$
and projects $p_{1},p_{2}\in N_{a}$ let

$\operatorname{vote}_{a}(p_{1},p_{2})=\begin{cases*}2,&if
$p_{1}\succ_{a}p_{2}$,\\\ 1,&if $p_{1}=p_{2}$,\\\ 0,&if
$p_{2}\succ_{a}p_{1}$.\end{cases*}$

Note that based on the definition of popularity, matching $M^{\prime}$ is more
popular than matching $M$ if $\lvert\\{a\in A\mid
M^{\prime}(a)\succ_{a}M(a)\\}\rvert>\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert$, which is equivalent to
$\sum_{a~{}\in~{}A}\operatorname{vote}_{a}(M^{\prime}(a),M(a))>n$. Further,
let $U(M)\coloneqq\\{a\in A\mid M(a)=a\\}$ be the set of applicants left
unmatched by $M$.

For our weighted matching instance $\mathcal{I}^{\prime}$ we now take the same
graph as in the popv-ha${}_{L}^{U}$ instance $\mathcal{I}$, and introduce the
weight function $w\colon E\to\\{0,1,2\\}$ such that for any $a\in A\setminus
U(M)$ and project $p\in N_{a}$ we set
$w(\\{a,p\\})=\operatorname{vote}_{a}(p,M(a))$, further for any $a\in U(M)$
and project $p\in N_{a}$ we set $w(\\{a,p\\})=1$. We claim that a matching
$M^{\prime}$ is more popular than $M$ in $\mathcal{I}$ if and only if
$w(M^{\prime})>n-\lvert U(M)\rvert$ in $\mathcal{I}^{\prime}$. Since the
weight of $M$ in $\mathcal{I}^{\prime}$ is exactly $n-\lvert U(M)\rvert$, this
is sufficient to show. The intuition behind this is how agents contribute to
$w(M)$ and $w(M^{\prime})$.

  * •

each $a\in A$ with $M^{\prime}(a)\succ_{a}M(a)$ adds 1 to $w(M^{\prime})-w(M)$

  * •

each $a\in A$ with $M(a)\succ_{a}M^{\prime}(a)$ subtracts 1 from
$w(M^{\prime})-w(M)$

  * •

each $a\in A$ with $M^{\prime}(a)=M(a)$ contributes the same to $w(M)$ and
$w(M)$

Thus $w(M^{\prime})>w(M)$ is achieved if and only if $M^{\prime}$ is more
popular than $M$.

##  4 Constant lower quotas

In this section, we show that all four of our problems become intractable when
the maximum lower quota is $3$ and the maximum degree is constant.
Furthermore, pop-ha${}_{L}^{U}$ is -complete even if the maximum lower quota
is $2$. We contrast this result by showing that the other three problems
become polynomial-time solvable if the maximum lower quota is $2$.

###  4.1 Lower quota $3$

We begin by showing that all our problems are hard for maximum lower quota $3$
by modifying a reduction from exact cover by 3-sets by Cechlárová and Fleiner
[17, Theorem 6] for their -hardness proof of pov-ha${}_{L}^{U}$.

Exact Cover by $3$-Sets (x3c)

Input: |  Set $X=\\{x_{1},\dots,x_{3m}\\}$ and set-system $\mathcal{T}=\\{T_{1},\dots,T_{n}\\}\subseteq 2^{X}$ such that $\lvert T_{i}\rvert=3$ for all $i\in[n]$.
---|---
Question: |  Is there a subset $T^{\prime}\subseteq\mathcal{T}$ such that $T^{\prime}$ is a partition of $X$?

###### Theorem 1

The problems popv-ha${}_{L}^{U}$ and perpo-ha${}_{L}^{U}$ are $\NP$-complete,
while pop-ha${}_{L}^{U}$ is -hard when $l_{\text{max}}=3=u_{\text{max}}$.

###  4.2 Lower quota $2$

Next we complement the results of Section 4.1 and show that all problems
except for pop-ha${}_{L}^{U}$ become polynomial-time solvable, while pop-
ha${}_{L}^{U}$ remains -complete for lower quota $2$. For this we use the
general factor problem and a recent result from the world of factor theory.

general factor problem

Input: |  Graph $G=(V,E)$ with edge weights $w\colon E\to\mathbb{R}$ and demands $B_{v}\subseteq\\{0,\dots,\lvert V\rvert\\}$ for each $v\in V$.
---|---
Task: |  Find a subgraph $H$ of maximum weight such that $\deg_{H}(v)\in B_{v}$, for each $v\in V$, where $\deg_{H}(v)$ is the degree of the vertex $v$ in $H$.

In a recent paper by Dudycz and Paluch [21], a pseudo-polynomial algorithm was
given for the restricted case where the maximum gap, i.e., the maximum number
of missing adjacent values in any degree list $B_{v}$, is at most $1$.

######  Proposition 1 (Dudycz and Paluch [21])

If there is no $v\in V$ and $p\geq 2$ such that $k\in B_{v}$,
$k+1,\dots,k+p\notin B_{v}$ and $k+p+1\in B_{v}$, then the general factor
problem can be solved in $\mathcal{O}(W\lvert E\rvert\,\lvert V\rvert^{6})$
time, where $W$ is the maximum edge weight.

This theorem leads to the following corollary.

###### Corollary 1

Given a w-ha${}_{L}^{U}$ instance with $l_{\text{max}}=2$, a maximum weight
matching can be computed in polynomial time if the highest edge weight is
polynomial in the size of the graph.

###### Proof

This immediately follows by setting $B_{a}=\\{0,1\\}$ for each applicant $a\in
A$ and $B_{p}=\\{0,\ell_{p},\dots,u_{p}\\}$ 111Note that in the paper of
Cechlárová and Fleiner [17], the applicants technically had capacities as
well, which can be easily implemented by setting $B_{a}=\\{0,\dots,c(a)\\}$
for each applicant $a$ with capacity $c(a)$. for each project $p\in P$. Since
$\ell_{p}\leq 2$, the gaps are of size at most $1$. ∎

Next we show how to combine the methods of Cornuéjols [18] and Dudycz and
Paluch [21] to design a faster algorithm for our special case, which is also
easier to implement by giving a Turing reduction to the maximum weight
matching problem in graphs without quotas. This reduction is achieved by
constructing gadgets similar to the one designed by Cornuéjols [18] and by
exploiting a key lemma of Dudycz and Paluch [21] on the existence of
augmenting paths and the structure of larger weight matchings.

###### Theorem 2

popv-ha${}_{L}^{U}$ and pov-ha${}_{L}^{U}$ can be solved in
$\mathcal{O}(\lvert V\rvert^{3}\lvert E\rvert)$ time, while perpo-
ha${}_{L}^{U}$ can be solved in $\mathcal{O}(\lvert V\rvert^{3}\lvert
E\rvert^{2})$ time if $l_{\text{max}}=2$.

Following this, we show that it is $\NP$-complete to determine whether a
popular matching exists if $l_{\text{max}}=2=u_{\text{max}}$. For this we use
a simple graph transformation with which popular matchings in non-bipartite
instances translate to popular matchings with lower quota $2$.

###### Theorem 3

pop-ha${}_{L}^{U}$ is $\NP$-complete even if $l_{\text{max}}=2=u_{\text{max}}$
and $\Delta_{P}=2$.

##  5 Parameterized complexity

In this section we study the parameterized complexity of our four problems
with regard to five different parameters. These parameters are identical to
the ones used by Boehmer and Heeger [11]: $n$, the number of applicants, $m$,
the number of projects, $m_{\text{quota}}$, the number of projects with a
lower quota greater than $1$, $m_{\text{closed}}$, the number of closed
projects in the matching, and finally, $m_{\text{open}}$, the number of open
projects in the matching. In real life instances, one would expect the number
of projects being allocated to be small in comparison to the number of
students. Depending on the instance, either $m_{\text{open}}$ or
$m_{\text{closed}}$ would seem like a very suitable candidate for a
parameterized algorithm. On the other hand, while $n$ is often large, our
${\mathrm{W[1]}}$-hardness result for this parameter for pop-ha${}_{L}^{U}$
eliminates the possibility of any fixed parameter algorithm for any smaller,
maybe more realistic, sub-parameter of $n$. For a brief introduction to
parameterized complexity we refer to Section 7.1 in the appendix.

###  5.1 Parameterization by $n$

First we observe the following theorem from Arulselvan et al. [2, Theorem 4],
which was later improved by Marx et al. [35].

######  Proposition 2 (Arulselvan et al. [2])

In an instance $\mathcal{I}$ of w-ha${}_{L}^{U}$ such that the underlying
graph has a treewidth $\mathbf{tw}$, a maximum weight matching can be found in
$\FPT$ time in $\mathbf{tw}+u_{\text{max}}$.

From this proposition, the inequalities $\mathbf{tw}\leq\min(n,m)$ and
$u_{\text{max}}\leq n$, and our results in Section 3 follows the fixed
parameter tractability with regard to the parameter $n$.

###### Corollary 2

w-ha${}_{L}^{U}$, popv-ha${}_{L}^{U}$, pov-ha${}_{L}^{U}$, and perpo-
ha${}_{L}^{U}$ are in $\FPT$ when parameterized by $n$.

While this result relies on the machinery of tree decompositions and
treewidth, we further complement this result by showing that the maximum
weight matching admits a kernelization if the weights are encoded in unary.
For this we exploit that if a subset of applicants could be matched to more
than $n$ different projects achieving the same weight, then we can delete at
least one of these projects and not change the maximum weight we can reach in
the instance.

###### Observation 1

An instance of w-ha${}_{L}^{U}$ with maximum weight $W$ admits a kernelization
with $\mathcal{O}(2^{n}n^{2}W)$ applicants and projects.

Even though it follows from the above observation that the other three
considered problems become fixed parameter tractable when parameterized by
$n$, pop-ha${}_{L}^{U}$ remains ${\mathrm{W[1]}}$-hard. We show this by
modifying of the proof of Boehmer and Heeger [11, Theorem 2], who reduce from
the classic multicolored independent set problem to prove that finding a
stable matching is W[1]-hard when parameterized by $n$.

###### Theorem 4

pop-ha${}_{L}^{U}$ parameterized by $n$ is ${\mathrm{W[1]}}$-hard.

###  5.2 Parameterization by $m$

Next we turn to pop-ha${}_{L}^{U}$ and show that the problem becomes fixed
parameter tractable when parameterized by the number of projects $m$. For this
we show how to reduce pop-ha${}_{L}^{U}$ to the parametric integer program
problem.

parametric integer program

Input: |  Matrices $B\in\mathbb{Q}^{n\times m},C\in\mathbb{R}^{m\times k}$, and a vector $d\in\mathbb{R}^{k}$.
---|---
Question: |  For any $b\in\mathbb{Z}^{m}$, such that $Cb\leq d$, does there exist an $x\in\mathbb{Z}^{n}$ such that $Bx\leq b$?

The feasibility of a parametric integer program can be decided in
$\mathcal{O}(f(n,m)poly(\lvert\lvert B,C,d\rvert\rvert_{\infty},k))$ time, as
shown by Eisenbrand and Shmonin [22]. Using this we can now show that pop-
ha${}_{L}^{U}$ is indeed in FPT when parameterized by $m$. We first construct
a matrix $C$ and vector $d$ such that all feasible matchings are represented
by solutions to $Cb\leq d$. Then we construct the matrix $B$ such that any
solution to $Bx\leq b$ represents a feasible matching that is more popular
than the matching represented by $b$, thus ensuring that the parametric
integer program is feasible if and only if no popular matching exists. To
bound the dimensions of the matrices we use that we can assign each agent a
type based on their preferences, of which there can be at most
$\mathcal{O}((m+1)!)$.

###### Theorem 5

pop-ha${}_{L}^{U}$ is in ${\mathrm{FPT}}$ when parameterized by $m$.

###### Proof

Our goal is to encode the matching instance in such a way that the resulting
parametric integer program is feasible if and only if no popular matching
exists. For this we choose the matrix $B$ and vector $d$ so that all possible
matchings can be represented by a vector $b$ satisfying $Cb\leq d$. Further
the matrix $B$ should be chosen in such a way that the vector $x$ represents a
matching that is more popular than the matching represented by $b$.

####  5.2.1 Notation

Since we parameterize by $m$, each applicant $a\in A$ can be uniquely
identified by her preference structure over $P$. There are at most
$\mathcal{O}((m+1)!)$ different preference structures, hence we can partition
$A$ into $t\in\mathcal{O}((m+1)!)$ types. Let $A_{1},\dots,A_{t}$ be this
partition such that any two applicants in the same set have identical
preference lists. We refer to the projects that appear in the preference lists
of applicants in $A_{i}$ as $N_{i}$. Furthermore we slightly alter the
notation of the previous sections to follow [10] and define the vote of a
vertex as

$\operatorname{vote}_{a}(p_{1},p_{2})=\begin{cases*}1,&if
$p_{1}\succ_{a}p_{2}$,\\\ 0,&if $p_{1}=p_{2}$,\\\ -1,&if
$p_{2}\succ_{a}p_{1}$.\end{cases*}$

By the definition of popularity, matching $M^{\prime}$ is more popular than
$M$ if and only if $\sum_{a\in
A}\operatorname{vote}_{a}(M^{\prime}(a),M(a))\geq 1$ holds. For easier
notation for any type $i\in[t]$ we define
$\operatorname{vote}_{i}(p_{1},p_{2})=\operatorname{vote}_{a}(p_{1},p_{2})$
where $a\in A_{i}$ is an applicant of type $i$.

####  5.2.2 Construction of $C$

As noted earlier, our goal is to construct the linear program represented by
$B$ and $d$ in such a way that every feasible matching is a solution to this
linear program. To reach this, for each $i\in[t]$ and $p\in N_{i}$ we create a
variable $x_{i}^{p}$ that should indicate how many applicants of type $A_{i}$
are matched to project $p$. Moreover we add one variable $x_{i}^{i}$
indicating the number of unmatched applicants of type $i$. Furthermore for
each project $p\in P$ we create a variable $o_{p}$ that should indicate
whether project $p$ is open or closed. This now leads us to the following
linear program

$\displaystyle\displaystyle\sum\limits_{p\in N_{i}\cup\\{i\\}}x_{i}^{p}$
$\displaystyle=$ $\displaystyle\lvert A_{i}\rvert,\quad$ for each $i\in[t]$
(1) $\displaystyle\displaystyle\sum\limits_{i\in[t]\colon p\in
N_{i}}x_{i}^{p}-o_{p}u_{p}$ $\displaystyle\leq$ $\displaystyle 0,\quad$ for
each $p\in P$ (2) $\displaystyle\displaystyle\sum\limits_{i\in[t]\colon p\in
N_{i}}x_{i}^{p}-o_{p}\ell_{p}$ $\displaystyle\geq$ $\displaystyle 0,\quad$ for
each $p\in P$ (3) $\displaystyle x_{i}^{p}$ $\displaystyle\geq$ $\displaystyle
0,\quad$ for each $i\in[t]$ and $p\in N_{i}$ (4) $\displaystyle o_{p}$
$\displaystyle\in$ $\displaystyle[0,1],\quad$ for each $p\in P$ (5)

Here Constraint (1) enforces that all applicants are either matched or
unmatched. With Constraints (2) and (3) we ensure that the number of
applicants matched to an open project is between its lower and upper quota and
the number of applicants matched to a closed project is $0$. Note that each
feasible matching is a solution to this ILP. Currently, any solution to this
ILP is of the form
$(x_{1}^{p_{1}},\dots,x_{t}^{p_{m}},o_{p_{1}},\dots,o_{p_{m}})$. This,
however, is not enough to fully model the ILP we need for $B$. As a first
step, for each variable of the form $x_{i}^{p}$ we add a second copy.
Furthermore we add $2t$ variables $b_{1},\dots,b_{2t}$ with $b_{2i}=\lvert
A_{i}\rvert=b_{2i+1}$, then we add $2m$ variables that are forced to be $0$,
and one variable that is forced to be $-1$. After this, each solution $b$ is
of the form $(\lvert A_{1}\rvert,\lvert A_{1}\rvert,\dots,\lvert
A_{t}\rvert,\lvert
A_{t}\rvert,x_{1}^{p_{1}},x_{1}^{p_{1}},\dots,x_{t}^{p_{m}},x_{t}^{p_{m}},o_{p_{1}},\dots,o_{p_{m}},\underbrace{0,\dots,0}_{2m\text{
times}},-1)$.

####  5.2.3 Construction of $B$

We design $B$ to ensure that there is a matching $M^{\prime}$ that is more
popular than the matching $M$ induced by $b$. For any type $i\in[t]$ and
projects $p,p^{\prime}\in N_{i}\cup\\{i\\}$, we create a variable
$x_{i}^{p\rightarrow p^{\prime}}$ that should indicate the number of
applicants of type $i$ who were matched to project $p$ in $M$ and are matched
to project $p^{\prime}$ in $M^{\prime}$. Furthermore, for each project $p\in
P$, we again create a variable $o^{\prime}_{p}$ indicating whether project $p$
is open or closed in $M^{\prime}$. This now allows us to construct the final
ILP.

$\displaystyle\displaystyle\sum\limits_{p,p^{\prime}\in
N_{i}\cup\\{i\\}}x_{i}^{p\rightarrow p^{\prime}}$ $\displaystyle=$
$\displaystyle\lvert A_{i}\rvert,\quad$ for each $i\in[t]$ (6)
$\displaystyle\displaystyle\sum\limits_{p^{\prime}\in
P\cup\\{i\\}}x_{i}^{p\rightarrow p^{\prime}}$ $\displaystyle=$ $\displaystyle
x_{i}^{p},\quad$ for each $i\in[t]$ and $p\in N_{i}$ (7)
$\displaystyle\displaystyle\sum\limits_{i\in[t],p\in P}x_{i}^{p\rightarrow
p^{\prime}}-o^{\prime}_{p^{\prime}}u_{p^{\prime}}$ $\displaystyle\leq$
$\displaystyle 0,\quad$ for each $p^{\prime}\in P$ (8)
$\displaystyle\displaystyle\sum\limits_{i\in[t],p\in P}x_{i}^{p\rightarrow
p^{\prime}}-o^{\prime}_{p^{\prime}}\ell_{p^{\prime}}$ $\displaystyle\geq$
$\displaystyle 0,\quad$ for each $p^{\prime}\in P$ (9)
$\displaystyle\displaystyle\sum\limits_{i\in[t]p,p^{\prime}\in
N_{i}\cup\\{i\\}}-\operatorname{vote}_{i}(p^{\prime},p)x_{i}^{p\rightarrow
p^{\prime}}$ $\displaystyle\leq$ $\displaystyle-1,$ (10) $\displaystyle
x_{i}^{p\rightarrow p^{\prime}}$ $\displaystyle\geq$ $\displaystyle 0,\quad$
for each $i\in[t]$ and $p,p^{\prime}\in N_{i}$ (11) $\displaystyle
o^{\prime}_{p}$ $\displaystyle\in$ $\displaystyle[0,1],\quad$ for each $p\in
P$ (12)

Constraint (6) ensures that each applicant has a new partner in $M^{\prime}$,
and Constraint (7) guarantees that each applicant matched to some $p$ in $M$
now has a new partner. Constraints (8) and (9) enforce the lower and upper
quota constraints, and finally Constraint (10) ensures that $M^{\prime}$ is
more popular than $M$.

###  5.3 Parameterization by $m_{\text{quota}}$

While for pop-ha${}_{L}^{U}$ we were able to show fixed parameter tractability
with regard to $m$, we now improve this parameter for the other three problems
by considering $m_{\text{quota}}$, i.e., the number of projects with a lower
quota greater than $1$. In order to solve this problem we turn to a special
subcase of our matching problems defined by Boehmer and Heeger [11], namely
the task of deciding whether, given a certain set of projects
$P_{\text{open}}$, there is a matching with our desired property that opens
exactly the projects in $P_{\text{open}}$. We show that finding a maximum
weight matching that opens exactly the projects in $P_{\text{open}}$ is
polynomial-time solvable. First we give an algorithm for simply finding a
matching that dominates a given matching and afterwards we modify this
algorithm to find a maximum weight matching. For this algorithm we utilize the
feasible flow with demands problem, which can easily be reduced to the well-
known maximum flow problem, as argued for instance in the textbook of Erickson
[24].

feasible flow with demands

Input: |  Directed graph $G=(V,E)$, capacities $C\colon E\to\mathbb{N}$, and demands $D\colon E\to\mathbb{N}$.
---|---
Question: |  Is there a flow $f\colon E\to\mathbb{N}$ such that $D(e)\leq f(e)\leq C(e)$ for all $e\in E$?

###### Theorem 6

Given an instance $\mathcal{I}$ of pov-ha${}_{L}^{U}$ with input matching $M$
and a set $P_{\text{open}}\subseteq P$, we can decide in polynomial time
whether a matching $M^{\prime}$ exists that dominates $M$ and opens exactly
the projects in the set $P_{\text{open}}$.

###### Proof

We construct an instance of feasible flow with demands to solve the problem.
The proof of correctness for this construction is in the appendix. First we
assume that some $a\in A$ is given who will be the designated applicant to
receive a better partner in $M^{\prime}$. Now we create a directed bipartite
graph $G_{a}$ with vertices $A\cup P_{\text{open}}\cup\\{p_{\perp},s,t\\}$,
where $p_{\perp}$ will represent the unmatched applicants. We connect $s$ to
all vertices in $A$ with demand and capacity of $1$ on the edge. Next we
connect $a$ to all projects in $P_{\text{open}}$ that $a$ prefers to $M(a)$
and all applicants in $A\setminus\\{a\\}$ get connected to all projects in
$P_{\text{open}}$ which they prefer to $M(a)$ as well as to $M(a)$ if $M(a)$
is in $P_{\text{open}}$, further if they are unmatched in $M$, we also connect
them to $p_{\perp}$. All of these edges have no demand and a capacity of $1$.
Finally we connect every project $p\in P_{\text{open}}$ to $t$, each with a
demand of $\ell_{p}$ and with a capacity of $u_{p}$ and we connect $p_{\perp}$
to $t$ with no demand and infinite capacity. We solve the feasible flow with
demands problem for all $a\in A$ in $G_{a}$ and if some $a\in A$ exists for
which the demands are satisfiable, we return the respective induced matching
as $M^{\prime}$. That is, if a flow of $1$ goes from $a$ to $p$, we match $a$
to $p$ in $M^{\prime}$ and if a flow of $1$ goes from $a$ to $p_{\perp}$, we
leave $a$ unmatched in $M^{\prime}$. Otherwise we return that our matching is
Pareto optimal.

$\phantom{1111}\ell_{p_{1}}=$ | 1 = | $u_{p_{1}}$
---|---|---
$\ell_{p_{2}}=$ | 3 = | $u_{p_{2}}$
$\ell_{p_{3}}=$ | 2, | $u_{p_{3}}=4$
$\ell_{p_{4}}=$ | 2 = | $u_{p_{4}}$
$\displaystyle a_{1}\colon$ $\displaystyle p_{2}\succ p_{1}\succ p_{3}$
$\displaystyle a_{2}\colon$ $\displaystyle p_{2}\succ p_{4}$ $\displaystyle
a_{3}\colon$ $\displaystyle p_{3}\succ p_{2}\succ p_{4}$ $\displaystyle
a_{4}\colon$ $\displaystyle p_{3}$

Figure 1: Consider an instance of pov-ha${}_{L}^{U}$ with four applicants
$a_{1},\dots,a_{4}$ and four projects $p_{1},\dots,p_{4}$ with quotas and
preference lists as shown on the right side of the figure. If we consider the
matching $M(a_{1})=p_{1},M(a_{2})=p_{4},M(a_{3})=p_{4}$, and $M(a_{4})=a_{4}$
with $P_{\text{open}}=\\{p_{1},p_{2},p_{3}\\}$, the above instance is the
feasible flow with demands instance created in Theorem 6.

Next we show how to generalize this idea to prove that finding a maximum
weight matching that opens exactly the projects in $P_{\text{open}}$ can be
done in polynomial time. For this we need the slightly more complicated but
still polynomial-time solvable max-cost circulation problem, see Tardos [43].

max-cost circulation

Input: |  Directed graph $G=(V,E)$, costs $p\colon E\to\mathbb{R}$, capacities $C\colon E\to\mathbb{N}$, and demands $D\colon E\to\mathbb{N}$.
---|---
Task: |  Find a flow $f\colon E\to\mathbb{N}$ of maximum cost such that for any $v\in V$ it holds that $\sum_{(v,w)\in E}f((v,w))-\sum_{(w,v)\in E}f((w,v))=0$, i.e., all flow gets conserved and such that for any edge $e\in E$ it holds that $D(e)\leq f(e)\leq C(e)$.

###### Theorem 7

Given an instance $\mathcal{I}$ of w-ha${}_{L}^{U}$ and a set
$P_{\text{open}}\subseteq P$, we can find in polynomial time a maximum weight
matching that opens exactly the projects in $P_{\text{open}}$.

Using this theorem, we can calculate maximum weight matchings in FPT time in
$m_{\text{quota}}$. To do so, we use the fact that projects with a lower quota
of at most $1$ are always open and then iterate through all projects with a
lower quota of at least $2$.

###### Theorem 8

Given an instance $\mathcal{I}$ of w-ha${}_{L}^{U}$, a maximum weight matching
can be computed in
$\mathcal{O}(2^{m_{\text{quota}}}poly(\lvert\mathcal{I}\rvert))$, where
$\lvert\mathcal{I}\rvert=nm+$ the input size of the weights.

Using the lemmas in Section 3 this now implies that popv-ha${}_{L}^{U}$,
perpo-ha${}_{L}^{U}$, and pov-ha${}_{L}^{U}$ are all fixed parameter tractable
when parameterized bz $m_{\text{quota}}$.

###  5.4 Parameterization by $m_{\text{open}}$

The next parameter we investigate is $m_{\text{open}}$, the number of projects
that are open in the output matching. We show hardness for all our problems,
by reducing from either x3c or the exact unique hitting set problem.

###### Theorem 9

Given an instance $\mathcal{I}$ of pov-ha${}_{L}^{U}$/popv-ha${}_{L}^{U}$ with
a matching $M$ and a parameter $m_{\text{open}}$, it is both
${\mathrm{W}}[1]$-hard to decide whether there is a matching that dominates /
is more popular than $M$ and opens exactly $m_{\text{open}}$ projects. This
remains true even if $M$ opens exactly $1$ project.

This approach also generalizes to pop-ha${}_{L}^{U}$ and perpo-ha${}_{L}^{U}$
with the difference that here it is even hard to decide whether there is a
desired matching with only one open project.

###### Theorem 10

Given an instance $\mathcal{I}$ of pop-ha${}_{L}^{U}$/perpo-ha${}_{L}^{U}$, it
is -hard to decide whether there is a popular / perfect Pareto optimal
matching that opens exactly $1$ project.

As a corollary of our previous proof, we obtain that given a set
$P_{\text{open}}\subseteq P$, it is -hard to determine whether a perfect
Pareto optimal matching or a popular matching opening exactly the projects in
$P_{\text{open}}$ exists.

###### Corollary 3

Deciding whether there exists a popular matching / perfect Pareto optimal
matching that opens exactly the projects in a given subset
$P_{\text{open}}\subseteq P$ is -hard, even if $\lvert
P_{\text{open}}\rvert=1$. 222Note that this is not a contradiction to Theorem
7, since given an instance of perpo-ha${}_{L}^{U}$, a maximum weight matching
opening only projects in $P_{\text{open}}$ does not need to correspond to a
perfect Pareto optimal matching and vice versa.

###  5.5 Parameterization by $m_{\text{closed}}$

As our final parameter we turn to $m_{\text{closed}}$, the number of closed
projects in our desired matching and show that all four problems become
W[1]-hard when parameterized by $m_{\text{closed}}$. For these results we
reduce from the classic problems multicolored independent set and multicolored
clique.

###### Theorem 11

Given an instance $\mathcal{I}$ of perpo-ha${}_{L}^{U}$, pov-ha${}_{L}^{U}$,
pop-ha${}_{L}^{U}$, or popv-ha${}_{L}^{U}$ and parameter $m_{\text{closed}}$,
it is ${\mathrm{W[1]}}$-hard to decide whether a matching of our desired type
exists that closes exactly $m_{\text{closed}}$ projects.

##  6 Open questions

There are two major open questions and future research directions that could
be derived from our paper. Firstly, the question whether pop-ha${}_{L}^{U}$ is
in FPT when parameterized by $m_{\text{quota}}$ is still open. Secondly, even
after the papers of Arulselvan et al. [2], Dudycz and Paluch [21], and now our
paper it is still open whether w-ha${}_{L}^{U}$ with maximum lower quota $2$
or the general factor problem with gap at most $1$ can be solved in polynomial
time, i.e., by eliminating the linear factor on $W$, the largest weight.

## References

  * Abraham et al. [2004] Abraham, D.J., Cechlárová, K., Manlove, D.F., Mehlhorn, K.: Pareto optimality in house allocation problems. In: ISAAC’04, pp. 3–15 (2004)
  * Arulselvan et al. [2018] Arulselvan, A., Cseh, Á., Groß, M., Manlove, D.F., Matuschke, J.: Matchings with lower quotas: algorithms and complexity. Algorithmica 80(1), 185–208 (2018)
  * Aziz et al. [2021a] Aziz, H., Biró, P., Yokoo, M.: Matching market design with constraints. Tech. rep., UNSW Sydney (2021a), URL http://www.cse.unsw.edu.au/~haziz/matching_survey.pdf
  * Aziz et al. [2013] Aziz, H., Brandt, F., Harrenstein, P.: Pareto optimality in coalition formation. Games and Economic Behavior 82, 562–581 (2013)
  * Aziz et al. [2021b] Aziz, H., Chan, H., Cseh, Á., Li, B., Ramezani, F., Wang, C.: Multi-robot task allocation–complexity and approximation. In: AAMAS’21 (2021b)
  * Aziz et al. [2018] Aziz, H., Chen, J., Gaspers, S., Sun, Z.: Stability and Pareto optimality in refugee allocation matchings. In: AAMAS’18, pp. 964–972 (2018)
  * Balliu et al. [2017] Balliu, A., Flammini, M., Olivetti, D.: On Pareto optimality in social distance games. In: AAAI’17, pp. 349–355 (2017)
  * Biró et al. [2010a] Biró, P., Fleiner, T., Irving, R.W., Manlove, D.F.: The College Admissions problem with lower and common quotas. Theoretical Computer Science 411, 3136–3153 (2010a)
  * Biró and Gudmundsson [2020] Biró, P., Gudmundsson, J.: Complexity of finding Pareto-efficient allocations of highest welfare. European Journal of Operational Research (2020)
  * Biró et al. [2010b] Biró, P., Irving, R.W., Manlove, D.F.: Popular matchings in the marriage and roommates problems. In: CIAC ’10, pp. 97–108 (2010b)
  * Boehmer and Heeger [2020] Boehmer, N., Heeger, K.: A fine-grained view on stable many-to-one matching problems with lower and upper quotas. In: WINE’20, pp. 31–44 (2020)
  * Brandl and Kavitha [2019] Brandl, F., Kavitha, T.: Two problems in max-size popular matchings. Algorithmica 81(7), 2738–2764 (2019)
  * Bullinger [2020] Bullinger, M.: Pareto-optimality in cardinal hedonic games. In: AAMAS’20, pp. 213–221 (2020)
  * de Caen [1998] de Caen, D.: An upper bound on the sum of squares of degrees in a graph. Discrete Mathematics 185(1-3), 245–248 (1998)
  * Cechlárová et al. [2016] Cechlárová, K., Eirinakis, P., Fleiner, T., Magos, D., Manlove, D., Mourtos, I., Oceláková, E., Rastegari, B.: Pareto optimal matchings in many-to-many markets with ties. Theory of Computing Systems 59(4), 700–721 (2016)
  * Cechlárová et al. [2014] Cechlárová, K., Eirinakis, P., Fleiner, T., Magos, D., Mourtos, I., Potpinková, E.: Pareto optimality in many-to-many matching problems. Discrete Optimization 14, 160–169 (2014)
  * Cechlárová and Fleiner [2017] Cechlárová, K., Fleiner, T.: Pareto optimal matchings with lower quotas. Mathematical Social Sciences 88, 3–10 (2017)
  * Cornuéjols [1988] Cornuéjols, G.: General factors of graphs. Journal of Combinatorial Theory, Series B 45(2), 185–198 (1988)
  * Cseh [2017] Cseh, Á.: Popular matchings. Trends in Computational Social Choice 105(3) (2017)
  * Cygan et al. [2015] Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms, vol. 4. Springer (2015)
  * Dudycz and Paluch [2018] Dudycz, S., Paluch, K.: Optimal general matchings. In: WG’18, pp. 176–189 (2018)
  * Eisenbrand and Shmonin [2008] Eisenbrand, F., Shmonin, G.: Parametric integer programming in fixed dimension. Mathematics of Operations Research 33(4), 839–850 (2008)
  * Elkind et al. [2020] Elkind, E., Fanelli, A., Flammini, M.: Price of Pareto optimality in hedonic games. Artificial Intelligence 288, 103357 (2020)
  * Erickson [2019] Erickson, J.: Algorithms (2019), ISBN 978-1-792-64483-2, URL http://jeffe.cs.illinois.edu/teaching/algorithms/
  * Faenza et al. [2019] Faenza, Y., Kavitha, T., Powers, V., Zhang, X.: Popular matchings and limits to tractability. In: SODA’19, pp. 2790–2809 (2019)
  * Gale and Shapley [1962] Gale, D., Shapley, L.S.: College admissions and the stability of marriage. The American Mathematical Monthly 69(1), 9–15 (1962)
  * Garey and Johnson [1979] Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco, CA. (1979)
  * Gopal et al. [2019] Gopal, K., Nasre, M., Nimbhorkar, P., Reddy, T.P.: Many-to-one popular matchings with two-sided preferences and one-sided ties. In: International Computing and Combinatorics Conference, pp. 193–205, Springer (2019)
  * Goto et al. [2014] Goto, M., Hashimoto, N., Iwasaki, A., Kawasaki, Y., Ueda, S., Yasuda, Y., Yokoo, M.: Strategy-proof matching with regional minimum quotas. In: AAMAS’14, pp. 1225–1232 (2014)
  * Gupta et al. [2021] Gupta, S., Misra, P., Saurabh, S., Zehavi, M.: Popular matching in roommates setting is NP-hard. ACM Transactions on Computation Theory (TOCT) 13(2), 1–20 (2021)
  * Gusfield and Irving [1989] Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press (1989)
  * Hamada et al. [2016] Hamada, K., Iwama, K., Miyazaki, S.: The hospitals/residents problem with lower quotas. Algorithmica 74(1), 440–465 (2016)
  * Kamiyama [2013] Kamiyama, N.: A note on the serial dictatorship with project closures. Operations Research Letters 41(5), 559–561 (2013)
  * Krishnapriya et al. [2018] Krishnapriya, A., Nasre, M., Nimbhorkar, P., Rawat, A.: How good are popular matchings? In: SEA’18 (2018)
  * Marx et al. [2021] Marx, D., Sankar, G.S., Schepper, P.: Degrees and gaps: Tight complexity results of general factor problems parameterized by treewidth and cutwidth. In: ICALP’21 (2021)
  * Mnich and Schlotter [2020] Mnich, M., Schlotter, I.: Stable matchings with covering constraints: A complete computational trichotomy. Algorithmica pp. 1–53 (2020)
  * Monte and Tumennasan [2013] Monte, D., Tumennasan, N.: Matching with quorums. Economics Letters 120(1), 14–17 (2013)
  * Nasre and Nimbhorkar [2018] Nasre, M., Nimbhorkar, P.: Popular matchings with lower quotas. In: FSTTCS’18, pp. 9:1–9:14 (2018)
  * Pietrzak [2003] Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences 67(4), 757–771 (2003)
  * Sanchez-Anguix et al. [2019] Sanchez-Anguix, V., Chalumuri, R., Aydoğan, R., Julian, V.: A near Pareto optimal approach to student–supervisor allocation with two sided preferences and workload balance. Applied Soft Computing 76, 1–15 (2019)
  * Schrijver [2003] Schrijver, A.: Combinatorial optimization: Polyhedra and efficiency, vol. 24. Springer Science & Business Media (2003)
  * Sng and Manlove [2010] Sng, C.T., Manlove, D.F.: Popular matchings in the weighted capacitated house allocation problem. Journal of Discrete Algorithms 8, 102–116 (2010)
  * Tardos [1985] Tardos, É.: A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3), 247–255 (1985)

##  7 Appendix

###  7.1 Parameterized complexity

Here we provide a short overview of parameterized complexity and the problems
we use in our reductions. For further background on parameterized complexity
and algorithms we refer the reader to the textbook by Cygan et al. [20].

A parameterized problem consists of two parts, the instance $\mathcal{I}$ and
a parameter $k$. The problem is in FPT (and called fixed parameter tractable)
if there is some algorithm solving it in time
$\mathcal{O}(f(k)\lvert\mathcal{I}\rvert^{\mathcal{O}(1)})$ for some
computable function $f$. A parameterized problem $P$ is reducible to another
parameterized problem $\hat{P}$ if there is some function $f$ that can be
computed in time $\mathcal{O}(g(k)\lvert\mathcal{I}\rvert^{\mathcal{O}(1)})$
for some computable function $g$, such that $(\mathcal{I},k)\in P$ if and only
if $f(\mathcal{I},k)=(\hat{\mathcal{I}},\hat{k})\in\hat{P}$ and $\hat{k}\leq
h(k)$ for some computable function $h$. It is easy to see that if $\hat{P}$ is
in FPT, then so is $P$ as well. Related to this is the concept of a
kernelization. Given an instance $(\mathcal{I},k)$ of a parameterized problem
$P$, a kernelization is an algorithm that computes another instance
$(\mathcal{I}^{\prime},k^{\prime})$ of $P$ in polynomial time, such that
$(\mathcal{I},k)\in P$ if and only if $(\mathcal{I}^{\prime},k^{\prime})\in P$
and $\mathcal{I}^{\prime}+k^{\prime}\leq f(k)$ for some computable function
$k$. This can be seen as applying provably correct data reductions. It is
commonly known that a problem $P$ is in FPT if and only if it has a
kernelization, see [20]. The class W[1] is now the class of all parameterized
problems that have a parameterized reduction to the clique problem,
parameterized by the solution size. We call a problem W[1]-hard if any problem
in W[1] can be reduced to it in FPT time, further we call a problem
W[1]-complete if it is W[1]-hard and also in W[1]. Since it is widely assumed
that clique is not in FPT, this assumption extends to all W[1]-hard problems.

The W[1]-complete problems we reduce from in this paper are as follows.
Firstly we use a highly restricted version of the hitting set problem.

Exact unique hitting set [20]

Input: |  Set of elements $X$, set system $\mathcal{T}\subseteq 2^{X}$, parameter $k$.
---|---
Question: |  Is there a set $H\subseteq X$ with $\lvert H\rvert=k$, such that $\lvert T\cap H\rvert=1$ for all $T\in\mathcal{T}$?

Furthermore due to their nice structural properties we use the multicolored
versions of independent set and clique, shown to be W[1]-complete by Pietrzak
[39].

Multicolored clique

Input: |  Graph $G=(V,E)$ and partition $V_{1},\dots,V_{k}$ of $V$.
---|---
Question: |  Is there a clique $C\subseteq V$, i.e., a vertex set inducing a complete graph, such that $\lvert V_{c}\cap C\rvert=1$ for all $c\in[k]$?

Multicolored independent set

Input: |  Graph $G=(V,E)$ and partition $V_{1},\dots,V_{k}$ of $V$.
---|---
Question: |  Is there an independent set $I\subseteq V$, i.e., a vertex set inducing a graph without any edges, such that $\lvert V_{c}\cap I\rvert=1$ for all $c\in[k]$?

###  7.2 Examples

We now present two characteristic instances we will later repeatedly use in
our proofs.

###### Observation 2

Consider the instance $\mathcal{I}$ of pop-ha${}_{L}^{U}$ with three
applicants $a_{1},a_{2},a_{3}$ and three projects $p_{1},p_{2},p_{3}$, each
with a lower and upper quota of $1$, such that the preference list of each
applicants is $p_{1}\succ p_{2}\succ p_{3}$. This instance does not admit a
popular matching.

###### Proof

A matching that is not perfect cannot be popular, since the matching obtained
by additionally pairing an unmatched applicant to an unmatched project is
preferred by this one applicant, while the other applicants are indifferent.
Since the instance is symmetric, we can assume without loss of generality that
if there is a popular matching then it is
${M=\\{(a_{1},p_{1}),(a_{2},p_{2}),(a_{3},p_{3})\\}}$. Let us consider the
matching $M^{\prime}=\\{(a_{1},p_{3}),(a_{2},p_{1}),(a_{3},p_{2})\\}$. Since
$M^{\prime}$ is preferred to $M$ by $a_{2}$ and $a_{3}$, while only $a_{1}$
prefers $M$ to $M^{\prime}$, $M^{\prime}$ is more popular than $M$. ∎

This also implies that for any instance containing three projects with lower
and upper quota $1$ and three applicants with the same relative preference
order over these three projects, in any popular matching, at least one
applicant needs to be matched to a project different from those three. Note
that if we would delete one of the three applicants, a popular matching would
indeed be possible, since we could match the remaining two applicants to
$p_{1}$ and $p_{2}$, thus ensuring that none of them could improve without the
other applicant getting worse. As the second example we introduce a small
gadget we also use in a later proof, which will also be an instance of the
famous Condorcet cycle.

###### Observation 3

Consider the instance $\mathcal{I}$ of pop-ha${}_{L}^{U}$ with three
applicants $a_{1},a_{2},a_{3}$ and three projects $p_{1},p_{2},p_{3}$, each
with a lower and upper quota of $3$, such that the preference list of $a_{1}$
is $p_{1}\succ_{a_{1}}p_{2}\succ_{a_{1}}p_{3}$, the preference list of $a_{2}$
is $p_{2}\succ_{a_{2}}p_{3}\succ_{a_{2}}p_{1}$ and the preference list of
$a_{3}$ is $p_{3}\succ_{a_{3}}p_{1}\succ_{a_{3}}p_{2}$, i.e., the preference
lists are just cyclically shifted between the applicants. This instance does
not admit a popular matching.

###### Proof

Any non-perfect matching has to be empty in this instance due to the lower
quota of $3$ on each project. Thus matching all three applicants to any of the
projects would lead to a matching that is preferred by all three applicants.
Therefore we only need to consider the three perfect matchings

  * •

$M_{1}$ with $M_{1}(p_{1})=\\{a_{1},a_{2},a_{3}\\}$,

  * •

$M_{2}$ with $M_{2}(p_{2})=\\{a_{1},a_{2},a_{3}\\}$,

  * •

$M_{3}$ with $M_{3}(p_{3})=\\{a_{1},a_{2},a_{3}\\}$.

Then the following statements hold.

  * •

The applicants $a_{2}$ and $a_{3}$ prefer $M_{3}$ to $M_{1}$, while $a_{1}$
prefers $M_{1}$ to $M_{3}$, making $M_{3}$ more popular than $M_{1}$.

  * •

The applicants $a_{1}$ and $a_{2}$ prefer $M_{2}$ to $M_{3}$, while $a_{3}$
prefers $M_{3}$ to $M_{2}$, making $M_{2}$ more popular than $M_{3}$.

  * •

The applicants $a_{1}$ and $a_{3}$ prefer $M_{1}$ to $M_{2}$, while $a_{2}$
prefers $M_{2}$ to $M_{1}$, making $M_{1}$ more popular than $M_{2}$.

Thus this instance admits no popular matching. ∎

###  7.3 Missing proof from Section 3

See 2

###### Proof

We start with the popv-ha${}_{L}^{U}$ case. For applicant $a$ and projects
$p_{1},p_{2}\in N_{a}$ let

$\operatorname{vote}_{a}(p_{1},p_{2})=\begin{cases*}2,&if
$p_{1}\succ_{a}p_{2}$,\\\ 1,&if $p_{1}=p_{2}$,\\\ 0,&if
$p_{2}\succ_{a}p_{1}$.\end{cases*}$

Note that based on the definition of popularity, matching $M^{\prime}$ is more
popular than matching $M$ if $\lvert\\{a\in A\mid
M^{\prime}(a)\succ_{a}M(a)\\}\rvert>\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert$ , which is equivalent to $\sum_{a\in
A}\operatorname{vote}_{a}(M^{\prime}(a),M(a))>n$. Further let
$U(M)\coloneqq\\{a\in A\mid M(a)=a\\}$ be the set of applicants left unmatched
by $M$.

####  7.3.1 Construction

For our weighted matching instance $\mathcal{I}^{\prime}$ we now take the same
graph as in the original instance $\mathcal{I}$, and introduce the weight
function $w\colon E\to\\{0,1,2\\}$ such that for any $a\in A\setminus U(M)$
and project $p\in N_{a}$ we set
$w(\\{a,p\\})=\operatorname{vote}_{a}(p,M(a))$, further for any $a\in U(M)$
and project $p\in N_{a}$ we set $w(\\{a,p\\})=1$. We claim that a matching
$M^{\prime}$ is more popular than $M$ in $\mathcal{I}$ if and only if
$w(M^{\prime})>n-\lvert U(M)\rvert$ in $\mathcal{I}^{\prime}$. Since the
weight of $M$ in $\mathcal{I}^{\prime}$ is exactly $n-\lvert U(M)\rvert$ this
is sufficient to show.

####  7.3.2 Correctness

Let $M^{\prime}$ be a matching that is more popular than $M$ in $\mathcal{I}$.
By the definition of popularity it holds that $\lvert\\{a\in A\mid
M^{\prime}(a)\succ_{a}M(a)\\}\rvert>\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert$. We now calculate the weight of
$M^{\prime}$ in $\mathcal{I}^{\prime}$.

$\displaystyle w(M^{\prime})$ $\displaystyle=2\lvert\\{a\in A\setminus
U(M)\mid M^{\prime}(a)\succ_{a}M(a)\\}\rvert+\lvert\\{a\in U(M)\mid
M^{\prime}(a)\succ_{a}a\\}\rvert$ $\displaystyle+\lvert\\{a\in A\setminus
U(M)\mid M^{\prime}(a)=M(a)\\}\rvert$
$\displaystyle\stackrel{{\scriptstyle(1)}}{{>}}\lvert\\{a\in A\setminus
U(M)\mid M^{\prime}(a)\succ_{a}M(a)\\}\rvert+\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert$ $\displaystyle+\lvert\\{a\in A\setminus
U(M)\mid M^{\prime}(a)=M(a)\\}\rvert$ $\displaystyle\geq\lvert\\{a\in
A\setminus U(M)\mid M^{\prime}(a)\succ_{a}M(a)\\}\rvert+\lvert\\{a\in
A\setminus U(M)\mid M(a)\succ_{a}M^{\prime}(a)\\}\rvert$
$\displaystyle+\lvert\\{a\in A\setminus U(M)\mid M^{\prime}(a)=M(a)\\}\rvert$
$\displaystyle=\lvert A\setminus U(M)\rvert$ $\displaystyle=n-\lvert
U(M)\rvert$

Inequality (1) follows from the fact that $\lvert\\{a\in A\setminus U(M)\mid
M^{\prime}(a)\succ_{a}M(a)\\}\rvert+\lvert\\{a\in U(M)\mid
M^{\prime}(a)\succ_{a}a\\}\rvert=\lvert\\{a\in A\mid
M^{\prime}(a)\succ_{a}M(a)\\}\rvert>\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert$.

Now assume that $M^{\prime}$ is not more popular than $M$ in $\mathcal{I}$.
Then by definition we know that $\lvert\\{a\in A\mid
M^{\prime}(a)\succ_{a}M(a)\\}\rvert\leq\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert$. By analogous calculations as in the
previous case we get the following.

$\displaystyle w(M^{\prime})$ $\displaystyle=2\lvert\\{a\in A\setminus
U(M)\mid M^{\prime}(a)\succ_{a}M(a)\\}\rvert+\lvert\\{a\in U(M)\mid
M^{\prime}(a)\succ_{a}a\\}\rvert$ $\displaystyle+\lvert\\{a\in A\setminus
U(M)\mid M^{\prime}(a)=M(a)\\}\rvert$
$\displaystyle\stackrel{{\scriptstyle(1)}}{{=}}n+\lvert\\{a\in A\setminus
U(M)\mid M^{\prime}(a)\succ_{a}M(a)\\}\rvert-\lvert\\{a\in U(M)\mid
M^{\prime}(a)=a\\}\rvert$ $\displaystyle-\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert$
$\displaystyle\stackrel{{\scriptstyle(2)}}{{=}}n+\lvert\\{a\in A\setminus
U(M)\mid M^{\prime}(a)\succ_{a}M(a)\\}\rvert+\lvert\\{a\in U(M)\mid
M^{\prime}(a)\succ_{a}a\\}\rvert$ $\displaystyle-\lvert\\{a\in U(M)\mid
M^{\prime}(a)\succ_{a}a\\}\rvert-\lvert\\{a\in U(M)\mid
M^{\prime}(a)=a\\}\rvert$ $\displaystyle-\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert$ $\displaystyle=n+\lvert\\{a\in A\mid
M^{\prime}(a)\succ_{a}M(a)\\}\rvert$ $\displaystyle-\lvert
U(M)\rvert-\lvert\\{a\in A\mid M(a)\succ_{a}M^{\prime}(a)\\}\rvert$
$\displaystyle\stackrel{{\scriptstyle(3)}}{{\leq}}n+\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert-\lvert U(M)\rvert$
$\displaystyle-\lvert\\{a\in A\mid M(a)\succ_{a}M^{\prime}(a)\\}\rvert$
$\displaystyle=n-\lvert U(M)\rvert$

Equality $(1)$ follows from the fact that

$n=\lvert\\{a\in A\mid M^{\prime}(a)\succ_{a}M(a)\\}\rvert+\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert+\lvert\\{a\in A\mid
M(a)=M^{\prime}(a)\\}\rvert.$

In Equality (2) we added $0=\lvert\\{a\in U(M)\mid
M^{\prime}(a)\succ_{a}a\\}\rvert-\lvert\\{a\in U(M)\mid
M^{\prime}(a)\succ_{a}a\\}\rvert$ and in Inequality (3) we used $\lvert\\{a\in
A\mid M^{\prime}(a)\succ_{a}M(a)\\}\rvert\leq\lvert\\{a\in A\mid
M(a)\succ_{a}M^{\prime}(a)\\}\rvert$, which follows from our assumption that
$M^{\prime}$ is not more popular than $M$.

With this we have shown that a matching $M$ is popular in $\mathcal{I}$ if and
only if there is no matching with weight larger than $n-\lvert U(M)\rvert$ in
$\mathcal{I}^{\prime}$.

With regard to the pov-ha${}_{L}^{U}$ case in our instance
$\mathcal{I}^{\prime}$ we again have the same graph as in $\mathcal{I}$ and
add the weight function $w\colon E\to\\{0,1,n,n+1\\}$, such that for any $a\in
A\setminus U(M)$ and $p\in N_{a}$

$w(\\{a,p\\})=\begin{cases*}n+1,&if $h\succ_{a}M(a)$\\\ n,&if $h=M(a)$\\\
0,&if $M(a)\succ_{a}h$\end{cases*}$

and if $a\in U(M)$ and $p\in N_{a}$ we set $w(\\{a,p\\})=1$. We claim that a
matching $M^{\prime}$ dominates $M$ in $\mathcal{I}$ if and only if
$w(M^{\prime})>n(n-\lvert U(M)\rvert)=w(M).$

####  7.3.3 Correctness

First assume that there is a matching $M^{\prime}$ that dominates $M$ in
$\mathcal{I}$. Then there is at least one applicant who prefers $M^{\prime}$
to $M$ while no applicant prefers $M$ to $M^{\prime}$ and thus based on the
definition, the weight of the matching $M^{\prime}$ in $\mathcal{I}^{\prime}$
is larger than $n(n-\lvert U(M)\rvert)$. Similarly, if $M^{\prime}$ does not
dominate $M$ in $\mathcal{I}$, then either there is an applicant in
$A\setminus U(M)$ preferring $M$ to $M^{\prime}$, thus contributing no weight
to the matching and therefore the weight of the matching $M^{\prime}$ in
$\mathcal{I}^{\prime}$ cannot possibly reach $n(n-\lvert U(M)\rvert)$ or each
applicant in $\mathcal{I}$ is indifferent between $M$ and $M^{\prime}$, which
implies $M=M^{\prime}$ and thus $w(M^{\prime})=n(n-\lvert U(M)\rvert)$ in
$\mathcal{I}^{\prime}$. ∎

###  7.4 Missing proofs from Section 4

See 1

For better readability we split this theorem into three separate statements.

###### Theorem 12

popv-ha${}_{L}^{U}$ is -complete, even with $l_{\text{max}}=3=u_{\text{max}}$,
$\Delta_{A}=4$, and $\Delta_{P}=3$.

###### Proof

The membership in immediately follows from the fact it can be checked in
polynomial time whether a matching is feasible and if it is more popular than
another matching. To show the hardness we reduce from exact cover by 3-sets.
We note that x3c is -complete, even if each element of $X$ appears in at most
three sets [27]. Furthermore, we can assume that $m$ is odd, because for an
even $m$ we can simply add three elements that appear in no other set, and a
set covering exactly them.

####  7.4.1 Construction

We create three sets of applicants $B=\\{b_{1},\dots,b_{3m}\\}$,
$Y=\\{y_{1},\dots,y_{3m}\\}$, $Z=\\{z_{1},\dots,z_{3m}\\}$ and we set $A=B\cup
Y\cup Z$. Furthermore we create three sets of projects
$C=\\{c_{1},\dots,c_{n}\\}$, $D=\\{d_{1},\dots,d_{3m}\\}$,
$E=\\{e_{1},\dots,e_{3m}\\}$ and set $P=C\cup D\cup E$. For these projects, we
set $\ell_{c_{i}}=u_{c_{i}}=3$, $\ell_{d_{i}}=u_{d_{i}}=3$, and
$\ell_{e_{i}}=u_{e_{i}}=2$.

Next we define the preferences of the applicants, here we take the indices
modulo $3m$, i.e., $1-1=3m$ in our notation. Let $i\in[3m]$ and
$T_{j},T_{k},T_{l}$ be the three sets that contain $x_{i}$. For each $i$, we
give applicant $b_{i}$ the preference list $c_{j}\succ c_{k}\succ c_{l}\succ
d_{i}$, and $z_{i}$ gets the preference list $d_{i}\succ e_{i-1}$. For $Y$, we
differentiate on the parity of $i$: if $i$ is odd, then we give $y_{i}$ the
preference list $e_{i}\succ d_{i}$ and otherwise, if $i$ is even, then $y_{i}$
gets the preference list $d_{i}\succ e_{i}$—these applicants are the ones
where we deviate from the proof of Cechlárová and Fleiner [17].

We next show that an exact cover exists if and only if the matching $M$
defined by $M(d_{i})=\\{b_{i},y_{i},z_{i}\\}$ for all $i\in[3m]$ is unpopular.

####  7.4.2 $\Rightarrow$

Firstly assume that we have an exact cover $T_{i_{1}},\dots,T_{i_{m}}$. Now we
create a matching $M^{\prime}$ with $M^{\prime}(b_{i})=c_{i_{j}}$ if $x_{i}\in
T_{i_{j}}$, $M^{\prime}(z_{i})=e_{i-1}$ and $M^{\prime}(y_{i})=e_{i}$. This
matching is feasible, since we have an exact cover and thus every $c_{i_{j}}$
is matched to exactly the three applicants from $B$ that could be matched to
it. Every $b_{i}$ and all $y_{i}$ with an odd index prefer $M^{\prime}$ to $M$
while all $z_{i}$ and $y_{i}$ with an even index prefer $M$ to $M^{\prime}$.
Tallying the votes, it turns out that $M^{\prime}$ is more popular than $M$,
because $|B|=|Z|$, and since $m$ was odd, there are more $y_{i}$ applicants
with an odd index than with an even index.

####  7.4.3  $\Leftarrow$

Next assume that there is a more popular feasible matching $M^{\prime}$. If
all $b_{i}$ are matched to some $c_{j}$ then we trivially have an exact cover.
Otherwise assume we have $b_{i_{1}},\dots,b_{i_{k}}$, who are not matched to a
$c_{j}$ and assume that $i_{1}<\dots<i_{k}.$ We let
$A_{i_{j}}\coloneqq\\{b_{i_{\alpha}},y_{i_{\alpha}+1},z_{i_{\alpha}}\mid
i_{j}\leq i_{\alpha}<i_{j+1}\\}$. The vote for $M^{\prime}$ is simply the sum
over all the votes in all the $A_{i_{j}}$. If $\lvert A_{i_{j}}\rvert=3$, then
$b_{i_{j+1}}$ has to be unmatched as well. Thus either $b_{i_{j}},z_{i_{j}}$,
and $y_{i_{j+1}}$ all stay the same or $b_{i_{j}},z_{i_{j}}$ both have to get
worse. Therefore the vote of $A_{i_{j}}$ in this case is non-positive. If
$\lvert A_{i_{j}}\rvert>3$, it is easy to see that the sum over all votes
except for $b_{i_{j}},y_{i_{j}+1}$, and $z_{i_{j}}$ can be at most one, since
the $y_{i_{\alpha}}$ are alternating and the $b_{i_{j}}$ and $z_{i_{j}}$
cancel out. Furthermore it has to hold that either $b_{i_{j}}$ is matched to
$d_{i_{j}}$ and thus $y_{i_{j}+1}$ is unmatched and votes negatively or
$b_{i_{j}}$ is unmatched and $z_{i}$ also has to vote negatively. Therefore
the vote in $A_{i_{j}}$ can be at most $0$ and thus $M$ could not have been
popular. ∎

###### Theorem 13

pop-ha${}_{L}^{U}$ is -hard, even with $l_{\text{max}}=3=u_{\text{max}}$,
$\Delta_{A}=10$, and $\Delta_{P}=3$.

###### Proof

We reduce from x3c again.

####  7.4.4 Construction

We follow the notation from the last reduction and create three sets of
applicants $B=\\{b_{1},\dots,b_{3m}\\}$, $Y=\\{y_{1},\dots,y_{3m}\\}$,
$Z=\\{z_{1},\dots,z_{3m}\\}$ and we set $A=B\cup Y\cup Z$. Furthermore we
create five sets of projects $C=\\{c_{1},\dots,c_{n}\\}$,
$C^{\prime}=\\{c^{\prime}_{1},\dots,c^{\prime}_{n}\\}$,
$C^{\prime\prime}=\\{c^{\prime\prime}_{1},\dots,c^{\prime\prime}_{n}\\}$,
$D=\\{d_{1},\dots,d_{3m}\\}$, $E=\\{e_{1},\dots,e_{3m}\\}$ and set $P=C\cup
C^{\prime}\cup C^{\prime\prime}\cup D\cup E$. The projects in
$D,C,C^{\prime}$, and $C^{\prime\prime}$ all have upper and lower quota $3$,
while the projects in $E$ have upper and lower quota $2$. Next let $i\in[3m]$
and let $T_{j},T_{k},T_{l}$ be the three sets that contain $x_{i}$. Now for
any $T_{p}\in\\{T_{j},T_{k},T_{l}\\}$ let

$\mathcal{C}(T_{p},x_{i})=\begin{cases}c_{p},c_{p}^{\prime},c_{p}^{\prime\prime},\text{if
}x_{i}\text{ is the element with the smallest index in }T_{p};\\\
c_{p}^{\prime},c_{p}^{\prime\prime},c_{p},\text{if }x_{i}\text{ is the element
with the second smallest index in }T_{p};\\\
c_{p}^{\prime\prime},c_{p},c_{p}^{\prime},\text{if }x_{i}\text{ is the element
with the third smallest index in }T_{p};\\\ \end{cases}$

and we give $b_{i}$ the preference list
$\mathcal{C}(T_{j},x_{i})\succ\mathcal{C}(T_{k},x_{i})\succ\mathcal{C}(T_{l},x_{i})\succ
d_{i}$. Note that this preference structure falls under Observation 3,
enforcing each of the $T_{p}$ projects to be closed. The applicant $z_{i}$
gets the preference list $d_{i}\succ e_{i-1}$. The preference list of $y_{i}$
is set to $e_{i}\succ d_{i}$ for each odd $i$, while its is set to $d_{i}\succ
e_{i}$ for each even $i$.

####  7.4.5 $\Leftarrow$

Firstly if no exact cover exists, then it follows by the calculations in
Theorem 1 that the matching $M$ with $M(d_{i})=\\{b_{i},y_{i},z_{i}\\}$ is
popular, since all we added were additional copies of projects in $C$.

####  7.4.6 $\Rightarrow$

If however an exact cover exists, then the matching $M$ is again unpopular.
Now assume that we have a matching $M^{\prime}\neq M$. If there is no $b_{i}$
that is matched to any $c_{j}$, $c^{\prime}_{j}$ or $c^{\prime\prime}_{j}$ in
$M^{\prime}$, then $M$ is more popular than $M^{\prime}$, since this would
improve the matching for any $b_{i}$ and $z_{i}$ not matched to $d_{i}$. If
there is however a $b_{i}$ that is matched to some (without loss of
generality) $c_{j}$, then there need to be $b_{k},b_{l}$ that are matched to
$c_{j}$ as well. Now this instance falls under Observation 3 and thus
$M^{\prime}$ was not popular. ∎

###### Theorem 14

perpo-ha${}_{L}^{U}$ is $\NP$-complete even when
$l_{\text{max}}=3=u_{\text{max}}$ and $\Delta_{A}=3=\Delta_{P}$.

###### Proof

First we observe that if a perfect matching exists, then a perfect Pareto
optimal matching also must exist, because of the monotonicity of the dominance
relation. This implies that the problem is in . With regard to the hardness we
give a simple reduction from x3c. For each set $T\in\mathcal{T}$ we create a
project $p_{T}$ with $\ell_{p_{T}}=u_{p_{T}}=3$, and for each element $x\in X$
that appears in the sets $T_{i},T_{j},T_{k}$ we create an applicant $a_{x}$
with edges to projects $p_{T_{i}},p_{T_{j}},p_{T_{k}}$, where these three
projects appear in an arbitrary order in the preference list of $a_{x}$.

It is obvious that an exact cover exists if and only if a perfect matching
exists, which is equivalent to the existence of a perfect Pareto optimal
matching. ∎

In order to prove Theorem 2, we first describe a faster algorithm for weighted
matching with lower quota 2.

While the theorem of Dudycz and Paluch [21] gives us an easy classification
result, we show how to combine the methods of Cornuéjols [18] and Dudycz and
Paluch [21] to get a faster algorithm for our special case, which is also
easier to implement. For this we first need to review some definitions of
Dudycz and Paluch [21]. We start with the definition of _neighboring type_ , a
measure to define similarity between graph factors (or matchings in our case).
For this we are given an instance of the general factor problem. For any $v\in
V$ and $k\in B_{v}$, let $u_{k}(v)\in B_{v}$ be the maximum element such that
either $B_{v}\cap[k,u_{k}(v)]\subseteq 2\mathbb{Z}$ or
$B_{v}\cap[k,u_{k}(v)]\subseteq 2\mathbb{Z}+1$, i.e., $B_{v}\cap[k,u_{k}(v)]$
only contains elements of the same parity as $k$. Similarly we let
$\ell_{k}(v)$ to be the minimum element such that $B_{v}\cap[\ell_{k}(v),k]$
has the same parity of $k$. In the following we also call any solution to the
general factor problem a $B$-matching. Given a $B$-matching $M$ we define
$B_{M}(v)\coloneqq[\ell_{\lvert M(v)\rvert}(v),u_{\lvert M(v)\rvert}(v)]$.
Using this we can finally define what a matching of neighboring type is.

######  Definition 1 (Neighboring type, Dudycz and Paluch [21])

Given two $B$-matchings $M^{\prime}$ and $M$ let $D=\\{v\in V\mid\lvert
M^{\prime}(v)\rvert\notin B_{M}(v)\\}$. Now we say that $M^{\prime}$ is of
neighboring type of $M$ if one of

  1. 1.

$\lvert D\rvert=0$

  2. 2.

$\lvert D\rvert=2$ and for $v\in D$, $B_{M^{\prime}}(v)$ and $B_{M}(v)$ are
_adjacent_ , meaning that either
$\max(B_{M^{\prime}}(v))+1=\min(B_{M^{\prime}}(v))$ or
$\max(B_{M}(v))+1=\min(B_{M^{\prime}}(v))$

  3. 3.

$\lvert D\rvert=1$ and for $v\in D$, either
$\min(B_{M}(v))-\max(B_{M^{\prime}}(v))=2$ or
$\min(B_{M^{\prime}}(v))-\max(B_{M}(v))=2$

holds.

This now brings us to one of the key theorems ([21, Theorem 2]) of their
paper, namely that while trying to find a matching of larger weight it is
sufficient to look at matchings of neighboring types.

######  Proposition 3 (Dudycz and Paluch [21])

Given a $B$-matching $M$ there exists a $B$-matching of greater weight than
$M$ if and only if there exists a $B$-matching of greater weight and
neighboring type of $M$.

This theorem now has consequences for our matching problem. First we take a
look at what kind of matchings have a neighboring type.

###### Observation 4

Given an instance with $l_{\text{max}}=2$ and a matching $M$, a matching
$M^{\prime}$ is of neighboring type to $M$ if there are

  1. 1.

arbitrarily many projects $p\in P$ with $\ell_{p}=2$, such that $\lvert
M(p)\rvert=2$ and $\lvert M^{\prime}(p)\rvert=0$ or $\lvert M(p)\rvert=0$ and
$\lvert M^{\prime}(p)\rvert=2$ and

  2. 2.

at most one of

    1. (a)

exactly one project $p\in P$ with $\lvert M(p)\rvert\neq 0$ and $\lvert
M^{\prime}(p)\rvert=\lvert M(p)\rvert+2$ or $\lvert M^{\prime}(p)\rvert\neq 0$
and $\lvert M^{\prime}(p)\rvert=\lvert M(p)\rvert-2$;

    2. (b)

two of projects $p\in P$, such that $\lvert M^{\prime}(p)\rvert=\lvert
M(p)\rvert\pm 1$ or applicants $a\in A$ that are matched in $M$ and unmatched
in $M^{\prime}$ or matched in $M^{\prime}$ and unmatched in $M$.

###### Proof

This mostly follows from the definition of neighboring type, the only way for
the second case of the neighboring type definition to be feasible, is for an
applicant to be matched/unmatched or for a project to get one less/more
applicant matched to it.

Similarly the only way for the third case to happen, is for a project to gain
two applicants, since the applicants only have a choice between $1$ and $0$
projects to be matched to them. ∎

Now we want to turn this observation into an algorithm and for this we use the
gadgets defined by [18] to reduce our problem to the maximum weight matching
problem without lower quotas. For simplicity’s sake we assume that each
applicant has a unique last-resort with lower and upper quota $1$ project to
which only she is connected with weight $0$, thus allowing us to assume that
all applicants are matched in any matching. The structure of our algorithm is
simple: we check all three cases induced by Observation 4 and in cases 2a) and
2b) we iterate over all possible projects and applicants to change.

###### Lemma 3

Given a weighted matching $M$ in an instance $\mathcal{I}$ of w-ha${}_{L}^{U}$
with weight function $w$, there is an $\mathcal{O}(\lvert V\rvert\lvert
E\rvert)$ time algorithm to check if there is a matching of neighboring type
to $M$ fulfilling neither of 2a) and 2b) in Observation 4.

###### Proof

Based on Observation 4, the only changes we are allowed to make to the
matching is to have arbitrarily many projects going from being matched to $2$
applicants to being matched to $0$ and vice versa. We now iteratively go over
all projects with $\lvert M(p)\rvert\in\\{0,2\\}$ and replace them by a
gadget, see Cornuéjols [18] for this approach. In the end this will give us an
instance $\mathcal{I}^{\prime}$ of maximum weight perfect matching.

Assume we are given a project $p\in P$ such that $p$ is adjacent to the
applicants $a_{1},\dots a_{k}$ with $k\geq 2$ and $\ell_{p}\geq 2$. Then we
introduce the new vertices $p_{1},\dots p_{k}$ and $s^{p}_{1},\dots
s^{p}_{k}$. We add an edge between $a_{i}$ and $p_{i}$ with weight
$w(a_{i},p)$ for all $i\in[k]$ and we connect $p_{i}$ to $s^{p}_{j}$ with
weight $0$ for $i,j\in[k]$ ,i.e., they are a complete bipartite graph. Finally
we add an edge from $s^{p}_{1}$ to $s^{p}_{2}$ also with weight $0$. We now
apply this transformation to all projects $p\in P$ with $\lvert
M(p)\rvert\in\\{0,2\\}$. This gadget will ensure that $p$ can be either
matched to $0$ or to $2$ applicants.

Further for each project $p\in P$ with $\lvert M(p)\rvert\notin\\{0,2\\}$ such
that $p$ is adjacent to the applicants $a_{1},\dots a_{k}$ we replace $p$ by
the new vertices $p_{1},\dots p_{k}$ and $s^{p}_{1},\dots s^{p}_{k-\lvert
M(p)\rvert}$. We again connect $a_{i}$ to $p_{i}$ with weight $w(a_{i},p)$ for
$i\in[k]$ and connect all $p_{i}$ and $s^{p}_{j}$ in a fully bipartite manner
with every edge having a weight of $0$. This gadget will ensure that $p$ can
only be matched to $\lvert M(p)\rvert$ applicants.

We now argue that every maximum weight perfect matching corresponds to a
matching of neighboring type to $M$ with maximum weight, such that neither of
2a) and 2b) in Observation 4 are fulfilled.

First assume that we are given a matching $N$ of neighboring type to $M$ and
we want to create a corresponding perfect matching $M^{\prime}$ in
$\mathcal{I}^{\prime}$. Now for each $p\in P$ with $\lvert
M(p)\rvert\in\\{0,2\\}$ and $\lvert N(p)\rvert=0$ we match $p_{i}$ to
$s^{p}_{i}$. For each $p\in P$ with $\lvert M(p)\rvert\in\\{0,2\\}$ and
$\lvert N(p)\rvert=2$, such that $N(p)=\\{a_{i},a_{j}\\}$, we match
$s^{p}_{1}$ to $s^{p}_{2}$, $p_{i}$ to $a_{i}$ and $p_{j}$ to $a_{j}$ and all
remaining $s^{p}_{k}$ and $p_{k}$ vertices in an arbitrary manner.

For each $p\in P$ with $\lvert M(p)\rvert\notin\\{0,2\\}$ it must hold that
$\lvert N(p)\rvert=\lvert M(p)\rvert$. We can thus match any $a_{i}\in N(p)$
to $p_{i}$ and match the remaining $p_{j}$ arbitrarily to the $s^{p}_{j}$.

It is easy to see that this matching is perfect and has the same weight as
$N$. Of course we can also revert this process and given any perfect matching
$M^{\prime}$ in $\mathcal{I}^{\prime}$ we can create a matching $N$ of the
desired neighboring type of the same weight, by matching $a_{i}$ to the
project $p$ in $N$ if $a_{i}$ is matched to $p_{i}$ in $M^{\prime}$. The
matching $N$ has the same weight as $M^{\prime}$ and due to the structure of
our gadget it is of the desired neighboring type.

Thus in order to verify whether $M$ is a maximum weight matching it is
sufficient to test whether $M^{\prime}$ is a maximum weight perfect matching,
which is possible in linear time in the size of the graph, see [41, Section
26.2]. It is easy to see that the graph created in $\mathcal{I}^{\prime}$ has
$\mathcal{O}(\lvert V\rvert+\lvert E\rvert)$ vertices and $\mathcal{O}(\lvert
E\rvert+\sum_{v\in V}\deg_{v}^{2})\in\mathcal{O}(\lvert E\rvert\,\lvert
V\rvert)$, see [14]. ∎

The same construction also allows us to find a matching of neighboring type
fulfilling either 2a) or 2b).

###### Corollary 1

Given a weighted matching $M$ in an instance $\mathcal{I}$ of w-ha${}_{L}^{U}$
with weight function $w$, there is an $\mathcal{O}(\lvert V\rvert^{3}\lvert
E\rvert)$ time algorithm to check if there is a matching of neighboring type
to $M$ fulfilling either 2a) or 2b) in Observation 4.

###### Proof

This can be done, by iterating over all possible projects in 2a) or all
possible pairs of projects in 2b) and fixing their degree using the same
gadget as in the previous theorem. ∎

Using this we now have a faster algorithm for our polynomial-time solvable
lower quota $2$ problems.

See 2

###### Proof

For popv-ha${}_{L}^{U}$ and pov-ha${}_{L}^{U}$ we can use Lemma 2 and our
previous algorithm to test whether the given matching is of maximum weight.
For perpo-ha${}_{L}^{U}$ we can start with any perfect matching which we can
find using $n$ iterations of finding a larger matching, followed by $\lvert
E\rvert$ iterations of finding a matching that dominates our given matching. ∎

See 3

###### Proof

Note that the membership in $\NP$ follows from Corollary 1. We reduce from the
-complete problem of finding a popular matching in a non-bipartite graph ([25,
30]). Given an instance $\mathcal{I}$ of the popular matching problem in the
non-bipartite graph $G=(V,E)$ and corresponding preference lists, we create an
instance $\mathcal{I}^{\prime}$ of pop-ha${}_{L}^{U}$ by creating an applicant
$a_{v}$ for each vertex $v\in V$ and a project $p_{e}$ with upper and lower
quota 2 for each edge $e\in E$. If a vertex $v\in V$ has a preference list
$v_{1}\succ_{v},\dots,\succ_{v}v_{k}$ in $\mathcal{I}$, then in
$\mathcal{I}^{\prime}$ we assign the applicant $a_{v}$ the preference list
$p_{\\{v_{1},v\\}}\succ_{a_{v}},\dots,\succ_{a_{v}}p_{\\{v_{k},v\\}}$, i.e.,
applicant $a_{v}$ ranks all the edges in the same order that the vertex $v$
ranked them. We now argue that $\mathcal{I}$ has a popular matching if and
only if $\mathcal{I}^{\prime}$ admits a popular matching.

We define a straightforward bijection between feasible matchings in
$\mathcal{I}$ and $\mathcal{I}^{\prime}$. To a given matching $M^{\prime}$ in
$\mathcal{I}^{\prime}$ we create a matching $M$ in $\mathcal{I}$ by including
the edge $(u,v)$ if and only if $a_{u}$ and $a_{v}$ are matched to the same
project in $M^{\prime}$. Conversely, for a given matching $M$ in $\mathcal{I}$
we create the matching $M^{\prime}$ in $\mathcal{I}^{\prime}$ with
$M^{\prime}(a_{u})=p_{\\{u,v\\}}=M^{\prime}(a_{v})$ if and only if $M(u)=v$.
Notice that the construction guarantees that the vertex $v$ is matched to its
$i$th choice in the matching $M$ in $\mathcal{I}$ if and only if the
corresponding applicant $a_{v}$ in $M^{\prime}$ in $\mathcal{I}^{\prime}$ is
matched to her $i$th choice. Thus if $M$ is popular in $\mathcal{I}$, then
$M^{\prime}$ was also popular in $\mathcal{I}^{\prime}$ and vice versa. ∎

###  7.5 Missing proofs from Section 5

See 1

###### Proof

To properly have a decision problem, we treat the maximum weight matching
problem as the problem of deciding whether there is a matching with weight at
least $x$. First if $\lvert P\rvert\leq W2^{n}$, we can trivially return our
current instance as a kernel of size $\mathcal{O}(W2^{n})$.

####  7.5.1 Construction

Let $A^{\prime}\subseteq A$ be any subset of applicants and for
$w^{\prime}\leq W\lvert A^{\prime}\rvert$ let

$P^{w^{\prime}}_{A^{\prime}}\subseteq P\coloneqq\\{p\in P\mid
A^{\prime}\subseteq N_{p},\ell_{p}\leq\lvert A^{\prime}\rvert\leq
u_{p},\sum_{a\in A^{\prime}}w(a,p)=w^{\prime}\\},$

i.e., the subset of projects, such that we could match all applicants of
$A^{\prime}$ to this project to get a weight of exactly $w^{\prime}$. Now for
any $A^{\prime}\subseteq A$ and $w^{\prime}\leq W\lvert A^{\prime}\rvert$ we
put a marker on $n$ of the projects in $H^{w^{\prime}}_{A^{\prime}}$. If there
are less than $n$ projects in $H^{w^{\prime}}_{A^{\prime}}$ we put a marker on
all of them. After this, we delete all projects without a marker.

####  7.5.2 Correctness

If there was no matching with a weight of at least $x$ in the original
instance, then our reduced instance also does not admit a matching of weight
at least $x$ since we only deleted projects. Now assume there was a matching
$M$ with weight at least $x$ in the original instance. If all the opened
projects in $M$ have a marker on them, then the matching is of course still
feasible. If there is some project $p$ without a marker, then there has to be
a different project that is unopened and has a marker on it, such that we can
match all the applicants in $M(p)$ to this project with the same weight, since
we guaranteed by our construction that there are at least $n$ of these
projects. Thus we can iteratively transform $M$ into a feasible matching in
our reduced instance. Finally we notice that each applicant can be adjacent to
at most $2^{n}nW$ projects and thus we have at most $\mathcal{O}(2^{n}n^{2}W)$
projects. ∎ See 4

###### Proof

We reduce from the W[1]-complete problem multicolored independent set. Here we
are given a graph $G=(V,E)$ together with a partition of the vertices into $k$
color classes $V_{1},\dots,V_{k}$ and we are searching for an independent set
that includes exactly one vertex from each color class. To further simplify
notation, we also assume that the graph is $p$-regular, each color class
contains exactly $q$ vertices, and no two vertices in the same color class are
adjacent (see [20] for this construction).

####  7.5.3 Construction

Our pop-ha${}_{L}^{U}$ instance consists of the following projects:

  * •

For each $v\in V$ we include a _vertex project_ $p_{v}$ with lower and upper
quota $4$.

  * •

For each edge $e\in E$ we include an _edge project_ $p_{e}$ with lower and
upper quota $4$.

  * •

We create three _dummy projects_ $p_{1},p_{2},p_{3}$, each with lower and
upper quota $1$.

  * •

Finally for each $(c,d)\in[k]\times[k]$ we create a _two-color project_
$p_{c,d}$ with upper and lower quota $5$.

Now we turn to the applicants. Let $c\in[k]$ be any color and let $v_{1},\dots
v_{q}$ be the vertices of $V_{c}$. Further for any $v_{i}\in V_{c}$ let
$e^{i}_{1},\dots e^{i}_{p}$ be a list of the edges $v_{i}$ is adjacent to. We
introduce two _selection applicants_ $a_{c}^{1}$ and $a_{c}^{2}$ with
preferences

$\displaystyle a_{c}^{1}\colon p_{e_{1}^{1}}\succ\dots\succ p_{e^{1}_{p}}\succ
p_{v_{1}}\succ\dots\succ p_{e^{q}_{1}}\succ\dots\succ p_{e^{q}_{p}}\succ
p_{v_{q}},$ $\displaystyle a_{c}^{2}\colon p_{e_{1}^{q}}\succ\dots\succ
p_{e^{q}_{p}}\succ p_{v_{q}}\succ\dots\succ p_{e^{1}_{1}}\succ\dots\succ
p_{e^{1}_{p}}\succ p_{v_{1}}.$

Note that the preference lists of these selection applicants list the vertex
projects in reverse order of each other and list all the edge projects
belonging to the vertex projects before these vertex projects. Further for any
color $c\in[k]$ we also add two _enforcing applicants_ $\hat{a}_{c}^{1}$ and
$\hat{a}_{c}^{2}$ with preference lists

$\displaystyle\hat{a}_{c}^{1}\colon p_{v_{1}}\succ\dots\succ p_{v_{q}}\succ
p_{1}\succ p_{2}\succ p_{3}\succ p_{c,1}\succ\dots\succ p_{c,q},$
$\displaystyle\hat{a}_{c}^{2}\colon p_{v_{q}}\succ\dots\succ p_{v_{1}}\succ
p_{1}\succ p_{2}\succ p_{3}\succ p_{c,1}\succ\dots\succ p_{c,q},$

and we add two _dummy applicants_ $a_{1}$ and $a_{2}$ who both have the
preference list $p_{1}\succ p_{2}\succ p_{3}$. Finally for each combination of
colors $(c,d)\in[k]\times[k]$ we also add one last _dummy applicant_ $a_{c,d}$
whose preference list only consists of $p_{c,d}$. Thus the number of
applicants is in $\mathcal{O}(k^{2})$.

####  7.5.4 $\Rightarrow$

First assume that $v_{1},\dots,v_{k}$ form a multicolored independent set with
$v_{c}\in V_{c}$ for $c\in[k]$. We now show that the matching $M$ with
$M(p_{v_{c}})=\\{a^{1}_{c},a^{2}_{c},\hat{a}_{c}^{1},\hat{a}_{c}^{2}\\}$ for
$c\in[k],M(p_{1})=a_{1}$ and $M(p_{2})=a_{2}$ is popular. To do so, we prove
that any applicant improving in a matching has a corresponding applicant that
gets worse in this matching.

  * •

First we notice that if $a_{2}$ would improve in any matching, then $a_{1}$
would get worse, thus canceling out their votes.

  * •

Similarly if any $\hat{a}_{c}^{1}$ would improve, then $\hat{a}_{c}^{2}$ would
get worse, due to the front part of their preference lists being reversed.
Naturally, if $\hat{a}_{c}^{2}$ would improve, $\hat{a}_{c}^{1}$ would get
worse and thus their votes also cancel out in this case.

  * •

If $a_{c}^{1}$ would improve by matching a vertex project, $a_{c}^{2}$ would
get worse, thus canceling out their vote.

  * •

Finally assume that $a_{c}^{1}$ could get better by matching an edge project
$p_{v,u}$ with $v\in V_{c}$ and $u\in V_{d}$. Then, since we have an
independent set, without loss of generality $a_{d}^{1}$ and $a_{d}^{2}$ cannot
have been matched to $p_{u}$ in our original matching. Thus by the structure
of our preference lists, at least one of $a_{d}^{1}$ and $a_{d}^{2}$ must have
gotten worse. Further all of the applicants of
$\hat{a}_{c}^{1},\hat{a}_{c}^{2},\hat{a}_{d}^{1},\hat{a}_{d}^{2}$ must now be
matched to a project they rank worse than their respective vertex project,
while at most $a_{c,d}$ could have gotten better if all $5$ applicants got
matched to $p_{c,d}$. Thus the total sum of their votes is at most $-1$.

Therefore since for any improving applicant, there has to be a unique
applicant who gets worse, the matching $M$ is popular.

####  7.5.5 $\Leftarrow$

Next we assume that we have a popular matching $M$.

####  7.5.6 $a_{c,d}$ and $p_{c,d}$ must be unmatched

Firstly we show that for any $(c,d)\in[k]\times[k]$ the applicant $a_{c,d}$
must be unmatched. If $a_{c,d}$ is matched to $p_{c,d}$ then due to the lower
quota of $5$,
$\hat{a}_{c}^{1},\hat{a}_{c}^{2},\hat{a}_{d}^{1},\hat{a}_{d}^{2}$ must all
also be matched to $p_{c,d}$. Now if any of $a_{c}^{1},a_{c}^{2},a_{d}^{1},$
and $a_{d}^{2}$ are unmatched, (without loss of generality $a_{c}^{1}$ and
$a_{c}^{2}$) we can simply choose some $v\in V_{c}$ and match
$a_{c}^{1},a_{c}^{2},\hat{a}_{c}^{1},$ and $\hat{a}_{c}^{2}$ to $p_{v}$ thus
improving the matching for $4$ applicants, while only making it worse for $3$,
which implies that the matching was not popular. Similarly if
$a_{c}^{1},a_{c}^{2},a_{d}^{1},$ and $a_{d}^{2}$ are all matched, they must be
matched to some edge projects. First, if they are matched to the same edge
project $p_{\\{v,u\\}}$ with $v\in V_{c}$ and $u\in V_{d}$, then we can take
two vertices $v^{\prime}\neq v\in V_{c}$ and $u^{\prime}\neq u\in V_{d}$ and
match $a_{c}^{1},a_{c}^{2},\hat{a}_{c}^{1},$ and $\hat{a}_{c}^{2}$ to
$p_{v^{\prime}}$ and $a_{d}^{1},a_{d}^{2},\hat{a}_{d}^{1},$ and
$\hat{a}_{d}^{2}$ to $p_{u^{\prime}}$ thus improving the matching for exactly
two of the four selection applicants
$a_{c}^{1},a_{c}^{2},a_{d}^{1},a_{d}^{2},$ ,while the matching improves for
$\hat{a}_{c}^{1},\hat{a}_{c}^{2},\hat{a}_{d}^{1},$ and $\hat{a}_{d}^{2}$ and
gets worse for $a_{c,d}$, thus implying that $M$ was unpopular. If the
applicants are matched to different edge projects, we can do the same trick as
earlier but incorporate the four applicants of the other colors as well.

####  7.5.7 No $\hat{a}_{c}$ can be matched to a dummy

We notice that the projects $p_{1},p_{2},p_{3}$ with their corresponding
applicants induce an instance of Observation 2. Thus in a popular matching
only two of the dummy projects can be open, which in turn implies that the
only applicants matched to the dummy projects can be the dummy applicants
(otherwise the matching is not even Pareto optimal), therefore for any color
$c\in[k]$ there must be exactly one vertex project $p_{v}^{c}$ open, to which
$a_{c}^{1},a_{c}^{2},\hat{a}_{c}^{1},$ and $\hat{a}_{c}^{2}$ are matched.

####  7.5.8 Constructing the independent set

Let us now take the set $I\coloneqq\\{v\in V\mid p_{v}\text{ is open in }M\\}$
and assume that there is an edge between two vertices $v,u\in I$, with $v\in
V_{c}$ and $u\in V_{d}$. Then if there is any edge between $u$ and $v$, we can
match $a_{c}^{1},a_{c}^{2},a_{d}^{1}$ and $a_{d}^{2}$ to $p_{\\{u,v\\}}$ and
$\hat{a}_{c}^{1},\hat{a}_{c}^{2},\hat{a}_{d}^{1},\hat{a}_{d}^{2},$ and
$a_{c,d}$ to $p_{c,d}$, thus improving the matching for $5$ applicants and
making it worse for $4$ which in turn would imply that the matching was not
popular. Therefore there cannot be edges between vertices in $I$ and thus $I$
must be a multicolored independent set. ∎

See 5

###### Proof

Our goal is to encode the matching instance in such a way that the resulting
parametric integer program is feasible if and only if no popular matching
exists. For this we choose the matrix $B$ and vector $d$ in such a way that
all possible matchings can be represented by a vector $b$ satisfying $Cb\leq
d$. Further the matrix $B$ should be chosen in such a way that the vector $x$
represents a matching that is more popular than the matching represented by
$b$.

####  7.5.9 Notation

First, since we parameterize by $m$, each applicant $a\in A$ can be uniquely
identified by her preference structure over $P$. There are at most
$\mathcal{O}((m+1)!)$ different preference structures, hence we can partition
$A$ into $t\in\mathcal{O}((m+1)!)$ types. Let $A_{1},\dots,A_{t}$ be this
partition, such that any two applicants in the same set have the same
preference list. Further we also refer to the projects that appear in the
preference lists of applicants in $A_{i}$ as $N_{i}$. Furthermore we slightly
alter the notation of the previous sections to follow [10] and define the vote
of a vertex as follows.

$\operatorname{vote}_{a}(p_{1},p_{2})=\begin{cases*}1,&if
$p_{1}\succ_{a}p_{2}$\\\ 0,&if $p_{1}=p_{2}$\\\ -1,&if
$p_{2}\succ_{a}p_{1}$\end{cases*}$

Following the definition of popularity, matching $M^{\prime}$ is more popular
than matching $M$ if and only if $\sum_{a\in
A}\operatorname{vote}_{a}(M^{\prime}(a),M(a))\geq 1$ holds. For easier
notation for any type $i\in[t]$ we define
$\operatorname{vote}_{i}(p_{1},p_{2})=\operatorname{vote}_{a}(p_{1},p_{2})$
where $a\in A_{i}$ is an applicant of type $i$.

####  7.5.10 Construction of $C$

As noted earlier, our goal is to construct the linear program represented by
$B$ and $d$ in such a way that every feasible matching is a solution to this
linear program. To reach this, for each $i\in[t]$ and $p\in N_{i}$ we create a
variable $x_{i}^{p}$ that should indicate how many applicants of type $A_{i}$
are matched to project $p$. Moreover we add one variable $x_{i}^{i}$
indicating the number of unmatched applicants of type $i$. Furthermore for
each project $p\in P$ we create a variable $o_{p}$ that should indicate
whether project $p$ is open or closed. This now leads us to the following
linear program

$\displaystyle\displaystyle\sum\limits_{p\in N_{i}\cup\\{i\\}}x_{i}^{p}$
$\displaystyle=$ $\displaystyle\lvert A_{i}\rvert,\quad$ for each $i\in[t]$
(13) $\displaystyle\displaystyle\sum\limits_{i\in[t]\colon p\in
N_{i}}x_{i}^{p}-o_{p}u_{p}$ $\displaystyle\leq$ $\displaystyle 0,\quad$ for
each $p\in P$ (14) $\displaystyle\displaystyle\sum\limits_{i\in[t]\colon p\in
N_{i}}x_{i}^{p}-o_{p}\ell_{p}$ $\displaystyle\geq$ $\displaystyle 0,\quad$ for
each $p\in P$ (15) $\displaystyle x_{i}^{p}$ $\displaystyle\geq$
$\displaystyle 0,\quad$ for each $i\in[t]$ and $p\in N_{i}$ (16)
$\displaystyle o_{p}$ $\displaystyle\in$ $\displaystyle[0,1],\quad$ for each
$p\in P$ (17)

Here Constraint (13) enforces that all applicants are either matched or
unmatched. Note that each feasible matching is a solution to this ILP.
Currently, any solution to this ILP is of the form
$(x_{1}^{p_{1}},\dots,x_{t}^{p_{m}},o_{p_{1}},\dots,o_{p_{m}})$. This,
however, is not enough to fully model the ILP we need for $B$. As a first
step, for each variable of the form $x_{i}^{p}$ we add a second copy.
Furthermore we add $2t$ variables $b_{1},\dots,b_{2t}$ with $b_{2i}=\lvert
A_{i}\rvert=b_{2i+1}$, then we add $2m$ variables that are forced to be $0$,
and one variable that is forced to be $-1$. After this, each solution $b$ is
of the form $(\lvert A_{1}\rvert,\lvert A_{1}\rvert,\dots,\lvert
A_{t}\rvert,\lvert
A_{t}\rvert,x_{1}^{p_{1}},x_{1}^{p_{1}},\dots,x_{t}^{p_{m}},x_{t}^{p_{m}},o_{p_{1}},\dots,o_{p_{m}},\underbrace{0,\dots,0}_{2m\text{
times}},-1)$.

####  7.5.11 Construction of $B$

We design $B$ to ensure that there is a matching $M^{\prime}$ that is more
popular than the matching $M$ induced by $b$. For any type $i\in[t]$ and
projects $p,p^{\prime}\in N_{i}\cup\\{i\\}$, we create a variable
$x_{i}^{p\rightarrow p^{\prime}}$ that should indicate the number of
applicants of type $i$ who were matched to project $p$ in $M$ and are matched
to project $p^{\prime}$ in $M^{\prime}$. Furthermore, for each project $p\in
P$, we again create a variable $o^{\prime}_{p}$ indicating whether project $p$
is open or closed in $M^{\prime}$. This now allows us to construct the final
ILP.

$\displaystyle\displaystyle\sum\limits_{p,p^{\prime}\in
N_{i}\cup\\{i\\}}x_{i}^{p\rightarrow p^{\prime}}$ $\displaystyle=$
$\displaystyle\lvert A_{i}\rvert,\quad$ for each $i\in[t]$ (18)
$\displaystyle\displaystyle\sum\limits_{p^{\prime}\in
P\cup\\{i\\}}x_{i}^{p\rightarrow p^{\prime}}$ $\displaystyle=$ $\displaystyle
x_{i}^{p},\quad$ for each $i\in[t]$ and $p\in N_{i}$ (19)
$\displaystyle\displaystyle\sum\limits_{i\in[t],p\in P}x_{i}^{p\rightarrow
p^{\prime}}-o^{\prime}_{p^{\prime}}u_{p^{\prime}}$ $\displaystyle\leq$
$\displaystyle 0,\quad$ for each $p^{\prime}\in P$ (20)
$\displaystyle\displaystyle\sum\limits_{i\in[t],p\in P}x_{i}^{p\rightarrow
p^{\prime}}-o^{\prime}_{p^{\prime}}\ell_{p^{\prime}}$ $\displaystyle\geq$
$\displaystyle 0,\quad$ for each $p^{\prime}\in P$ (21)
$\displaystyle\displaystyle\sum\limits_{i\in[t]p,p^{\prime}\in
N_{i}\cup\\{i\\}}-\operatorname{vote}_{i}(p^{\prime},p)x_{i}^{p\rightarrow
p^{\prime}}$ $\displaystyle\leq$ $\displaystyle-1,$ (22) $\displaystyle
x_{i}^{p\rightarrow p^{\prime}}$ $\displaystyle\geq$ $\displaystyle 0,\quad$
for each $i\in[t]$ and $p,p^{\prime}\in N_{i}$ (23) $\displaystyle
o^{\prime}_{p}$ $\displaystyle\in$ $\displaystyle[0,1],\quad$ for each $p\in
P$ (24)

Here Constraint (18) ensures that all applicants have a new partner in
$M^{\prime}$, while Constraint (19) ensures that every applicant matched to
some $p$ in $M$ now has a new partner. Constraints (20) and (21) again ensure
that the lower and upper quotas are met and finally Constraint (22) ensures
that $M^{\prime}$ is more popular than $M$.

####  7.5.12 Correctness

For the correctness of our construction we first observe that our is indeed a
parametric integer program. This follows from the fact that we can model any
constraint of the type $\sum_{i}\alpha_{i}x_{i}=y$ as constraints
$\sum_{i}\alpha_{i}x_{i}\leq y$ and $\sum_{i}-\alpha_{i}x_{i}\leq-y$. Thus the
right hand-side of the second ILP is exactly $b$, except that we simply ignore
the $o_{p}$ variables from $b$. Now all that is left to show is that the
parametric integer program is feasible if and only if no popular matching
exists. First assume that the parametric integer program is feasible and let
$M$ be any feasible matching in our instance. Then if we set $o_{p}=1$ for any
project $p\in P$ if and only if the project $p$ is open in $M$ and for any
type $i\in[t]$ and projects $p\in N_{i}\cup\\{i\\}$, we set $x_{i}^{p}$ to be
the number of applicants of type $i$ matched to $p$ in $M$, the first ILP is
feasible, since the first constraint is fulfilled by every applicant being
matched, while the second and third constraints are fulfilled because $M$
adheres to the quotas.

Now due to us having a feasible parametric integer program instance, there is
an assignment of the variables to fulfill the second ILP. Using this
assignment we can get a feasible matching $M^{\prime}$, by opening all
projects $p\in P$ with $o^{\prime}_{p}=1$ and matching $\sum_{p^{\prime}\in
P}x_{i}^{p^{\prime}\rightarrow p}$ applicants of type $i$ to project $p$. Due
to the Constraints (6), (8), and (9) this implies that $M^{\prime}$ is a
feasible matching. Furthermore Constraint (7) gives us that we can create this
matching from $M$ by matching exactly $x_{i}^{p\rightarrow p^{\prime}}$
applicants of type $i$ that were matched to $p$ in $M$ to $p^{\prime}$ in
$M^{\prime}$. And thus since

$\displaystyle\sum\limits_{i\in[t]p,p^{\prime}\in
N_{i}\cup\\{i\\}}-\operatorname{vote}_{i}(p^{\prime},p)x_{i}^{p\rightarrow
p^{\prime}}\leq-1,$

it holds that

$\displaystyle\sum\limits_{i\in[t]p,p^{\prime}\in
N_{i}\cup\\{i\\}}\operatorname{vote}_{i}(p^{\prime},p)x_{i}^{p\rightarrow
p^{\prime}}\geq 1,$

which implies that $M^{\prime}$ is more popular, since $x_{i}^{p\rightarrow
p^{\prime}}$ is exactly the number of applicants who switched from $M$ to
$M^{\prime}$.

Now assume that no popular matching exists and let $b$ be any feasible
variable assignment to the first ILP. Then we can construct a feasible
matching $M$, by opening all projects $p\in P$ with $o_{p}=1$ and matching
$x_{i}^{p}$ applicants of type $i$ to $p$. Then there is a matching
$M^{\prime}$ that is more popular than $M$. By letting $x_{i}^{p\rightarrow
p^{\prime}}$ be the number of applicants of type $i$ who were matched to $p$
in $M$ and to $p^{\prime}$ in $M^{\prime}$ and by letting $o^{\prime}_{p}=1$
if and only if the project $p$ is open in $M^{\prime}$, we get a feasible
assignment to the second ILP, since we know that

$1\leq\sum_{a\in
A}\operatorname{vote}_{a}(M^{\prime}(a),M(a))=\sum\limits_{i\in[t]p,p^{\prime}\in
N_{i}\cup\\{i\\}}\operatorname{vote}_{i}(p^{\prime},p)x_{i}^{p\rightarrow
p^{\prime}}.$

####  7.5.13 Running time

It is easy to see that $k,\lvert B\rvert\in\mathcal{O}((tm)^{2})$ and since
the maximum entry of any matrix or vector is at most $n$, we get $\lvert\lvert
B,C,d\rvert\rvert_{\infty}\in\mathcal{O}(n+m)$ and thus we can solve the
parametric integer program in $\mathcal{O}(f(m)poly(n+m))$ for some computable
function $f$, which shows that pop-ha${}_{L}^{U}$ is in FPT when parameterized
by $m$. ∎ See 6

###### Proof

We show how to solve this problem via the feasible flow with demands problem.
First we assume that some $a\in A$ is given who will be the designated
applicant to receive a better partner in $M^{\prime}$. Now we create a
directed bipartite graph $G_{a}$ with vertices $A\cup
P_{\text{open}}\cup\\{p_{\perp},s,t\\}$, where $p_{\perp}$ will represent the
unmatched applicants. We connect $s$ to all vertices in $A$ with demand and
capacity of $1$ on the edge. Next we connect $a$ to all projects in
$P_{\text{open}}$ that $a$ prefers to $M(a)$ and all applicants in
$A\setminus\\{a\\}$ get connected to all projects in $P_{\text{open}}$ which
they prefer to $M(a)$ as well as to $M(a)$ if $M(a)$ is in $P_{\text{open}}$,
further if they are unmatched in $M$, we also connect them to $p_{\perp}$. All
of these edges have no demand and a capacity of $1$. Finally we connect every
project $p\in P_{\text{open}}$ to $t$, each with a demand of $\ell_{p}$ and
with a capacity of $u_{p}$ and we connect $p_{\perp}$ to $t$ with no demand
and infinite capacity. We solve the feasible flow with demands problem for all
$a\in A$ in $G_{a}$ and if some $a\in A$ exists for which the demands are
satisfiable, we return the respective induced matching as $M^{\prime}$. That
is, if a flow of $1$ goes from $a$ to $p$, we match $a$ to $p$ in $M^{\prime}$
and if a flow of $1$ goes from $a$ to $p_{\perp}$ we leave $a$ unmatched in
$M^{\prime}$. Otherwise we return that our matching is Pareto optimal.

First assume that there is a $G_{a}$ such that there is a feasible flow in
$G_{a}$. Since each edge from $s$ to $A$ has a demand of $1$, this implies
that each applicant in $A$ is either matched to a project in $P_{\text{open}}$
that she prefers to her project in $M$ or that she is matched to the same
project in both matchings. Furthermore since $a$ is only connected to projects
she prefers to $M(a)$, this implies that $a$ is better off in $M^{\prime}$.
Finally since each project in $P_{\text{open}}$ has a demand equal to its
lower quota, each of the projects must be open and since its capacity is equal
to its upper quota, the matching must be feasible. Thus $M^{\prime}$ is a
feasible matching and dominates $M$.

Similarly if there is a matching $M^{\prime}$ that only opens projects in
$P_{\text{open}}$ and dominates $M$, there has to be an applicant $a\in A$ who
strictly prefers $M^{\prime}$ to $M$. We can thus take the network $G_{a}$ and
the flow that connects every $\hat{a}\in A$ to $M^{\prime}(\hat{a})$ if
$\hat{a}$ is matched in $M^{\prime}$ and connects it to $p_{\perp}$ if
$\hat{a}$ is unmatched. Since the matching only opens projects in
$P_{\text{open}}$ and respects the quotas, this also leads to a flow
respecting the demands incoming into $t$. Thus there is a feasible flow in
$G_{a}$. ∎

$\phantom{1111}\ell_{p_{1}}=$ | 1 = | $u_{p_{1}}$
---|---|---
$\ell_{p_{2}}=$ | 3 = | $u_{p_{2}}$
$\ell_{p_{3}}=$ | 2, | $u_{p_{3}}=4$
$\ell_{p_{4}}=$ | 2 = | $u_{p_{4}}$
$\displaystyle a_{1}\colon$ $\displaystyle p_{2}\succ p_{1}\succ p_{3}$
$\displaystyle a_{2}\colon$ $\displaystyle p_{2}\succ p_{4}$ $\displaystyle
a_{3}\colon$ $\displaystyle p_{3}\succ p_{2}\succ p_{4}$ $\displaystyle
a_{4}\colon$ $\displaystyle p_{3}$

Figure 2: Consider an instance of pov-ha${}_{L}^{U}$ with four applicants
$a_{1},\dots,a_{4}$ and four projects $p_{1},\dots,p_{4}$ with quotas and
preference lists as shown on the right side of the figure. If we consider the
matching $M$ with $M(a_{1})=p_{1},M(a_{2})=p_{4},M(a_{3})=p_{4}$, and
$M(a_{4})=a_{4}$ with $P_{\text{open}}=\\{p_{1},p_{2},p_{3}\\}$, the above
instance is the feasible flow with demands instance created in Theorem 6.

See 7

###### Proof

For our reduction to max-cost circulation we again create a network with
vertices $A\cup P_{\text{open}}\cup\\{p_{\perp},s\\}$, next we connect each
applicant $a\in A$ to all projects she is adjacent to in the original graph,
each with demand $0$, capacity $1$ and the same cost as in the original
network and we connect $a$ to $p_{\perp}$, again with demand $0$, capacity $1$
and cost $0$, next we connect all projects $p\in P_{\text{open}}$ to $s$, each
with demand $\ell_{p}$ and capacity $u_{p}$ and we connect $p_{\perp}$ to $s$
with demand $0$ and capacity $n$. Finally we connect $s$ to every applicant
$a\in A$, each with demand and capacity $1$.

It is obvious that matchings in our original graph in which exactly the
projects in $P_{\text{open}}$ are open, correspond to circulations in our new
graph, since we enforce every project to have a circulation of at least the
lower quota. Thus finding a maximum weight circulation is equivalent to
finding a maximum weight matching that opens exactly the projects in
$P_{\text{open}}$.

∎

See 8

###### Proof

In this proof we generalize the approach of Theorem 7. We refer to
$P_{\text{quota}}$ as the set of all projects with a lower quota greater than
$1$. For this we create a network with vertices $\\{s,p_{\perp}\\}\cup A\cup
P$. Now we iterate over all subsets $\hat{P}\subseteq P_{\text{quota}}$ and
construct the same instance as in Theorem 7 with $P_{\text{open}}=\hat{P}\cup
P\setminus P_{\text{quota}}$, but instead of connecting each project in
$P\setminus P_{\text{quota}}$ with a demand of $1$ to $s$, we connect it with
a demand of $0$. This guarantees that the projects in $P\setminus
P_{\text{quota}}$ can be either open or closed and a max-cost circulation in
this instance corresponds to a maximum weight matching that opens all projects
in $\hat{P}$ and can choose to open any number of projects in $P\setminus
P_{\text{quota}}$. Therefore by iterating over all possible projects with a
non-unit lower quota, we can find the maximum weight matching. ∎

See 9

###### Proof

We reduce from the problem exact unique hitting set as defined in Section 2.
As our input we are given a set of elements $X=\\{x_{1},\dots,x_{n}\\}$, a set
of subsets $\mathcal{T}\subseteq 2^{X}$

For each element $x_{i}\in X$ let $T_{i}\subseteq\mathcal{T}$ be the set of
sets in which the element $x_{i}$ appears. For each $x_{i}\in X$ we create a
project $p_{x_{i}}$ with upper and lower quota $\lvert T_{i}\rvert$. Further
we create a _last-resort project_ $p^{-}$ with upper and lower quota
$\lvert\mathcal{T}\rvert$. Next for each
$T=\\{\hat{x}_{1},\dots,\hat{x}_{\ell}\\}\in\mathcal{T}$ we create an
applicant $a_{T}$ with preference list $p_{\hat{x}_{1}}\succ\ldots\succ
p_{\hat{x}_{\ell}}\succ p^{-}$. Note that the ordering of the non-last-resort
projects is arbitrary. Now let $M$ be the matching that matches all applicants
to $p^{-}$.

First we assume that there is an exact unique hitting set $H$ of size $k$ and
construct a matching $M^{\prime}$ that dominates $M$. For each
$T\in\mathcal{T}$ there is exactly one $x_{i}\in T\cap H$. We add
$(a_{T},p_{x_{i}})$ to our new matching $M^{\prime}$. Since the hitting set is
unique, for every $x_{i}\in H$ the project $p_{x_{i}}$ meets their quota
exactly. Thus $M^{\prime}$ is feasible. Furthermore, $M^{\prime}$ dominates
$M$ because in $M^{\prime}$ every applicant is matched to a project she
prefers to $p^{-}$. From this follows that $M$ was not Pareto optimal.

Next assume that there is a matching that opens exactly $k$ projects and
dominates $M$. Let $H\subseteq X$ be the set of elements whose projects are
open. Since the lower quota of each element is exactly the number of sets this
element appears in, each set must be covered by exactly one element of $H$.
Thus $H$ must be an exact unique hitting set.

For popv-ha${}_{L}^{U}$ we can mostly follow the reduction, except that we set
the upper and lower quota of $p^{-}$ to $2n-1$ and we add $n-1$ dummy
applicants, each of whom only has $p^{-}$ in her preference list. Following
the same argumentation as in the previous proof it is easy to see that the
matching that matches all applicants to $p^{-}$ is popular if and only if no
exact unique hitting set exists, since else we can construct a matching for
which there is one more applicant who prefers the new matching to $M$, than
there are applicants who prefer $M$ to the new matching, by matching all
element projects to their respective sets as in pov-ha${}_{L}^{U}$ case. ∎

See 10

###### Proof

We modify the previous reduction and reduce from x3c instead of exact unique
hitting set. We are again given a set of items $X=\\{x_{1},\dots,x_{3m}\\}$
and a set $\mathcal{T}=\\{T_{1},\dots,T_{k}\\}\subseteq 2^{X}$ of size $3$
subsets and we want to decide whether there is a partition
$T\subseteq\mathcal{T}$ of $X$. First for each $T_{i}\in\mathcal{T}$ we check
if there is another $T_{j}\in\mathcal{T}$ such that $T_{i}\cap
T_{j}=\emptyset$. If there is no such set $T_{j}$ and $\lvert X\rvert>3$, we
can simply remove $T_{i}$ from $\mathcal{T}$ as it cannot be part of any
partition, since no other set could be included.

After this we follow the previous reduction and add one project $p_{i}$ for
each $T_{i}\in\mathcal{T}$ with upper and lower quota $3$ and a last-resort
project $p^{-}$ with lower and upper quota $6m-1$. We again add one applicant
$a_{x}$ per element $x\in X$ with preference list
$p_{i_{1}}\succ_{a_{x}}p_{i_{2}}\succ_{a_{x}}p_{i_{3}}\succ_{a_{x}}p^{-}$,
where the projects correspond to the three sets $T_{i_{1}},T_{i_{2}}$, and
$T_{i_{3}}$ in which $x$ appears. We also add $3m-1$ dummy applicants, each of
whom only has $p^{-}$ on their preference list. Exactly as in the previous
proofs, the matching that assigns every applicant to $p^{-}$ is popular if and
only if an exact cover exists. Furthermore any matching opening only one of
the projects corresponding to sets cannot be popular, since we can always open
a second project with different applicants, since we required that any set has
another that is disjoint from it. Thus there is a popular matching with
exactly one open project if and only if there is no exact cover. The result
for perpo-ha${}_{L}^{U}$ simply follows by removing the dummy agents. ∎

See 11 We again split this theorem into four separate statements in the
appendix for better readability.

###### Theorem 15

Given an instance $\mathcal{I}$ of perpo-ha${}_{L}^{U}$ and parameter
$m_{\text{closed}}$, it is ${\mathrm{W[1]}}$-hard to decide whether a perfect
Pareto optimal matchings exists that closes exactly $m_{\text{closed}}$
projects.

###### Proof

We reduce from the multicolored independent set Problem. Here we are again
given a graph $G=(V,E)$ together with a partition of the vertices into $k$
color classes $V_{1},\dots,V_{k}$ and our goal is to find an independent set
with exactly one vertex per class. We again assume that each color class has
exactly $q$ vertices.

####  7.5.14 Construction

First we introduce the projects we add to our construction.

  * •

For each $v\in V$ we create one _vertex project_ $p_{v}$ with lower and upper
quota $q$.

  * •

For each edge $e\in E$ we create one _edge project_ $p_{e}$ with lower and
upper quota $2q+1$.

  * •

For each combination of colors $(c,d)\in[k]\times[k]$ with $c\neq d$ we create
a _two-color project_ $p_{c,d}$ with lower and upper quota $1$.

Now we turn to the applicants.

  * •

For each color $c\in[k]$ and pair of vertices $(v,u)\in V_{k}^{2}$ with $v\neq
u$ we create an applicant $a_{v,u}$ with preference list $p_{v}\succ p_{u}$.

  * •

For each $e=\\{u,v\\}\in E$ with $v\in V_{c}$ and $u\in V_{d}$ we add $2q$
_edge applicants_ $a_{e}^{1},\dots,a_{e}^{2q}$ each with preference list
$p_{u}\succ p_{v}\succ p_{e}$ and one _dummy applicant_ $a_{e}$ with
preference list $p_{c,d}\succ p_{e}$.

Finally we set $m_{\text{closed}}\coloneqq k+{k\choose 2}.$

####  7.5.15 $\Rightarrow$

####  7.5.16 Matching construction

First we assume that we have a multicolored independent set
$v_{1},\dots,v_{k}$ with $v_{c}\in V_{c}$ for $c\in[k]$. We now construct a
perfect Pareto optimal matching $M$ by matching

  * •

for any edge $e\in E$ all edge applicants to $p_{e}$;

  * •

for any color $c\in[k]$ and $v\in V_{c}\setminus\\{v_{c}\\}$ all applicants in
$\\{a_{v,u}\mid u\in V_{c}\setminus\\{v\\}\\}$ and $a_{v_{c},v}$ to $p_{v}$.

It is easy to see that $M$ closes exactly the projects
$p_{v_{1}},\dots,p_{v_{k}}$ and all two-color projects, thus closing exactly
$m_{\text{closed}}=k+{k\choose 2}$ projects. Also since all applicants are
matched, $M$ is perfect.

####  7.5.17 Pareto optimality

In order to show that $M$ is Pareto optimal, we go over all applicants and
show that they cannot improve without any other applicant getting worse.

  * •

For any color $c\in[k]$ and any vertices $v,u\in V_{c}$ with $v\neq v_{c}$ the
applicant $a_{v,u}$ cannot improve since she is matched to her top choice in
$M$.

  * •

For the applicant $a_{v_{c},v}$ the only possibility to improve is to open the
project $p_{v_{c}}$, but the only applicants who prefer this project to their
current project are all $q$ projects in $\\{a_{v_{c},v}\mid v\in
V_{c}\setminus\\{v_{c}\\}\\}$ and all edge projects corresponding to edges
adjacent to $v_{c}$. Therefore if we match $a_{v_{c},v}$ to $p_{v_{c}}$, then
at least $1$ but at most $q-1$ applicants corresponding to any edge can be
matched to this project. This leaves at least one edge, such that $q+1$ of
their edge applicants need a new project. But since their only possibility for
this would be the other vertex project corresponding to the other vertex of
the edge which has an upper quota of $q$, this would imply that at least one
applicant would get worse compared to $M$. Therefore the applicant $a_{v_{c}}$
cannot improve.

  * •

Let $e=\\{u,v\\}\in E$, and without loss of generality assume that $a_{e}^{1}$
should improve. Then they and all other $2q-1$ applicants should be either
matched to $p_{v}$ or $p_{u}$. Since $e$ is an edge, either $u$ or $v$ is not
in the independent set and therefore there is at least one top choice
applicant matched to the corresponding project that would be unmatched in case
of all $2q$ edge applicants being matched.

Thus no applicant can improve and $M$ is Pareto optimal.

####  7.5.18 $\Leftarrow$

Now assume that we have a perfect Pareto optimal matching $M$ with exactly
$k+{k\choose 2}$ closed projects. First, since $M$ is perfect (so every
applicant needs to be matched) at most $k$ vertex projects can be closed. Next
we notice that there are exactly ${k\choose 2}$ two color projects.

  * •

Since for any closed edge project $p_{e}$, the applicant $a_{e}$ would need to
be matched to the corresponding two color project and the applicants
$a_{e}^{1},\dots,a_{e}^{2q}$ would need to be matched to a vertex project with
no vertex applicants. This implies that in any perfect matching with
$k+{k\choose 2}$ closed projects, all edge projects must be open since
otherwise two of the $k+{k\choose 2}$ possible closed projects would be open.

  * •

Due to the perfect requirement there can be at most one vertex project
$p_{v_{c}}$ closed per color $c\in[k]$.

  * •

Because we have a Pareto optimal matching there cannot be any two closed
projects $p_{v_{c}}$ and $p_{v_{d}}$ with $c,d\in[k]$ with an edge $e$ between
them, since otherwise matching $a_{e}$ to $p_{c,d}$,
$a_{e}^{1},\dots,a_{e}^{q}$ to $p_{v_{c}}$ and $a_{e}^{q},\dots,a_{e}^{2q}$ to
$p_{v_{d}}$ would dominate $M$.

Therefore the set of vertices corresponding to the closed projects in $M$ is a
multicolored independent set. ∎

###### Theorem 16

Given an instance $\mathcal{I}$ of pov-ha${}_{L}^{U}$, parameter
$m_{\text{closed}}$, and matching $M$, it is ${\mathrm{W[1]}}$-hard to decide
whether matching exists that closes exactly $m_{\text{closed}}$ projects and
dominates $M$.

###### Proof

We reduce from the multicolored clique problem. For this we are again given a
graph $G=(V,E)$ with a partition into color classes $V_{1},\dots,V_{k}$ and
our goal is to find a clique adhering to this partition. For simpler notation
we assume that the graph induced by each color class is an independent set.
This allows us to use clique and multicolored clique interchangeably and we
can ensure that edges are always between two different colors in our
construction.

####  7.5.19 Construction

First as our projects we include

  * •

for each $v\in V$, a _vertex project_ $p_{v}$ with lower and upper quota
$k-1$;

  * •

for each edge $e\in E$, an _edge project_ $p_{e}$ with lower and upper quota
$2$;

  * •

for each color $c\in[k]$, a _color project_ $p_{c}$ with lower and upper quota
$k-1$.

Our applicants will be the following.

  * •

For each color $c\in[k]$ and vertex $v\in V_{c}$, we add $k-1$ _vertex
applicants_ $a_{v}^{1},\dots,a_{v}^{k-1}$, each with preference list
$p_{c}\succ p_{v}$.

  * •

For each edge $e=\\{u,v\\}\in E$, we include two _edge applicants_ ,
$a_{e}^{u}$ with preference list $p_{u}\succ p_{e}$ and $a_{e}^{v}$ with
preference list $p_{v}\succ p_{e}$.

Our matching $M$ now matches all vertex applicants to their corresponding
vertex project, i.e., it matches all applicants in
$\\{a_{v}^{1},\dots,a_{v}^{k}\\}$ to $p_{v}$, and it matches all edge
applicants to their edge project. Finally we set
$m_{\text{closed}}\coloneqq{k\choose 2}$

####  7.5.20 $\Rightarrow$

Let us assume we have a clique $C=\\{v_{1},\dots,v_{k}\\}$ with $v_{c}\in
V_{c}$ for $c\in[k]$. Then we take the matching $M^{\prime}$ such that

  * •

For any color $c\in[k]$ the vertex applicants
$a_{v_{c}}^{1},\dots,a_{v_{c}}^{k-1}$ are matched to $p_{c}$, thus improving
over $M$ for all of them.

  * •

For any vertex $v\in V\setminus C$, i.e., $v$ is not in the clique, we match
the vertex applicants $a_{v}^{1},\dots,a_{v}^{k-1}$ are matched to $p_{v}$.

  * •

For any edge $e=(v,u)$ such that $v$ and $u$ are in the clique, we match
$a_{e}^{v}$ to $p_{v}$ and $a_{e}^{u}$ to $p_{u}$, thus improving their
matching.

  * •

For any edge $e=(v,u)$ such that at least one of $v$ and $u$ is not in the
clique, we match $a_{e}^{v}$ and $a_{e}^{u}$ to $p_{e}$.

The matching $M^{\prime}$ does not make any applicant worse, adheres to the
lower and upper quotas, due to each vertex in the clique having exactly $k-1$
neighbors in the clique and closes exactly the ${k\choose 2}$ projects
corresponding to the edges between the vertices in the clique.

####  7.5.21 $\Leftarrow$

Assume that we have a matching dominating $M$, which closes exactly ${k\choose
2}$ projects. It is easy to see that the only way to close ${k\choose 2}$
projects while simultaneously matching all applicants is to close ${k\choose
2}$ edge projects, matching the edge applicants to the corresponding vertex
projects and the vertex applicants to the color projects. This however implies
that all vertices corresponding to promoted vertex projects must have an edge
to all the other vertices, thus forming a multicolored clique. ∎

###### Corollary 4

Given an instance $\mathcal{I}$ of popv-ha${}_{L}^{U}$, parameter
$m_{\text{closed}}$, and matching $M$, it is ${\mathrm{W[1]}}$-hard to decide
whether matching exists that closes exactly $m_{\text{closed}}$ projects and
is more popular than $M$.

###### Proof

Instead of having $k$ color projects, we just have one selection project
$p_{s}$ with lower quota $k(k-1)$ which is ranked lowest by all vertex
projects and we add one selection applicant $a_{s}$ who only ranks $p_{s}$.
Then the matching $M$ from the last proof is obviously less popular than the
matching $M^{\prime}$ assigning all the edge applicants as in the last proof,
while all the vertex applicants and the selection applicant to the selection
project. Furthermore since the votes of vertex and edge projects cancel each
other out, the only way to get a more popular matching closing exactly
${k\choose 2}$ projects is to match the selection gadget and also $k(k-1)$
edge applicants, which just as in the last proof implies the existence of a
clique. ∎

###### Theorem 17

Given an instance $\mathcal{I}$ of pop-ha${}_{L}^{U}$ and parameter
$m_{\text{closed}}$, it is ${\mathrm{W[1]}}$-hard to decide whether a popular
matching exists that closes exactly $m_{\text{closed}}$ projects, even if
$\mathcal{I}$ does not admit any other popular matching.

###### Proof

We again reduce from the multicolored clique problem, where we are given a
graph $G=(V,E)$ with partition $V_{1},\dots,V_{k}$ of the vertices of $G$.

####  7.5.22 Construction

As our main projects we include

  * •

for each color $c\in[k]$ a _color project_ $p_{c}$ with lower and upper quota
$k$;

  * •

for each vertex $v\in V$ a _vertex project_ $p_{v}$ with lower and upper quota
$k$;

  * •

for each vertex $v\in V$ a _vertex project_ $p_{v}$ with lower and upper quota
$k$;

  * •

for each edge $e\in E$ an _edge project_ $p_{e}$ with lower and upper quota
$2$.

Further as our _dummy projects_ we include

  * •

three _dummy color projects_ $p_{C,1},p_{C,2},p_{C,3}$;

  * •

six _dummy vertex projects_ $p_{V,1},p_{V,2},p_{V,3},p_{V,4},p_{V,5},p_{V,6}$;

  * •

three _dummy edge projects_ $p_{E,1},p_{E,2},p_{E,3}$,

with all dummy projects having a lower and upper quota of $1$.

Our non-dummy applicants are as follows.

  * •

For each color $c\in[k]$ and vertex $v\in V_{c}$ we add $k-1$ _vertex
applicants_ $a_{v}^{1},\dots,a_{v}^{k-1}$ with preference list $p_{c}\succ
p_{v}\succ p_{V,4}\succ p_{V,5}\succ p_{V,6}$.

  * •

For each edge $e=\\{u,v\\}$ we add two _edge applicants_ $a_{e}^{u}$ with
preference list $p_{u}\succ p_{e}\succ p_{E,1}\succ p_{E,2}\succ p_{E,3}$ and
$a_{e}^{v}$ with preference list $p_{v}\succ p_{e}\succ p_{E,1}\succ
p_{E,2}\succ p_{E,3}$.

Finally our dummy applicants will be as follows.

  * •

For each color $c\in[k]$ and vertex $v\in V_{c}$ we add one _vertex dummy
applicant_ $a_{v}^{D}$ with preference list $p_{v}\succ p_{V,1}\succ
p_{V,2}\succ p_{V,3}$.

  * •

For each color $c\in[k]$ we add one _color dummy applicant_ $a_{c}^{D}$ with
preference list $p_{c}\succ p_{C,1}\succ p_{C,2}\succ p_{C,3}$.

  * •

We add two _common color dummy applicants_ $a_{C,1},a_{C,2}$ with preference
list $p_{C,1}\succ p_{C,2}\succ p_{C,3}$.

  * •

We add two _common vertex dummy applicants_ $a_{V,1},a_{V,2}$ with preference
list $p_{V,1}\succ p_{V,2}\succ p_{V,3}$.

  * •

We add two _common enforcing vertex dummy applicants_ $a_{V,3},a_{V,4}$ with
preference list $p_{V,4}\succ p_{V,5}\succ p_{V,6}$.

  * •

Finally we add two _common edge dummy applicants_ $a_{E,1},a_{E,2}$ with
preference list $p_{E,1}\succ p_{E,2}\succ p_{E,3}$.

This construction heavily relies on Observation 2. The vertex dummy applicants
guarantee that in each popular matching each vertex project must be open and
the dummy color applicants guarantee that each color project must be open.
Similarly the common enforcing vertex dummy applicants force every vertex
applicant to be matched and the common edge dummy applicants force every dummy