11institutetext:  ELTE Eötvös Loránd University, Budapest, Hungary
22institutetext: HUN-REN Centre for Economic and Regional Studies, Budapest,
Hungary

# A Simple 1.5-approximation Algorithm for a Wide Range of Maximum Size Stable
Matching Problems

Gergely Csáji 1122

###### Abstract

We give a simple approximation algorithm for a common generalization of many
previously studied extensions of the maximum size stable matching problem with
ties. These generalizations include the existence of critical vertices in the
graph, amongst whom we must match as much as possible, free edges, that cannot
be blocking edges and $\Delta$-stabilities, which mean that for an edge to
block, the improvement should be large enough on one or both sides. We also
introduce other notions to generalize these even further, which allows our
framework to capture many existing and future applications. We show that the
edge duplicating technique allows us to treat these different types of
generalizations simultaneously, while also making the algorithm, the proofs
and the analysis much simpler and shorter than in previous approaches. In
particular, we answer an open question by Askalidis et al. [1] about the
existence of a $\frac{3}{2}$-approximation algorithm for the Max-SMTI problem
with free edges. This demonstrates that this technique can grasp the
underlying essence of these problems quite well and have the potential to be
able to solve many future applications.

##  1 Introduction

Preference based matching markets is an extensively studied topic in computer
science, mathematics and economics literature. The intensive study of the area
started back in 1962 after the seminal paper of Gale and Shapley [7]. They
defined the model for the stable marriage problem and showed that a stable
matching always exists and can be found in linear time. Since then, countless
applications and related models have been studied, see Manlove [17] for an
overview. Applications include Resident allocation, University admissions,
Kidney exchanges, job markets and much more.

###  1.1 Related work

In the stable marriage problem, the goal is to match two classes of agents in
a way such that there are no blocking edges, i.e. pairs of agents who mutually
consider each other better than their partner. The _stable marriage problem
with ties and incomplete lists_ (smti) was first studied by Iwama et al. [12],
who showed the NP-hardness of Max-SMTI, which is the problem of finding a
maximum size stable matching in an SMTI instance. Since then, various
algorithms have been proposed to improve the approximation ratio, e.g. Iwama
et al. [11, 10] and Király [13], and the current best ratio is $\frac{3}{2}$
by a polynomial-time algorithm of McDermid [18], where the same ratio is
attained by linear-time algorithms of Pauluch [20, 21] and Király [14, 15].
This $\frac{3}{2}$-approximation has been extended to critical relaxed stable
matchings by a very recent paper of Nasre et al. [19], which is a
generalization of Max-SMTI, where there is a set of critical agents, amongst
whom we must match as much as possible and stability is generalized in an
appropriate way. Critical relaxed stability has also been studied in Krishnaa
et al. [16], where they showed that a critical relaxed stable matching always
exists, but finding a maximum size such matching is NP hard to approximate
within $\frac{21}{19}-\varepsilon$, even with only strict preferences.

The approximation algorithm for Max-SMTI has also been extended to some
cardinal and matroidal generalizations as well by Csáji et al. [4]. This
include for example common quotas and $\Delta$-min-stability, where there is a
number $\Delta$, and blocking is relaxed in a way such that only those edges
can block, where both participating agents improve by at least $\Delta$. The
matroidal generalization of stable matching was introduced in Fleiner [6].

As for the inapproximability of Max-SMTI, Halldórssson et al. [8] showed that
it is NP-hard to approximate it within some constant factor. Later,
inapproximability results have been improved, especially assuming stronger
complexity theoretic conjectures. Yanagisawa [22] and Halldórsson et al. [9]
showed that assuming the Unique Games Conjecture, there is no
$\frac{4}{3}-\varepsilon$-approximation for any $\varepsilon>0$. By a recent
work by Dudycz et al. [5] it follows that assuming the Small Set Expansion
Hypothesis or the strong-UGC, there cannot even be a
$\frac{3}{2}-\varepsilon$-approximation algorithm for Max-SMTI.

Stable matchings with free edges - that is, edges that can be included in a
matching, but cannot block - have also been studied in many papers. Askalidis
et al. [1] proved that with strict preferences and free edges, finding a
maximum size stable matching can be $\frac{3}{2}$-approximated in polynomial
time. However, on the negative side they showed that the problem does not
admit a polynomial time $\frac{21}{19}-\varepsilon$ approximation algorithm
unless $P=NP$ and assuming the Unique Games Conjecture, it does not even admit
a $\frac{3}{2}-\varepsilon$ approximation. These negative results also hold
with respect to strict preferences. They posed as an open question whether
this $\frac{3}{2}$-approximation can be extended to weak preferences. In this
paper we answer this question positively. Cechlárová and Fleiner [2]
investigated the stable roommates problem with free edges and proved NP-
hardness even in very restricted settings.

###  1.2 Our Contributions

In this paper we extend the $\frac{3}{2}$-approximation algorithm for Max-SMTI
for a common generalization of many previously introduced and studied
concepts. In particular, we answer an open question posed by Askalidis et al.
[1] about the existence of a $\frac{3}{2}$-approximation algorithm for the
Max-SMTI problem with free edges. We utilize a recently introduced edge
duplicating technique by Yokoi [23] and Csáji et al. [4] and show that with
the help of this technique, we are able to solve much harder and more general
related problems in a lot simpler and more elegant way. We give a simple
approximation algorithm for a framework that includes free edges, critical
vertices, critical edges, capacities, matroid constraints, many cardinal
stability notions and more. First, we describe our algorithm for the one-to-
one bipartite matching case in Section 3. Then, we extend it to the most
general case with matroidal constraints in Section 4.

Although both our algorithm and our analysis are quite simple and elegant, we
emphasize that our method can solve many problems that previously took whole
papers in highly rated journals and conferences to tackle and also answers a
decade long open question.

##  2 Preliminaries

We investigate matching markets, where the set of agents with the possible set
of contracts is given by a bipartite graph $G=(U,W;E)$, where vertices
correspond to agents and edges correspond to possible, mutually acceptable
contracts. For each agent $v\in U\cup W$, let $E(v)$ denote the edges that are
incident to $v$. We assume that for each agent $v$, there is a preference
function $p_{v}:E(v)\to\mathbb{R}_{\geq 0}$, which defines a weak ranking over
the incident edges of $v$. We emphasize that we assume that the agents
(vertices) rank their incident edges instead of the adjacent agents on the
other side, because we allow parallel edges in our model, representing
multiple types of contracts between two given agents. We also assume that
$p_{v}(\emptyset)\leq 0$, which denotes that an agent always weakly prefers to
be matched to any acceptable partners rather than being unmatched.

We say that an edge set $M\subseteq E$ is a matching, if $|M\cap E(v)|\leq 1$
for each $v\in U\cup W$. For a vertex $v$, let $M(v)$ denote the edge incident
to $v$ in $M$, if there is any, otherwise $M(v)$ is $\emptyset$. We say that
an edge $e=(u,w)\notin M$ blocks a matching $M$, if $p_{w}(e)>p_{w}(M(w))$ and
$p_{u}(e)>p_{u}(M(u))$ holds, that is, both agents strictly prefer each other
to their partners in $M$. A matching $M$ is called weakly stable or just
stable, if there is no blocking edge to $M$. The problem of finding a maximum
size weakly stable matching in a bipartite graph with weak preferences, called
Max-SMTI is a well studied problem that is NP-hard even to approximate within
some constant, but admits a linear time $\frac{3}{2}$-approximation.

We continue by introducing the generalizations that we consider. We start with
$\Delta$-min and $\Delta$-max stability, which were introduced in Csáji et al.
[4] (a similar notion to $\Delta$-min stability has also been defined in Chen
et al. [3]). The motivation behind these notions is that in many applications,
blocking pairs may only arise if one or both member of the pair improves by a
significant enough amount.

Let $\Delta>0$ be a constant. A matching $M$ is $\Delta$-min-stable, if there
is no blocking edge $e=(u,w)$ with respect to $M$, such that
$\min\\{p_{u}(e)-p_{u}(M(u)),p_{w}(e)-p_{w}(M(w))\\}\geq\Delta$, that is, both
agents improve by at least $\Delta$. The motivation behind this is clear: if a
blocking does not result in a significant improvement, it may not even worth
the effort.

A matching $M$ is $\Delta$-max-stable, if there is no blocking edge $e=(u,w)$
with respect to $M$, such that
$\max\\{p_{u}(e)-p_{u}(M(u)),p_{w}(e)-p_{w}(M(w))\\}\geq\Delta$, that is, one
of the improvements is at least $\Delta$. Note here, that the edge $e$ still
must be a blocking edge, so both $p_{u}(e)-p_{u}(M(u))>0$ and
$p_{w}(e)-p_{w}(M(w))>0$ are assumed. The motivation behind this notion is
that in many cases, it may be enough that one agent can improve by a
sufficiently large amount to initiate a blocking contract, and the other agent
only has to accept it, so for him even a smaller improvement is enough. By
choosing $\Delta$ to be small enough, it is easy to see that both of these
stability notions strictly generalize weak stability.

Now we define critical matchings and relaxed stability, as they were defined
in a very recent work of Krishnaa et al. [16]. For this, let us suppose that
there is a set $C\subseteq U\cup W$ of critical vertices. Criticality means
that we want to match as many of them as possible in any matching. We say that
a matching $M$ is critical, if there is no other matching $M^{\prime}$, such
that $M^{\prime}$ covers strictly more vertices from $C$, than $M$. Of course,
there may not be a matching that is both critical and weakly stable. Hence, we
need a weaker notion of stability, called relaxed stability. A matching $M$ is
relaxed stable, if there is no blocking pair $e=(u,w)$ to $M$, such that
$M(u)$ and $M(w)$ are not critical vertices. The motivation behind this
definition is that since we want to maximize the number of matched critical
agents, we do not allow blocking pairs, where one of the participating agents
would leave a critical agent unmatched. We will slightly strengthen this
notion of stability for the following reason: this does not allow a pair
consisting of an unmatched critical agent and another agent whose partner is
critical to block. However, after letting the agents of such a blocking pair
to be matched together, the number of critical agents covered remains to same,
(so maximal), hence such a pair indeed should be able to block. We will show
that this strengthening of stability is still enough to guarantee existence.

Now we generalize the concept of criticality and relaxed stability in a
natural way. Suppose that there is a set $E_{c}$ of critical edges too. This
represents that it may be also important that we match the critical agents
with specific types of contracts, or to certain other agents that are good
enough for them, or more compatible with them in some way. For a matching $M$,
let $M_{c}=M\cap E_{c}$ denote the critical edges of $M$. We say that a
matching $M$ is critical, if there is no matching $N$, such that $N_{c}$
covers strictly more critical vertices than $M_{c}$. A matching $M$ is
critical relaxed stable, if it is critical and there is no blocking edge
$e=(u,w)$, such that $M\setminus\\{(u,M(u)),(M(w),w)\\}\cup\\{e\\}$ is still
critical. The special case of only critical vertices can be obtained by
choosing $E=E_{c}$.

Finally we introduce the notion of free agents and free edges. In Askalidis et
al. [1], free edges were used to model stable matching instances, where there
are friendship and business relations which restrict certain edges from
blocking. Let us suppose there is a set $F\subseteq E$ of free edges and a set
$F_{A}\subseteq U\cup W$ of free agents. Free agents cannot participate in any
blocking edge, while free edges cannot be blocking edges. Hence, a matching
$M$ is stable in this instance, if for each blocking edge $(u,w)$ it holds
that $|\\{u,w\\}\cap F_{A}|\geq 1$ or $(u,w)\in F$. Clearly, we can model free
agents with free edges only: just make each edge adjacent to a free agent a
free edge.

Next we define a nice common generalization of $\Delta$-min/max stablity and
the notion of free edges. Here we suppose that for each edge $e=(u,w)$, there
are two numbers $\gamma_{e}^{u}>0$ and $\gamma_{e}^{w}>0$ given. We say that a
matching is $\gamma$-min stable, if there is no blocking edge $e=(u,w)$ such
that $p_{u}(e)-p_{u}(M(u))\geq\gamma_{e}^{u}$ and
$p_{w}(e)-p_{w}(M(w))\geq\gamma_{e}^{w}$ holds. Similarly, a matching is
$\gamma$-max stable, if there is no blocking edge $e=(u,w)$ such that
$p_{u}(e)-p_{u}(M(u))\geq\gamma_{e}^{u}$ or
$p_{w}(e)-p_{w}(M(w))\geq\gamma_{e}^{w}$ holds. The case of
$\Delta$-stabilites with a set $F\subseteq E$ of free edges corresponds to the
very special case, when $\gamma_{e}^{v}=\infty$, if $e\in F$ and
$\gamma_{e}^{v}=\Delta$ otherwise. Hence, in our model, we allow very
different types of conditions for each edge to block, independently from each
other, which can incorporate many other special properties of certain
applications. For example, if one thinks about job markets, and assumes that
the underlying preferences are in correspondence with the salaries of the
positions, there may be many other aspects of a workplace that make it
desirable. Hence, for each agent and each different company and position, the
increase in the salary that would make a job offer good enough for the
applicant to switch, might be different. Similary, depending on a company’s
existing employees and a new agent, it may depend on the specific skills of a
new agent that are relevant for the company, how large of a salary within a
contract would be worth it for the company to switch from an existing employee
to the new one in a blocking pair.

Putting it all together, we define a general model, which incorporates all of
the previously discussed ones. Suppose we are given a set $C\subseteq U\cup W$
of critical vertices, a set $E_{c}\subseteq E$ of critical edges and
$\gamma_{e}^{v}$ values for each pair $(e,v)\in E\times(U\cup W)$ such that
$v\in e$. We say that a matching $M$ is c$\gamma$-min stable, if $M$ is
critical and there is no blocking edge $e=(u,w)$, such that
$M\setminus\\{(u,M(u)),(M(w),w)\\}\cup\\{e\\}$ is still critical, and
$\min\\{p_{u}(e)-p_{u}(M(u))-\gamma_{e}^{u},p_{w}(e)-p_{w}(M(w))-\gamma_{e}^{w}\\}\geq
0$ both hold. Otherwise, we call such a blocking edge a $c\gamma$-min blocking
edge. Clearly, this generalizes all three concepts: $\Delta$-min stability,
free edges and critical vertices. Similarly we can define c$\gamma$-max stable
matchings by replacing
$\min\\{p_{u}(e)-p_{u}(M(u))-\gamma_{e}^{u},p_{w}(e)-p_{w}(M(w))-\gamma_{e}^{w}\\}\geq
0$ with
$\max\\{p_{u}(e)-p_{u}(M(u))-\gamma_{e}^{u},p_{w}(e)-p_{w}(M(w))-\gamma_{e}^{w}\\}\geq
0$.

In order to be able to solve both problems with the same algorithm, let us go
even one step further and consider a common generalization of the above two
problems that we describe now. Instead of one $\gamma_{e}^{u}$, we have values
$0<\gamma_{e}^{u}<\delta_{e}^{u}$ for each vertex-edge pair. We say that an
edge $e=(u,w)$ $c\gamma$-blocks a matching $M$, if
$M\setminus\\{(u,M(u)),(M(w),w)\\}\cup\\{e\\}$ is still critical, and either
$\min\\{p_{u}(e)-p_{u}(M(u))-\gamma_{e}^{u},p_{w}(e)-p_{w}(M(w))-\delta_{e}^{w}\\}\geq
0$ or
$\min\\{p_{u}(e)-p_{u}(M(u))-\delta_{e}^{u},p_{w}(e)-p_{w}(M(w))-\gamma_{e}^{w}\\}\geq
0$ holds. We say that a matching $M$ is $c\gamma$-stable, if $M$ is critical
and there is no edge that $c\gamma$-blocks $M$.

If the $\gamma_{e}^{v}$ values are sufficiently small, then this corresonds to
$c\gamma$-max stability, and when the $\gamma_{e}^{v}$ and $\delta_{e}^{v}$
values are sufficently close, then it corresponds to $c\gamma$-min stability.

Now we define the optimization problem we investigate, called Maximum
$c\gamma$-stable matching with ties, incomplete preferences and critical edges
abbriviated as Max-$c\gamma$-smti for short.

Max-$c\gamma$-smti In: A bipartite graph $G=(U,W;E)$, $p_{v}()$ preference
valuations for each $v\in U\cup W$, a set $C\subseteq U\cup W$ of critical
vertices, a set $E_{c}\subseteq E$ of critical edges, numbers
$0<\gamma_{e}^{v}<\delta_{e}^{v}$ for each pair $(e,v)\in E\times(U\cup W)$
such that $v\in e$. Out: A maximum size $c\gamma$-stable matching $M$

The main result of the paper is a simple $\frac{3}{2}$-approximation algorithm
for Max-$c\gamma$-smti.

##  3 The Algorithm

We start by describing a high level view of the algorithm. Let $I$ be an
instance of Max-$c\gamma$-smti.

1\. Create an instance $I^{\prime}$ of the stable marriage problem with strict
preferences by making parallel copies of each edge and create strict
preferences over the created edges.

2\. Run the Gale-Shapley algorithm to obtain a stable matching $M^{\prime}$ in
the new instance $I^{\prime}$

3\. Take the projection $M$ of $M^{\prime}$ to $I$ by taking an edge $e$
inside $M$, whenever one of the parallel copies of $e$ was inside
$M^{\prime}$.

The intuition behind this algorithm is the following. Our goal is a stable
matching that is as large as possible. Hence, to help agents not to remain
alone, we create copies for each edge, that allow rejected and unmatched
agents multiple new chances to propose again to the same partner with a new,
stronger contract that is more favorable to the other agent and can be good
enough for her to reject another partner who has been considered better than
the proposing agent before.

###  3.1 The case of $E_{c}=E$

Let us start with the special case when each edge is critical, so only the
number of covered critical vertices matters. Also, this means that $M_{c}=M$
for any matching $M$. The more general case will be solved by the same simple
ideas, however, the many required types of copies make it more difficult to
follow. We describe the algorithm in more detail as follows. Let $I$ be an
instance of Max-$c\gamma$-smti. Let $|C\cap U|=s$ and $|C\cap W|=t$. For each
edge $e=(u,w)\in E$ we create parallel edges as follows

  * –

We create copies $a(e)$, $b_{0}(e),b_{1}(e)$ and $c(e)$,

  * –

If $w\in C\cap W$ is critical we create copies $x_{1}(e),\dots,x_{t}(e)$,

  * –

If $u\in C\cap U$ is critical we create copies $z_{1}(e),\dots,z_{s}(e)$.

Then, we create strict preferences as follows. For a vertex $u\in U$, we rank
the copies according to the rule

$x_{1}\succ\dots\succ x_{t}\succ
a\succeq^{\gamma}b_{0}\succeq^{\delta-\gamma}b_{1}\succ c\succ
z_{s}\succ\dots\succ z_{1}$.
For a vertex $w\in W$, we rank the copies according to the rule

$z_{1}\succ\dots\succ z_{s}\succ
c\succeq^{\gamma}b_{1}\succeq^{\delta-\gamma}b_{0}\succ a\succ
x_{t}\succ\dots\succ x_{1}$.
For any non-$b_{i}$ copy, we rank the edges of the same copy according to the
preference functions $p_{v}()$ by breaking the ties arbitrarily. Here,
$\alpha\succ\beta$ denotes that for any two edges $e,f$, the copy $\alpha(e)$
is ranked higher than the copy $\beta(f)$.

The notation $a\succeq^{\gamma}b_{0}\succeq^{\delta-\gamma}b_{1}$ means that
for any edge $e$, $a(e)\succ_{v}b_{0}(e)\succ_{v}b_{1}(e)$, but
$b_{0}(f)\succ_{v}a(e)$, if and only if $p_{v}(f)\geq p_{v}(e)+\gamma_{f}^{v}$
and $b_{1}(f)\succ_{v}a(e)$ if and only if $p_{v}(f)\geq
p_{v}(e)+\delta_{f}^{v}$. This can be obtained in the following way. For each
vertex $u\in U$ rank the $a$ copies according to $p_{v}()$ by breaking the
ties arbitrarily. Then, we can insert the $b_{0}$ copy of each edge $f$, such
that $b_{0}(f)\succ_{u}a(e)$, if and only if $p_{u}(f)\geq
p_{u}(e)+\gamma_{f}^{u}$. Similarly we can insert the $b_{1}$ copies such that
$b_{1}(f)\succ_{u}a(e)$ if and only if $p_{u}(f)\geq p_{u}(e)+\delta_{f}^{u}$.
For the $W$ side, we do it similarly, according to their ranking. Note that
this definition allows the $b_{i}$ copies to be ranked in a different order
than $p_{v}()$, which is surprising, but necessary. If there are still some
ties remaining, we break them arbitrarily.

We remark another way to create the ranking over the $a,b_{0},b_{1},c$ copies.
For a vertex $u\in U$ and $e=(u,w)$ let $p_{u}(a(e))=p_{u}(e)$,
$p_{u}(b_{0}(e))=p_{u}(e)-\gamma_{e}^{u}$ and
$p_{u}(b_{1}(e))=p_{u}(e)-\delta_{e}^{u}$. Then, for each vertex, these new
(possibly negative) preference number define a weak order, in which we break
ties in a way such that with the same value the $b_{1}$ copies are best, the
$b_{0}$ copies are second and the $a$ copies are last. We can do it similary
for the $W$ side, with the tiebreaking $b_{0}$ first, $b_{1}$ second, $c$
best.

We illustrate the creation of the extended preferences on a concrete example
with the second method. Let $s=t=1$. Let $u\in U$ be an agent with three
adjacent edges $e,f,g$. Let $p_{u}(e)=1$, $p_{u}(f)=3$ and $p_{u}(g)=4$. Also,
let $\gamma_{e}^{u}=1,\gamma_{f}^{u}=2,\gamma_{g}^{u}=2$ and
$\delta_{e}^{u}=2,\delta_{f}^{u}=3,\delta_{g}^{u}=6$. Then,
$p_{u}(a(g))=4,p_{u}(a(f))=3,p_{u}(b_{0}(g))=2,p_{u}(b_{0}(f))=p_{u}(a(e))=1,p_{u}(b_{1}(f))=p_{u}(b_{0}(e))=0,p_{u}(b_{1}(e))=-1,p_{u}(b_{1}(g))=-2$.
Then, the ranking between the copies is the following:

$x_{1}(g)\succ_{u}x_{1}(f)\succ_{u}x_{1}(e)\succ_{u}a(g)\succ_{u}a(f)\succ_{u}b_{0}(g)\succ_{u}b_{0}(f)\succ_{u}a(e)\succ_{u}b_{1}(f)\succ_{u}b_{0}(e)\succ_{u}b_{1}(e)\succ_{u}b_{1}(g)\succ_{u}c(g)\succ_{u}c(f)\succ_{u}c(e)\succ_{u}z_{1}(g)\succ_{u}z_{1}(f)\succ_{u}z_{1}(e)$.

Notice that here $b_{1}(f)\succ_{u}b_{1}(e)\succ_{u}b_{1}(g)$, so for the
$b_{1}$ copy, the edges are not ranked in their original order.

######  Theorem 3.1.

Max-$c\gamma$-smti can be $\frac{3}{2}$-approximated in
$\mathcal{O}((s+t)|E|)$ time, if $E=E_{c}$.

###### Proof.

We prove the theorem in three simple claims. Let $M$ denote the output of the
algorithm and $M^{\prime}$ be its preimage in the extended instance
$I^{\prime}$.

######  Claim.

$M$ is critical.

Proof: Suppose for contradiction that there is a matching $N$, such that $N$
covers strictly more critical vertices than $M$. Then, it must hold that
either $N$ covers more critical vertices from $U$ or more critical vertices
form $W$ than $M$.

Suppose that the first case holds. Then, there is a component $P$ (a path) in
$N\cup M$, such that there is an endpoint $u_{1}\in U\cap C$ that is critical,
but is only matched in $N$, and also more critical vertices are covered in
$N\cap P$, than in $M\cap P$. Let $e_{1}=(u_{1},w_{1})=N(u_{1})$. As $u_{1}$
is critical, we know that the copies
$z_{1}(u_{1},w_{1}),\dots,z_{s}(u_{1},w_{1})$ exist. As $u_{1}$ is not matched
in $M^{\prime}$, the fact that $z_{1}(u_{1},w_{1})$ does not block
$M^{\prime}$ implies that $w_{1}$ is matched in $M^{\prime}$ and with a
$z_{1}$-type edge. Let $z_{1}(u_{2},w_{1})=M^{\prime}(w_{1})$. This
immediately implies that $u_{2}\in U\cap C$, as $z_{1}(u_{2},w_{1})$ exists.
By our assumption on the component (more critical vertices are covered in
$N\cap P$, than in $M\cap P$), $u_{2}$ is matched in $N$ to a vertex $w_{2}$.

As any $z_{2}$ copy is better for $u_{2}$ in $I^{\prime}$, but
$z_{2}(u_{2},w_{2})$ exists and does not block, $z_{j}(u_{3},w_{2})\in
M^{\prime}$ for some $u_{3}\in U$ and $j\leq 2$. Again, we obtain that $u_{3}$
is critical, so by our assumption on the component, $u_{3}$ is matched in $N$
to a vertex $w_{3}$. By iterating this argument, we get that there must be
vertices $u_{1},u_{2},\dots,u_{s+1}\in U$ that are critical, which contradicts
$|U\cap C|=s$.

The second case is analogous.  $\blacksquare$

######  Claim.

The output matching $M$ by the algorithm is $c\gamma$-stable.

Proof: Suppose for contradiction that there is a $c\gamma$-blocking edge
$e=(u,w)$ to $M$.

If $u$ is unmatched, then $g=(u^{\prime},w)=M(w)$ exists. As $e$
$c\gamma$-blocks and $M$ is critical, we get that $u\in C$ if and only if
$u^{\prime}\in C$. Hence, the best copy of $e$ and $g$ for $w$ has the same
type, either $z_{1}(e)$ or $c(e)$. In both cases, we get that this copy of $e$
blocks $M^{\prime}$ as these copies are both ranked according to $p_{w}()$,
contradiction. If $w$ is unmatched, $x_{1}(e)$ or $a(e)$ blocks $M^{\prime}$
for similar reasons, contradiction.

Hence, $M(u)=f=(u,w^{\prime})$ and $M(w)=g=(u^{\prime},w)$ is not $\emptyset$.
Because $e$ $c\gamma$-blocks, $p_{u}(e)\geq p_{u}(f)+\gamma_{e}^{u}$ and
$p_{w}(e)\geq p_{w}(g)+\delta_{e}^{w}$ or $p_{u}(e)\geq
p_{u}(f)+\delta_{e}^{u}$ and $p_{w}(e)\geq p_{w}(g)+\gamma_{e}^{w}$. Also, as
$e$ $c\gamma$-blocks, the vertices $u^{\prime},w^{\prime}$ cannot be critical,
so $x_{1}(f),\dots,x_{t}(f),z_{1}(g),\dots,z_{s}(g)$ do not exist. Hence, in
the first case $b_{0}(e)$ and in the second case $b_{1}(e)$ blocks
$M^{\prime}$, contradiction.

$\blacksquare$

######  Claim.

For any c$\gamma$-min stable matching $N$ it holds that
$|N|\leq\frac{3}{2}|M|$.

Proof: Suppose for contradiction that there is a $c\gamma$-stable matching $N$
such that $|N|>\frac{3}{2}|M|$. Then, there must be a path component in $N\cup
M$ that is either a single $N$-edge, or consists of two $N$-edges and one
$M$-edge. The first case is clearly impossible, as $M$ is necessarily maximal.

Suppose the second case holds. Let $e=(u_{1},w_{2})$ be the edge of $M$ and
$f=(u_{1},w_{1})$, $g=(u_{2},w_{2})$ be the edges of $N$.

First observe that as $M$ and $N$ are critical, $e$ and $f\cup g$ cover the
same number of critical vertices, so $w_{1},u_{2}$ are not critical and
$x_{1}(f),\dots,x_{t}(f),z_{1}(g),\dots,z_{s}(g)$ does not exists.

As $a(f)$ does not block, $b_{0}(e),b_{1}(e)$, $a(e)$ or $x_{i}(e)\in
M^{\prime}$ for some $i$. As $c(g)$ does not block, $b_{0}(e),b_{1}(e)$,$c(e)$
or $z_{j}(e)\in M^{\prime}$ for some $j$. Hence, $b_{0}(e)$ or $b_{1}(e)\in
M^{\prime}$. If $b_{0}(e)\in M^{\prime}$, then $p_{u_{1}}(e)\geq
p_{u_{1}}(f)+\gamma_{e}^{u_{1}}$ and $p_{w_{2}}(e)\geq
p_{w_{2}}(g)+\delta_{e}^{w_{2}}$ as $M^{\prime}$ is stable, so $e$
$c\gamma$-blocks $N$ (combining with the fact that $e$ and $f\cup g$ cover the
same number of critical vertices), contradiction. The other case implies
$p_{u_{1}}(e)\geq p_{u_{1}}(f)+\delta_{e}^{u_{1}}$ and $p_{w_{2}}(e)\geq
p_{w_{2}}(g)+\gamma_{e}^{w_{2}}$, so $e$ $c\gamma$-blocks $N$, contradiction
again.

$\blacksquare$

The statement follows from these three claims. The running time of the
algorithm is linear in the number of edges of the extended instance, as the
Gale-Shapley algorithm is linear, so it has running time
$\mathcal{O}((s+t)|E|)$. ∎

###  3.2 General case

Next, we discuss the more general case with an arbirtary subset of critical
edges.

We may assume without loss of generality that each critical edge $E_{c}$ is
adjacent to at least one critical vertex, otherwise it cannot cover any
critical vertices, so we get an equivalent instance by making the edge non-
critical.

Let us start by describing the extended instance $I^{\prime}$. For each edge
$e=(u,w)\in E$ we create parallel edges as follows:

  * –

We create copies $a(e)$, $b_{0}(e),b_{1}(e)$ and $c(e)$,

  * –

If $w\in C\cap W$ is critical and $e\in E_{c}$ is also critical, we create
copies $x_{1}(e),\dots,x_{t+7}(e)$

  * –

If $u\in C\cap U$ is critical and $e\in E_{c}$ is also critical, we create
copies $z_{1}(e),\dots,z_{s+7}(e)$

  * –

Finally, if $e\in E_{c}$ is critical and both $u,w\in C$ are critical, we
create a copies $y_{0}(e),y_{1}(e)$

Then, we create strict preferences as follows. Let
$\delta^{\prime}=\delta-\gamma$. For a vertex $u\in U$, we rank the copies
according to the rule

$x_{1}\succeq^{\gamma}x_{2}\succeq^{\delta^{\prime}}x_{3}\succ
x_{4}\succ\dots\succ x_{t+4}\succ z_{s+7}\succeq^{\gamma}(y_{0}\succeq
z_{s+6})\succeq^{\delta^{\prime}}(y_{1}\succeq z_{s+5})\succ
z_{s+4}\succ\dots\succ z_{4}\succ a\succeq^{\gamma}(b_{0}\succeq z_{3}\succeq
x_{t+5})\succeq^{\delta^{\prime}}(b_{1}\succeq z_{2}\succeq x_{t+6})\succ
z_{1}\succ x_{t+7}\succ c$.
For a vertex $w\in W$, we rank the copies according to the rule

$z_{1}\succeq^{\gamma}z_{2}\succeq^{\delta^{\prime}}z_{3}\succ
z_{4}\succ\dots\succ z_{s+4}\succ x_{t+7}\succeq^{\gamma}(y_{1}\succeq
x_{t+6})\succeq^{\delta^{\prime}}(y_{0}\succeq x_{t+5})\succ
x_{t+4}\succ\dots\succ x_{4}\succ c\succeq^{\gamma}(b_{1}\succeq x_{3}\succeq
z_{s+5})\succeq^{\delta^{\prime}}(b_{0}\succeq x_{2}\succeq z_{s+6})\succ
x_{1}\succ z_{s+7}\succ a$.

Here, when we denote $(\alpha\succeq\beta)$ for some types of copies, then it
always means that we insert $\alpha(e)$ and $\beta(e)$ together with
$\beta(e)$ being strictly after $\alpha(e)$ (so no other edge comes between
them) and we keep them together, so in the end for any other edge, either it
is worse than both of them or better than both of them. In the model where we
assign preference values to the copies to create a new ranking, this
corresponds to that these copies always get the same value, so they are tied,
and then we keep them together in the tiebreaking in that order.

The only important thing is that, if we have some copies
$\alpha\succeq^{\gamma}(\beta_{1}\succeq\cdots\succeq\beta_{k})\succeq^{\delta^{\prime}}(\omega_{1}\succeq\cdots\succeq\omega_{l})$,
then for any edge $e$,
$\alpha(e)\succ_{v}\beta_{1}(e)\succ_{v}\cdots\succ_{v}\beta_{k}(e)\succ_{v}\omega_{1}(e)\succ_{v}\cdots\succ_{v}\omega_{l}(e)$
and that for any $i\in[\\{1,\dots,k\\}$ and $j\in\\{1,\dots,l\\}$ it holds
that $\beta_{i}(f)\succ_{v}\alpha(e)$, if and only if $p_{v}(f)\geq
p_{v}(e)+\gamma_{f}^{v}$ and $\omega_{j}(f)\succ_{v}\alpha(e)$ if and only if
$p_{v}(f)\succ p_{v}(e)+\delta_{f}^{v}$.

The edges from copies
$x_{1},x_{4},x_{5},\dots,x_{t+4},x_{t+7},z_{1},z_{4},z_{5}\dots,z_{s+4},$
$z_{s+7},a,c$ are ranked according to $p_{v}()$, the others are then inserted
to the right place as before. In the preference value model, we do this by
computing the corresponding values similarly as in the previous case (with
each copy in a parenthesis getting the same value) and for tie breaking we use
a suitable rule. For example for a vertex $u\in U$, amongst the copies
$a,b_{0},b_{1},z_{2},z_{3},x_{t+5},x_{t+6}$, we can use
$b_{1}\succ_{u}z_{2}\succ_{u}x_{t+6}\succ_{u}b_{0}\succ_{u}z_{3}\succ_{u}x_{t+5}\succ_{u}a$.
The ties between the same type of copies can be broken arbitrarily.

######  Theorem 3.2.

Max-$c\gamma$-smti can be $\frac{3}{2}$-approximated in
$\mathcal{O}((s+t)|E|)$ time.

###### Proof.

We prove the theorem in three simple claims. Let $M$ denote the output of the
algorithm and $M^{\prime}$ be its preimage in the extended instance
$I^{\prime}$.

######  Claim.

$M$ is critical.

Proof: Suppose for contradiction that there is a matching $N$, such that
$N_{c}$ covers strictly more critical vertices than $M_{c}$. Then, it must
hold that either $N_{c}$ covers more critical vertices from $U$ or more
critical vertices from $W$ than $M_{c}$.

Suppose that the first case holds. Then, there is a component (a path) in
$N_{c}\cup M_{c}$, such that there is an endpoint $u_{1}\in U\cap C$ that is
critical, but is only covered in $N_{c}$ and also more critical vertices are
covered in $N_{c}\cap P$, than in $M_{c}\cap P$. Let
$e_{1}=(u_{1},w_{1})=N_{c}(u_{1})$. As $u_{1}$ is critical, we know that the
copies $z_{1}(u_{1},w_{1}),\dots,z_{s+7}(u_{1},w_{1})$ exist. As $u_{1}$ is
not covered with a critical edge in $M$ (as it is uncovered in $M_{c}$), it
can only be matched with an $a,b_{i}$ or $c$ type copy. The fact that
$z_{4}(u_{1},w_{1})$ does not block $M^{\prime}$ implies that $w_{1}$ is
matched in $M^{\prime}$ and with a $z_{j}$-type edge with $j\leq 4$. Let
$(u_{2},w_{1})=M(w_{1})$. This immediately implies that $u_{2}\in U\cap C$ and
$(u_{2},w_{1})\in E_{c}$, as $z_{j}(u_{2},w_{1})$ exists. By our assumption on
the component (more critical vertices are covered in $N_{c}\cap P$, than in
$M_{c}\cap P$), $u_{2}$ is matched in $N_{c}$ to a vertex $w_{2}$.

As any $z_{5}$ copy is better for $u_{2}$ in $I^{\prime}$ than any $z_{j}$
copy with $j\leq 4$, but $z_{5}(u_{2},w_{2})$ exists and does not block,
$z_{j}(u_{3},w_{2})\in M^{\prime}$ for some $u_{3}\in U$ and $j\leq 5$. Again,
we obtain that $u_{3}$ is critical and $(u_{3},w_{2})\in E_{c}$, so by our
assumption on the component, $u_{3}$ is matched in $N_{c}$ to a vertex
$w_{3}$. By iterating this argument, we get that there must be vertices
$u_{1},u_{2},\dots,u_{s+1}\in U$ that are critical, which contradicts $|U\cap
C|=s$.

The second case is analogous.  $\blacksquare$

######  Claim.

The output matching $M$ by the algorithm is $c\gamma$-stable.

Proof: Suppose for contradiction that there is a $c\gamma$-blocking edge
$e=(u,w)$ to $M$.

If $u$ is unmatched, then $g=M(w)=(u^{\prime},w)$ exists. As $e$
$c\gamma$-blocks and $M$ is critical we get that $e\in E_{c}$ if and only if
$g\in E_{c}$ and if yes, then $u^{\prime}\in C$ if and only if $u\in C$. In
particular, we get that the best copy of $e$ and $g$ in $I^{\prime}$ for $w$
is the same. Also, this copy can be only $c,x_{t+7}$ or $z_{1}$ and all these
copies are ranked according to $p_{w}()$. Therefore, this copy of $e$ blocks
$M^{\prime}$, as $e$ $c\gamma$-blocks $M$, contradiction. The case when $w$ is
unmatched is similar.

Hence, $M(u)=f=(u,w^{\prime})$ and $M(w)=g=(u^{\prime},w)$ is not $\emptyset$.
Because $e$ $c\gamma$-blocks, $p_{u}(e)\geq p_{u}(f)+\gamma_{e}^{u}$ and
$p_{w}(e)\geq p_{w}(g)+\delta_{e}^{w}$ or $p_{u}(e)\geq
p_{u}(f)+\delta_{e}^{u}$ and $p_{w}(e)\geq p_{w}(g)+\gamma_{e}^{w}$.

If $f,g\notin E_{c}$, then $e\notin E_{c}$, as $M$ is critical. Hence, only
$a,b_{0},b_{1},c$ copies exists of $e,f,g$. As $e$ $c\gamma$-blocks $M$, we
get that $b_{0}(e)$ or $b_{1}(e)$ blocks $M^{\prime}$, contradiction.

Suppose that $f,g\in E_{c}$. Then, $e\in E_{c}$, $u,w\in C$ and
$u^{\prime},w^{\prime}\notin C$, because $e$ $c\gamma$-blocks. Hence,
$x_{i}(f),z_{j}(g)$ do not exists for any $i,j$, but $y_{0}(e),y_{1}(e)$
exist. As $e$ $c\gamma$-blocks one of $y_{0}(e),y_{1}(e)$ blocks $M^{\prime}$,
contradiction.

Suppose that $f\in E_{c},g\notin E_{c}$. In particular, only
$a(g),b_{0}(g),b_{1}(g),c(g)$ exist of $g$. Then, $e\in E_{c}$ as $e$
$c\gamma$-blocks and $w^{\prime}\in C$ if and only if $w\in C$. If
$w,w^{\prime}\in C$, then $x_{2}(e),x_{3}(e)$ exist and one of them blocks
$M^{\prime}$, contradiction. If $w,w^{\prime}\notin C$, then $u\in C$ (by our
assumption for any $e\in E_{c}$, at least one endpoint is critical) and
$x_{i}(e),x_{i}(f)$ do not exists for any $i$ and neither does
$y_{0}(e),y_{0}(f),y_{1}(e),y_{1}(f)$. Hence, $z_{s+5}(e)$ or $z_{s+6}(e)$
blocks $M^{\prime}$, contradiction.

The case $f\notin E_{c},g\in E_{c}$ is analogous.

$\blacksquare$

######  Claim.

For any c$\gamma$-min stable matching $N$ it holds that
$|N|\leq\frac{3}{2}|M|$.

Proof: Suppose for contradiction that there is a $c\gamma$-stable matching $N$
such that $|N|>\frac{3}{2}|M|$. Then, there must be a path component in $N\cup
M$ that is either a single $N$-edge, or consist of two $N$-edges and one
$M$-edge. The first case is clearly impossible, as $M$ is necessarily maximal.

Suppose the second case holds. Let $e=(u_{1},w_{2})$ be the edge of $M$ and
$f=(u_{1},w_{1})$, $g=(u_{2},w_{2})$ be the edges of $N$.

First observe that as $M$ and $N$ are critical, $e$ and $f\cup g$ cover the
same number of critical vertices with critical edges. Hence, if $e$
$\gamma$-blocks $N$, then it $c\gamma$-blocks $N$.

Suppose that $f,g\notin E_{c}$. Then, $e\notin E_{c}$ and only
$a,b_{0},b_{1},c$ copies exists of all three edges. As $a(f)$ does not block
$M^{\prime}$, $b_{0}(e),b_{1}(e)$ or $a(e)\in M^{\prime}$. As $c(g)$ does not
block $M^{\prime}$, $b_{0}(e),b_{1}(e)$ or $c(e)\in M^{\prime}.$ Hence,
$b_{0}(e)$ or $b_{1}(e)\in M^{\prime}$. Furthermore, if $b_{0}(e)\in
M^{\prime}$, then $p_{u_{1}}(e)\geq p_{u_{1}}(f)+\gamma_{e}^{u_{1}}$ and
$p_{w_{2}}(e)\geq p_{w_{2}}(g)+\delta_{e}^{w_{2}}$, so $e$ $c\gamma$-blocks
$N$ (combining with the fact that $e$ and $f\cup g$ cover the same number of
critical vertices), contradiction. The other case implies $p_{u_{1}}(e)\geq
p_{u_{1}}(f)+\delta_{e}^{u_{1}}$ and $p_{w_{2}}(e)\geq
p_{w_{2}}(g)+\gamma_{e}^{w_{2}}$, so $e$ $c\gamma$-blocks $N$, contradiction
again.

Next suppose that $f,g\in E_{c}$. Then, as $M$ is critical, $e\in E_{c}$,
$u_{1},w_{2}\in C$ and $u_{2},w_{1}\notin C$. Hence, $x_{i}(f),z_{j}(g)$ does
not exists for any $i,j$ but $y_{0}(e),y_{1}(e)$ exist and also
$z_{j}(f),x_{i}(g)$ exists for all $i,j$. As $z_{s+7}(f)$ does not block and
$x_{t+7}(g)$ does not block $M^{\prime}$ we get that $y_{0}(e)\in M^{\prime}$
or $y_{1}(e)\in M^{\prime}$ and in both cases, $e$ $c\gamma$-blocks $N$,
contradiction.

Suppose that $f\in E_{c},g\notin E_{c}$. Then, as $M,N$ are critical, $e\in
E_{c}$ and $w_{1}\in C$ if and only if $w_{2}\in C$. If $w_{1},w_{2}\in C$,
then $x_{1}(f)$ exists. As $x_{1}(f)$ does not block and $c(g)$ does not block
$M^{\prime}$, $x_{2}(e)\in M^{\prime}$ or $x_{3}(e)\in M^{\prime}$. In both
cases, $e$ $c\gamma$-blocks $N$, contradiction. If $w_{1},w_{2},\notin C$,
then $u_{1}\in C$ (each $e\in E_{c}$ has one critical endpoint by our
assumption) and $y_{0}(e),y_{1}(e),x_{i}(e)$ does not exists for
$i\in\\{1,\dots,t+7\\}$, but $z_{j}(e),z_{j}(f)$ does for
$j\in\\{1,\dots,s+7\\}$. As neither $z_{s+7}(f)$ nor $c(g)$ blocks
$M^{\prime}$, we get that $z_{s+6}(e)\in M^{\prime}$ or $z_{s+5}(e)\in
M^{\prime}$. In both cases, we get that $e$ $c\gamma$-blocks $N$,
contradiction.

The case $f\notin E_{c},g\in E_{c}$ is similar.

$\blacksquare$

The statement follows from these three claims. The running time of the
algorithm is linear in the edges of the extended instance, as the Gale-Shapley
algorithm is linear, so it has running time $\mathcal{O}((s+t)|E|)$. ∎

We state one remark about a straightforward extension of this algorithm.

######  Remark 1.

If we can have $k$
$(\gamma_{e}^{v})_{1}<(\gamma_{e}^{v})_{2}<\dots<(\gamma_{e}^{v})_{k}$ values
instead of the two $\gamma_{e}^{v},\delta_{e}^{v}$ values, and let $e=(u,w)$
block if $p_{u}(e)\geq p_{u}(M(u))+(\gamma_{e}^{u})_{i}$ and $p_{w}(e)\geq
p_{w}(M(w))+(\gamma_{e}^{w})_{k+1-i}$ for some $i\in\\{1,\dots,k\\}$, then
this framework can also incorporate a notion of $\gamma$-sum stability. In
$\gamma$-sum stability, we have one $\gamma_{e}$ value for each edge, and
$(u,w)$ $\gamma$-sum blocks, if it blocks and the sum of the two improvements
are at least $\gamma_{e}$. With $k=\mathcal{O}(|U\cup W|^{2})$ copies, we can
have $(\gamma_{e}^{v})_{1}<(\gamma_{e}^{v})_{2}<\dots<(\gamma_{e}^{v})_{k}$
values for each possible improvement $c$ and $\gamma_{e}-c$ such that
$(\gamma_{e}^{v})_{i}=\gamma_{e}-(\gamma_{e}^{v})_{k+1-i}$, so $\gamma$-sum
stability becomes a special case. Furthermore, the same algorithm
straightforwardly extends to this case, we only need to make $k$ copies
instead of $2$ for the needed cases and define the strict ranking in
$I^{\prime}$ according to the differences
$(\gamma_{e}^{v})_{i+1}-(\gamma_{e}^{v})_{i}$.

##  4 General Case with Matroid Constraints

Let us also extend the framework for two sided matroid constraints (which
generalizes capacities and laminar common quotas too). For this, we first
define matroids formally.

###  4.1 Matroids

A matroid is a pair $(E,\mathcal{I})$ of a finite ground set $E$ and a
nonempty family $\mathcal{I}\subseteq 2^{E}$ satisfying the following two
axioms: (i) $A\subseteq B\in\mathcal{I}$ implies $A\in\mathcal{I}$, and (ii)
for any $A,B\in\mathcal{I}$ with $|A|<|B|$, there is an element $x\in
B\setminus A$ with $A+x\in\mathcal{I}$. A set in $\mathcal{I}$ is called an
independent set, and an inclusion-wise maximal one is called a base. By axiom
(ii), all bases have the same size, which is called the rank of the matroid. A
circuit is an inclusion-wise minimal dependent set. The _fundamental circuit_
of an element $x\in S\setminus B$ for a base $B$, denoted by $C_{B}(x)$, is
the unique circuit in $B+x$. By a slight abuse of notation, we will also use
$C_{I}(x)$ for an independent set $I$ and an element $x\in E\setminus I$ to
denote the unique circuit in $I+x$ if it exists.

We define some simple operations of matroids that also produce matroids. Let
$\mathcal{M}_{1}=(E_{1},\mathcal{I}_{1}),\mathcal{M}_{2}=(E_{2},\mathcal{I}_{2})$
be two matroids. The direct sum $\mathcal{M}_{1}\oplus\mathcal{M}_{2}$ is the
matroid, where the ground set is $E_{1}\cup E_{2}$ and a set $I\subseteq
E_{1}\cup E_{2}$ is independent, if and only if $I\cap
E_{1}\in\mathcal{I}_{1}$ and $I\cap E_{2}\in\mathcal{I}_{2}$.

The truncation of a matroid $\mathcal{M}=(E,\mathcal{I})$ to size $k$ is the
matroid, where the ground set is $E$ and a set $I\subseteq E$ is independent
if and only if $I\in\mathcal{I}$ and $|I|\leq k$. For a subset $J\subseteq E$,
the deletion of $J$ defines the matroid $\mathcal{M}\setminus J$, whose ground
set is $E\setminus J$ and $I\subseteq E\setminus J$ is independent if and only
if it is independent is $\mathcal{M}$. Finally, the contraction of an
independent set $J$ defines a matroid $\mathcal{M}/J$, whose ground set is
similarly $E\setminus J$, and a set $I$ is independent, if and only if $I\cup
J\in\mathcal{I}$.

If we have a total order $\succ$ given on $E$, then the triple
$M=(E,\mathcal{I},\succ)$ is called a _(totally) ordered matroid_. A nice
property of totally ordered matroids is that for any weight vector
$w\in\mathbb{R}^{E}$ that satisfies $w_{x}>w_{y}\Leftrightarrow x\succ y$, the
unique maximum weight base is the same. We call this base $A$ the _optimal
base_ of $(E,\mathcal{I},\succ)$; it is characterized by the property that the
worst element of $C_{A}(x)$ is $x$ for any $x\in S\setminus A$. We need the
following theorem about ordered matroids from [4].

######  Theorem 4.1.

(Csáji, Király, Yokoi) Let $\mathcal{M}=(E,\mathcal{I},\succ)$ be an ordered
matroid of rank $r$. Let $A$ be the optimal base and $B$ be a base disjoint
from $A$. Then, there is a perfect matching $a_{i}b_{i}$ $(i\in[r])$ between
$A$ and $B$ such that $a_{i}\succ b_{i}$ and $B+a_{i}-b_{i}\in\mathcal{I}$ for
every $i\in[r]$.

We also need a well-known simple Lemma about matroids.

######  Lemma 1.

Let $I,J$ be two independent sets of a matroid $\mathcal{M}$ such that for
each $e\in I$, $J+e\notin\mathcal{M}$. Then, for each subset
$I^{\prime}\subseteq I$ it holds that the union of the fundamental cycles of
the elements in $I^{\prime}$ contains at least $|I^{\prime}|$ elements.

###### Proof.

If for a subset $I^{\prime}$, the union of the fundamental cycles of these
elements $C_{I^{\prime}}$ in $J$ would be smaller than $|I^{\prime}|$, then by
axiom (ii) of matroids, there would be an element $e\in I^{\prime}$ such that
$C_{I^{\prime}}+e\in\mathcal{I}$, which contradicts that the fundamental cycle
of $e$ is in $C_{I^{\prime}}$. ∎

An important class of matroids is laminar matroids. A matroid
$\mathcal{M}=(E,\mathcal{I})$ is a laminar matroid, if there is a laminar
family $\mathcal{S}$ of sets over $E$, together with integer numbers
$q_{S}\in\mathbb{N}$ for each $S\in\mathcal{S}$, such that a subset
$I\subseteq E$ is independent, if and only if $|I\cap S|\leq q_{S}$ for each
$S\in\mathcal{S}$. In particular, if a matroidal constraint comes from a
simple vertex capacity $q(v)$, then it defines a laminar matroid with
$\mathcal{S}=\\{E(v)\\}$ and $q_{S}=q(v)$.

###  4.2 Extending the model to matroid constraints

We continue by extending our model and stability notions for the case of
matroidal constraints. Here, for each agent $v\in U\cup W$, apart from the
preference valuation $p_{v}()$, there is also a matroid
$\mathcal{M}_{v}=(E_{v},\mathcal{I}_{v})$ over $E(v)$. For each $v\in U\cup
W$, let $r(v)$ be the rank of the matroid $\mathcal{M}_{v}$. By taking the
direct sums of the matroids on both sides, and appending the preference lists
of the vertices, we create two matroids $\mathcal{M}_{U}=(E,\mathcal{I}_{U})$
and $\mathcal{M}_{W}=(E,\mathcal{I}_{W})$. Here, $M\subseteq E$ is called a
common independent set, if $M\cap E(v)$ is independent in the matroid
$\mathcal{M}_{v}$ for each $v\in U\cup W$ or equivalently, $M$ is independent
in both $\mathcal{M}_{U}$ and $\mathcal{M}_{W}$.

Let $C\subseteq U\cup W$ denote the set of critical agents and $E_{c}\subseteq
E$ the set of critical edges and suppose we are given numbers
$0<\gamma_{e}^{v}<\delta_{e}^{v}$ for each edge $e$ and vertex $v\in e$ as
before. Without loss of generality, we suppose that for each critical edge
$e$, at least one of its endpoints is critical. Again, let $M_{c}=M\cap
E_{c}$. We say that a common independent set $M$ is critical, if $M_{c}$ fills
at least as many places of critical vertices as $N_{c}$ for any other common
independent set $N$. That is, $\sum_{v\in C}|M(v)\cap E_{c}|$ is maximum among
all common independent sets.

We say that an edge $e=(u,w)$ $c\gamma$-blocks a common independent set $M$,
if there are $f\in M(u)\cup\\{\emptyset\\},g\in M(w)\cup\\{\emptyset\\}$ such
that $M^{\prime}=M\setminus\\{f,g\\}\cup\\{e\\}$ is also critical,
$M-f+e\in\mathcal{I}_{U}$, $M-g+e\in\mathcal{I}_{w}$ and either
$p_{u}(e)-p_{u}(f)\geq\gamma_{e}^{u}$ and
$p_{w}(e)-p_{w}(g)\geq\delta_{e}^{w}$ or $p_{u}(e)-p_{u}(f)\geq\delta_{e}^{u}$
and $p_{w}(e)-p_{w}(g)\geq\gamma_{e}^{w}$ holds. $M$ is $c\gamma$-stable, if
no edge $c\gamma$-blocks $M$.

Hence, we obtain the following optimization problem:

max-$c\gamma$-kernel In: A bipartite graph $G=(U,W;E)$, $p_{v}()$ preference
valuations for each $v\in U\cup W$, a set $C\subseteq U\cup W$ of critical
vertices, a set $E_{c}\subseteq E$ of critical edges, matroids
$\mathcal{M}_{v}$ for each $v\in U\cup W$ and numbers
$0<\gamma_{e}^{v}<\delta_{e}^{v}$ for each pair $(e,v)\in E\times(U\cup W)$
such that $v\in e$. Out: A maximum size $c\gamma$-stable common independent
set $M$.

###  4.3 Extending the algorithm

Let $s=\sum_{u\in U\cap C}r(u)$ and $t=\sum_{w\in W\cap C}r(w)$ be the sum of
ranks of the matroids of the critical agents in $U$ and $W$ respectively. In
particular, $s,t$ are upper bounds on the number of places of critical
vertices that can be covered in $U$ and $W$ respectively.

The idea of the algorithm is the same again, but here, we use the fact that
the stable matching problem can be solved in quadratic with Fleiner’s
algorithm (linear time in case of laminar matroids), even if each vertex has
matroid constraints.

Hence, the steps are:

1\. Create an instance $I^{\prime}$ with $G^{\prime}=(U,W;E^{\prime})$ of
stable matching problem with matroid constraints and strict preferences by
making parallel copies of each edge and create strict preferences over the
created edges.

2\. Run Fleiner’s algorithm to obtain a stable common independent set
$M^{\prime}$ in the new instance $I^{\prime}$.

3\. Take the projection $M$ of $M^{\prime}$ to $I$ by taking an edge $e$
inside $M$, whenever one of the parallel copies of $e$ was inside
$M^{\prime}$.

Let us start by describing the extended instance $I^{\prime}$. For each edge
$e=(u,w)\in E$ we create parallel edges as follows:

  * –

We create copies $a(e)$, $b_{0}(e),b_{1}(e)$ and $c(e)$,

  * –

If $w\in C\cap W$ is critical and $e\in E_{c}$ is also critical, we create
copies $x_{1}(e),\dots,x_{t+7}(e)$

  * –

If $u\in C\cap U$ is critical and $e\in E_{c}$ is also critical, we create
copies $z_{1}(e),\dots,z_{s+7}(e)$

  * –

Finally, if $e\in E_{c}$ is critical and both $u,w\in C$ are critical, we
create a copies $y_{0}(e),y_{1}(e)$

Then, we create the strict preferences according to the same rule as in the
one-to-one matching case. The matroids $\mathcal{M}^{\prime}_{v}$ for the
agents in the extended instance are created such that $M^{\prime}\subset
E^{\prime}(v)$ is independent, if and only if it contains at most one parallel
copy of each edge and its projection $M\subset E(v)$ is independent in
$\mathcal{M}_{v}$. Therefore, $M^{\prime}\subseteq E^{\prime}$ is a common
independent set if and only if it contains at most one copy of each edge and
its projection $M\subseteq E$ is a common independent set.

We proceed by proving the algorithm is a $\frac{3}{2}$-approximation even in
this most general model.

######  Theorem 4.2.

max-$c\gamma$-kernel can be $\frac{3}{2}$-approximated in
$\mathcal{O}((s+t)^{2}|E|^{2})$ time even with arbitrary matroid constraints.
If the matroid contraints are given by laminar matroids, then the running time
is $\mathcal{O}((s+t)|E|)$.

###### Proof.

We prove the theorem in three claims again. Let $M$ denote the output of the
algorithm and $M^{\prime}$ be its preimage in the extended instance
$I^{\prime}$.

######  Claim.

$M$ is critical.

Proof: Suppose for contradiction that there is a common independent set $N$,
such that $\sum_{v\in C}|M_{c}(v)|<\sum_{v\in C}|N_{c}(v)|$. Then, it must
hold that either $N_{c}$ covers more places of critical vertices from $U$ or
more from $W$ than $M_{c}$. Suppose that the first case holds.

We create a graph $H=(U^{\prime},W^{\prime},E_{M_{c}\cup N_{c}})$ by making
$q(v)=|E(v)|$ copies $v^{1},\dots,v^{q(v)}$ of each vertex $v\in U\cup W$.
Then, for each edge $e=(u,w)\in M_{c}$ we add an edge
$e^{\prime}=(u^{i},w^{j})$ (for some copy $u^{i}$ of $u$ and $w^{j}$ of $w$)
to $E_{M_{c}\cup N_{c}}$ such that these edges form a matching $M_{c}^{H}$ in
$H$. As $|M\cap E(v)|\leq q(v)$ $\forall v\in U\cup W$, this is clearly
possible. Then, we add an edge $e^{\prime}=(u^{i},w^{j})$ for each $e=(u,w)\in
N_{c}$ such that

  1. 1.

These edges form a matching $N_{c}^{H}$ in $H$,

  2. 2.

If $M_{c}(u)+e\in\mathcal{I}_{u}$, then $u^{i}$ is not covered by $M_{c}^{H}$,

  3. 3.

If $M_{c}(w)+e\in\mathcal{I}_{w}$, then $w^{j}$ is not covered by $M_{c}^{H}$,

  4. 4.

If $M_{c}(u)+e\notin\mathcal{I}_{u}$, then $u^{i}$ is covered by a copy
$f^{\prime}\in M_{c}^{H}$ of an edge $f\in M_{c}$, such that
$M_{c}(u)-f+e\in\mathcal{I}_{u}$,

  5. 5.

If $M_{c}(w)+e\notin\mathcal{I}_{w}$, then $w^{j}$ is covered by a copy
$f^{\prime}\in M_{c}^{H}$ of an edge $f\in M_{c}$, such that
$M_{c}(w)-f+e\in\mathcal{I}_{w}$.

We can choose the endpoint in $U^{\prime}$ for each edge such that 2 and 3
hold, because we have $q(v)=|E(v)|$ many options which is always sufficient.
We can also choose the enpoint in $W^{\prime}$ such that 4 and 5 hold, because
if $M_{c}(w)+e\notin\mathcal{I}_{w}$ or $M_{c}(u)+e\notin\mathcal{I}_{u}$,
then the fundamental cycle of $e$ in $M$ is included in $M_{c}$ and by Lemma
1, the Hall-property is satisfied, so we can match the edges to the vertex
copies such that 4 and 5 will hold.

By our assumption, there must be a component $P$ in $N_{c}^{H}\cup M_{c}^{H}$
such that $N_{c}^{H}$ matches strictly more copies of critical vertices than
$M_{c}^{H}$ in $U^{\prime}$. We can conclude that there is a vertex
$u_{k_{1}}\in U\cap C$ such that a copy $u_{k_{1}}^{i_{1}}$ is covered by
$N_{c}^{H}$ with an edge $(u_{k_{1}}^{i_{1}},w_{l_{1}}^{j_{1}})$, but not by
$M_{c}^{H}$. Let $e_{1}=(u_{k_{1}},w_{l_{1}})$. Hence,
$M_{c}(u_{k_{1}})+e_{1}\in\mathcal{I}_{u_{k_{1}}}$.

As $u_{k_{1}}$ is critical, we know that the copies
$z_{1}(e_{1}),\dots,z_{s+7}(e_{1})$ exist. As
$M_{c}(u_{k_{1}})+e_{1}\in\mathcal{I}_{u_{k_{1}}}$, we know that either
$M(u_{k_{1}})+e\in\mathcal{M}_{u_{k_{1}}}$ or otherwise there is an edge
$f_{1}\in M\setminus M_{c}$ such that
$M(u_{k_{1}})-f_{1}+e_{1}\in\mathcal{I}_{u_{k_{1}}}$. In particular, we know
that if there is such an edge $f_{1}$, then only $a,b_{0},b_{1},c$ copies
exist of $f$. Hence, by the fact that $z_{4}(e_{1})$ does not block
$M^{\prime}$ we get that $M(w_{l_{1}})+e_{1}\notin\mathcal{I}_{w_{l_{1}}}$ and
that for each edge $f$ in the fundamental circuit of $e_{1}$ in
$\mathcal{M}_{w_{l_{1}}}$, $z_{j}(f)\in M^{\prime}$ with $j\leq 4$. This
implies that for each edge $f=(u,w_{l_{1}})\in M(w_{l_{1}})$ in the
fundamental cycle of $e_{1}$, $f\in E_{c}$ and $u\in C$. By property 5, in
$M_{c}^{H}$ $w_{l_{1}}^{j_{1}}$ is matched to some $u_{k_{2}}^{i_{2}}$
($k_{2}$ can be the same as $k_{1}$ but it is not important for the analysis)
with $u_{k_{2}}\in C$ and $f_{2}=(u_{k_{2}},w_{l_{1}})\in E_{c}$. By our
assumption on the component $P$ ($N_{c}^{H}$ matches more copies of critical
vertices), $u_{k_{2}}^{i_{2}}$ is matched in $N_{c}^{H}$ to a vertex
$w_{l_{2}}^{j_{2}}$. Let $e_{2}=(u_{k_{2}},w_{l_{2}})$.

By property 4, we know that
$M_{c}(u_{k_{2}})+e_{2}\notin\mathcal{I}_{u_{k_{2}}}$, so the fundamental
cycle of $e_{2}$ in $\mathcal{M}_{u_{k_{2}}}$ is included in
$M_{c}(u_{k_{2}})$ and
$M_{c}(u_{k_{2}})+e_{2}-f_{2}\in\mathcal{I}_{u_{k_{2}}}$. As any $z_{5}$ copy
is better for $u_{k_{2}}$ in $I^{\prime}$ than any $z_{j}$ copy with $j\leq
4$, but $z_{5}(e_{2})$ exists and does not block, we have
$M(w_{l_{2}})+e_{2}\notin\mathcal{I}_{w_{l_{2}}}$ and for each $f\in
M(w_{l_{2}})$ in the fundamental cycle of $e_{2}$ in
$\mathcal{M}_{w_{l_{2}}}$, $z_{j}(f)\in M^{\prime}$ with some $j\leq 5$.
Therefore, for each such edge $f=(u,w_{l_{2}})$, $f\in E_{c}$ and $u\in C$. By
propety 5, the copy of $w_{l_{2}}$ covered by the image of $e_{2}$ in
$N_{c}^{H}$ is also covered by a copy of one of these edges $f$, say
$f_{3}=(u_{k_{3}},w_{l_{2}})$. By our assumption on $P$, the copy of
$u_{k_{3}}$ matched by $f_{3}$ is also covered by $N_{c}^{H}$ with an edge
$(u_{k_{3}}^{i_{3}},w_{l_{3}}^{j_{3}})$. Let $e_{3}=(u_{k_{3}},w_{l_{3}})$.
Using property 4, we get that $f_{3}$ is in the fundamental cycle of $e_{3}$
in $M(u_{k_{3}})$.

By iterating this argument, we get that there must be more than $s$ vertices
of $U^{\prime}$ that are copies of critical vertices in $U$ and are covered by
$N_{c}^{H}$, which is a contradiction, as at most $s$ places of the critical
vertices in $U$ can be covered by a common independent set.

The second case is analogous.  $\blacksquare$

######  Claim.

The output common independent set $M$ by the algorithm is $c\gamma$-stable.

Proof: Suppose for contradiction that there is a $c\gamma$-blocking edge
$e=(u,w)$ to $M$ with $f\in M(u)\cup\\{\emptyset\\}$ and $g\in
M(w)\cup\\{\emptyset\\}$.

If $M(u)+e\in\mathcal{I}_{u}$, then $M(w)+e\notin\mathcal{I}_{w}$, so
$g=(u^{\prime},w)\in M(w)\cup\\{\emptyset\\}$ is not $\emptyset$. As $e$
$c\gamma$-blocks and $M$ is critical we get that $e\in E_{c}$ if and only if
$g\in E_{c}$ and if yes, then $u^{\prime}\in C$ if and only if $u\in C$. In
particular, we get that the best copy of $e$ and $g$ in $I^{\prime}$ for $w$
is the same. Also, this copy can be only $c,x_{t+7}$ or $z_{1}$ and all these
copies are ranked according to $p_{w}()$. Therefore, this copy of $e$ blocks
$M^{\prime}$, as $e$ $c\gamma$-blocks $M$, contradiction. The case when
$M(w)+e\in\mathcal{M}_{w}$ is similar.

Hence, $M(u)=f=(u,w^{\prime})$ and $M(w)=g=(u^{\prime},w)$ is not $\emptyset$.
Because $e$ $c\gamma$-blocks, $p_{u}(e)\geq p_{u}(f)+\gamma_{e}^{u}$ and
$p_{w}(e)\geq p_{w}(g)+\delta_{e}^{w}$ or $p_{u}(e)\geq
p_{u}(f)+\delta_{e}^{u}$ and $p_{w}(e)\geq p_{w}(g)+\gamma_{e}^{w}$.

If $f,g\notin E_{c}$, then $e\notin E_{c}$, as $M$ is critical. Hence, only
$a,b_{0},b_{1},c$ copies exists of $e,f,g$. As $e$ $c\gamma$-blocks $M$, we
get that $b_{0}(e)$ or $b_{1}(e)$ blocks $M^{\prime}$, contradiction.

Suppose that $f,g\in E_{c}$. Then, $e\in E_{c}$, $u,w\in C$ and
$u^{\prime},w^{\prime}\notin C$, because $e$ $c\gamma$-blocks. Hence,
$x_{i}(f),z_{j}(g)$ do not exists for any $i,j$, but $y_{0}(e),y_{1}(e)$
exists. As $e$ $c\gamma$-blocks one of $y_{0}(e),y_{1}(e)$ blocks
$M^{\prime}$, contradiction.

Suppose that $f\in E_{c},g\notin E_{c}$. In particular, only
$a(g),b_{0}(g),b_{1}(g),c(g)$ exists of $g$. Then, $e\in E_{c}$ as $e$
$c\gamma$-blocks and $w^{\prime}\in C$ if and only if $w\in C$. If
$w,w^{\prime}\in C$, then $x_{2}(e),x_{3}(e)$ exists and one of them blocks
$M^{\prime}$, contradiction. If $w,w^{\prime}\notin C$, then
$x_{i}(e),x_{i}(f)$ do not exists for any $i$ and neither does
$y_{0}(e),y_{0}(f),y_{1}(e),y_{1}(f)$. Hence, $z_{s+5}(e)$ or $z_{s+6}(e)$
blocks $M^{\prime}$, contradiction.

The case $f\notin E_{c},g\in E_{c}$ is analogous.  $\blacksquare$

######  Claim.

For any c$\gamma$-min stable common independent set $N$ it holds that
$|N|\leq\frac{3}{2}|M|$

Proof: Suppose for contradiction that there is a $c\gamma$-stable common
independent set $N$ such that $|N|>\frac{3}{2}|M|$.

Let $N_{i}$ be a subset of $N\setminus M$ such that $M\cup
N_{i}\in\mathcal{I}_{i}$ and $|M\cup N_{i}|=|N|$ for each $i\in\\{U,W\\}$. The
sets $N_{U}$ and $N_{W}$ are disjoint because $M^{\prime}$ is an inclusionwise
maximal common independent set in $I^{\prime}$.

Let $\mathcal{M}^{*}_{i}$ be the matroid obtained from $\mathcal{M}_{i}$ by
deleting $E\setminus(M\cup N)$, contracting $(M\cap N)\cup N_{i}$, and
truncating to the size of $M\setminus N$. That is, the ground set of
$\mathcal{M}_{i}^{*}$ is $E_{i}^{*}=(M\setminus N)\cup(N\setminus(M\cup
N_{i}))$ and $\mathcal{M}_{i}^{*}=\\{\,I\subseteq E^{*}_{i}:I\subseteq M\cup
N,~{}I\cup(M\cap N)\cup N_{i}\in\mathcal{M}_{i},~{}|I|\leq|M\setminus
N|\,\\}$. In $\mathcal{M}_{i}^{*}$, the sets $M_{i}^{*}\coloneqq M\setminus N$
and $N_{i}^{*}\coloneqq N\setminus(M\cup N_{i})$ are bases that are
complements of each other.

We define a strict preference order $\succ^{*}_{i}$ on $E_{i}^{*}$ in the
following way. The elements of $N\setminus(M\cup N_{U}\cup N_{W})$ are worst
(in arbitrary order). On the remaining elements, we define the preferences
based on the strict preferences created in $I^{\prime}$ over $E^{\prime}$. We
do this as follows. For an edge $e\in N_{U}\setminus M$, we take the best
existing copy for $\mathcal{M}_{W}$. For an edge $e\in N_{W}\setminus M$, we
take the best existing copy for $\mathcal{M}_{U}$. Finally, for $e\in
M\setminus N$, we take the copy included in $M^{\prime}$. Then, we order these
edges (first just within the sets $E(v)\cap(M\cup N_{U}\cup N_{W})$) according
to the preference orders induced on these copies in $I^{\prime}$ and then
extend this order by appending the constructed individual orders within the
sets $E(v)\cap(M\cup N_{U}\cup N_{W})$ after each other arbitrarily.

In the ordered matroid
$\mathcal{M}_{i}^{*}=(E^{*},\mathcal{I}^{*}_{i},\succ^{*}_{i}$), $M_{i}^{*}$
is an optimal base. Indeed, $e$ is the worst element in the fundamental cycle
of $e$ in $M_{i}^{*}$ for every $e\in N_{i}^{*}\cap(N_{U}\cup N_{W})$, as
otherwise a copy of $e$ would block $M^{\prime}$, contradiction. It is also
clear for the elements in $N_{i}^{*}\setminus(N_{U}\cup N_{W})$ by the
definition of $\succ^{*}_{i}$. By Theorem 4.1, there is a perfect matching
$P_{i}$ for $i=U,W$ between $M_{i}^{*}$ and $N_{i}^{*}$ such that
$e\succ_{i}^{*}f$ and $f$ is in the fundamental cycle of $e$ in $N_{i}^{*}$
for every $(e,f)\in P_{i}$, where $e\in M_{i}^{*}$ and $f\in N_{i}^{*}$.

Since $|N|>1.5|M|$ implies $|N_{U}^{*}|=|N_{W}^{*}|>|M\setminus N|/2$, there
is an element $e\in M\setminus N$ that is covered by both $P_{U}$ and $P_{W}$.
Let $(e,f)\in P_{U}$, $(e,g)\in P_{W}$ with
$f=(u_{1},w_{1}),e=(u_{1},w_{2}),g=(u_{2},w_{2})$.

Note that this means that if $e^{\prime}$ is the copy of $e$ in $M^{\prime}$,
then $e^{\prime}$ is better than the best existing copy of $f$ for $u_{1}$ and
$e^{\prime}$ is better than the best existing copy of $g$ for $w_{2}$. Also,
$N+e-f\in\mathcal{I}_{U}$ and $N+e-g\in\mathcal{I}_{W}$.

Suppose that $f,g\notin E_{c}$. Then, $e\notin E_{c}$ and only
$a,b_{0},b_{1},c$ copies exists of all three edges, because otherwise
$N+e-f-g$ is a common independent set covering more places of critical
vertices with critical edges, than $N$, contradicting that $N$ is critical. As
$a(f)$ is not better than $e^{\prime}$, $b_{0}(e),b_{1}(e)$ or $c(e)\in
M^{\prime}$. As $c(g)$ is not better than $e^{\prime}$, $b_{0}(e),b_{1}(e)$ or
$a(e)\in M^{\prime}.$ Hence, $b_{0}(e)$ or $b_{1}(e)\in M^{\prime}$. If
$b_{0}(e)\in M^{\prime}$, then $p_{u}(e)\geq p_{u}(f)+\gamma_{e}^{u}$ and
$p_{w}(e)\geq p_{w}(g)+\delta_{e}^{w}$, so $e$ $c\gamma$-blocks $N$ (combining
with the fact that $e$ and $f\cup g$ both match 0 critical nodes),
contradiction. The other case implies $p_{u}(e)\geq p_{u}(f)+\delta_{e}^{u}$
and $p_{w}(e)\geq p_{w}(g)+\gamma_{e}^{w}$, so $e$ $c\gamma$-blocks $N$,
contradiction again.

Next suppose that $f,g\in E_{c}$. If $x_{1}(f)$ exists, then as $e^{\prime}$
is better than $x_{1}(f)$ for $u_{1}$, we get that
$e^{\prime}\in\\{x_{1}(e),x_{2}(e),x_{3}(e)\\}$. Hence, as either $x_{t+7}(g)$
or $z_{1}(g)$ exists by $g\in E_{c}$, it cannot hold that $e^{\prime}$ is
better than the best existing copy of $g$, contradiction. Similarly we get
that $z_{1}(g)$ does not exist, so $u_{1},w_{2}\in C$, $u_{2},w_{1}\notin C$.
As $e^{\prime}$ is better than $z_{s+7}(f)$ for $u_{1}$ and better than
$x_{t+7}(g)$ for $w_{2}$ we get that $e^{\prime}\in\\{y_{0}(e),y_{1}(e)\\}$.
In particular, $e\in E_{c}$ and $p_{u}(e)\geq
p_{u}(f)+\gamma_{e}^{u}$,$p_{w}(e)\geq p_{w}(g)+\delta_{e}^{w}$ or
$p_{u}(e)\geq p_{u}(f)+\delta_{e}^{u}$, $p_{w}(e)\geq
p_{w}(g)+\gamma_{e}^{w}$. Hence, $e$ is $c\gamma$-blocking $N$, contradiction.

Suppose that $f\in E_{c},g\notin E_{c}$. If $w_{1}\in C$, then as $e^{\prime}$
is better for $u_{1}$ than $x_{1}(f)$,
$e^{\prime}\in\\{x_{1}(e),x_{2}(e),x_{3}(e)\\}$. It is also better than $c(g)$
for $w_{2}$, so $e^{\prime}$ is either $x_{2}(e)$ or $x_{3}(e)$. In
particular, $e\in E_{c}$ and $w_{2}\in C$, which means that $e$
$c\gamma$-blocks $N$, contradiction. If $w_{1}\notin C$, then by the facts
that $e^{\prime}$ is better than $z_{s+7}(f)$ for $u_{1}$ and better than
$c(g)$ for $w_{2}$, we get that $e^{\prime}$ cannot be an $a,b_{0},b_{1}$ or
$c$ type copy. Hence, $e\in E_{c}$. This implies that $w_{2}\notin C$, as
otherwise $N+e-f-g$ matches more places of critical vertices with critical
edges, than $N$, contradiction. So there is no $y_{0}(e),y_{1}(e)$ copy.
Combining this, we obtain that either $z_{s+5}(e)\in M^{\prime}$ or
$z_{s+6}(e)\in M^{\prime}$. In both cases, it follows that $e$
$c\gamma$-blocks $N$, contradiction.

The case $f\notin E_{c},g\in E_{c}$ is similar.  $\blacksquare$

The running time follows from the fact that Fleiner’s algorithm runs in time
$\mathcal{O}(|E^{\prime}|^{2})=\mathcal{O}((s+t)^{2}|E|^{2})$-time. In the
case, when the matroids $\mathcal{M}_{v}$ are simple laminar matroids, coming
from for example vertex capacities $q(v)$, the matroids in $I^{\prime}$ are
laminar, hence the running time of Fleiner’s algorithm can be reduced to
$\mathcal{O}((s+t)|E|)$ and so is our algorithm’s. The theorem now follows. ∎

######  Remark 2.

Even this algorithm is straghtforward to extend to work for the case when $k$
$(\gamma_{e}^{v})_{i}$ numbers are given, but the number of required copies
make the analysis more technical and tedious.

##  5 Conclusion and Future Work

In this paper we demonstrated the robust usefulness and generality of the edge
duplicating technique and provided simple algorithms for many Max-SMTI
generalizations at the same time. As there are probably even more cases, where
this technique could provide a nice solution, there is a huge potential of
applying it to other lesser known or yet to be introduced models.

##  6 Acknowledgements

The author was supported by the Hungarian Scientific Research Fund, OTKA,
Grant No. K143858, by the Momentum Grant of the Hungarian Academy of Sciences,
grant number 2021-1/2021 and by the Ministry of Culture and Innovation of
Hungary from the National Research, Development and Innovation fund, financed
under the KDP-2023 funding scheme (grant number C2258525).

## References

  * [1] Georgios Askalidis et al.  “Socially stable matchings in the hospitals/residents problem”  In _Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings 13_ , 2013, pp. 85–96  Springer
  * [2] Katarına Cechlárová and Tamás Fleiner  “Stable roommates with free edges”, 2009
  * [3] Jiehua Chen, Piotr Skowron and Manuel Sorge  “Matchings under preferences: Strength of stability and tradeoffs”  In _ACM Transactions on Economics and Computation_ 9.4 ACM New York, NY, 2021, pp. 1–55
  * [4] Gergely Csáji, Tamás Király and Yu Yokoi  “Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching”  In _Symposium on Simplicity in Algorithms (SOSA)_ , 2023, pp. 103–113  SIAM
  * [5] Szymon Dudycz, Pasin Manurangsi and Jan Marcinkowski  “Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems”  In _Approximation and Online Algorithms: 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6–10, 2021, Revised Selected Papers_ , 2022, pp. 48–64  Springer
  * [6] Tamás Fleiner  “A matroid generalization of the stable matching polytope”  In _Proc. 8th International Conference on Integer Programming and Combinatorial Optimization_ , 2001, pp. 105–114  Springer
  * [7] David Gale and Lloyd S Shapley  “College admissions and the stability of marriage”  In _The American Mathematical Monthly_ 69.1 Taylor & Francis, 1962, pp. 9–15
  * [8] Magnús Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita  “Inapproximability results on stable marriage problems”  In _LATIN 2002: Theoretical Informatics: 5th Latin American Symposium Cancun, Mexico, April 3–6, 2002 Proceedings 5_ , 2002, pp. 554–568  Springer
  * [9] Magnús M Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa  “Improved approximation of the stable marriage problem”  In _Algorithms-ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings 11_ , 2003, pp. 266–277  Springer
  * [10] Kazuo Iwama, Shuichi Miyazaki and Naoya Yamauchi  “A ($2-c\frac{1}{\sqrt{n}}$)-Approximation Algorithm for the Stable Marriage Problem”  In _Algorithmica_ 51.3 Springer, 2008, pp. 342–356
  * [11] Kazuo Iwama, Shuichi Miyazaki and Naoya Yamauchi  “A 1.875-approximation algorithm for the stable marriage problem”  In _Proc. Eighteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2007)_ , 2007, pp. 288–297  SIAM, Philadelphia
  * [12] Kazuo Iwama, David Manlove, Shuichi Miyazaki and Yasufumi Morita  “Stable marriage with incomplete lists and ties”  In _Proc. 26th International Colloquium on Automata, Languages, and Programming (ICALP 1999)_ , 1999, pp. 443–452  Springer
  * [13] Zoltán Király  “Better and simpler approximation algorithms for the stable marriage problem”  In _Algorithmica_ 60.1 Springer, 2011, pp. 3–20
  * [14] Zoltán Király  “Linear time local approximation algorithm for maximum stable marriage”  In _Proc. Second International Workshop on Matching Under Preferences (MATCH-UP 2012)_ , 2012, pp. 99
  * [15] Zoltán Király  “Linear time local approximation algorithm for maximum stable marriage”  In _Algorithms_ 6.3 Multidisciplinary Digital Publishing Institute, 2013, pp. 471–484
  * [16] Prem Krishnaa, Girija Limaye, Meghana Nasre and Prajakta Nimbhorkar  “Envy-freeness and relaxed stability: Hardness and approximation algorithms”  In _Journal of Combinatorial Optimization_ 45.1 Springer, 2023, pp. 41
  * [17] David Manlove  “Algorithmics of matching under preferences”  World Scientific, 2013
  * [18] Eric McDermid  “A 3/2-approximation algorithm for general stable marriage”  In _Proc. 36th International Colloquium on Automata, Languages, and Programming (ICALP 2009)_ , 2009, pp. 689–700  Springer
  * [19] Meghana Nasre, Prajakta Nimbhorkar and Keshav Ranjan  “Critical Relaxed Stable Matchings with Two-Sided Ties”  In _arXiv preprint arXiv:2303.12325_ , 2023
  * [20] Katarzyna Paluch  “Faster and simpler approximation of stable matchings”  In _Proc. 9th International Workshop on Approximation and Online Algorithms (WAOA 2011)_ , 2011, pp. 176–187
  * [21] Katarzyna Paluch  “Faster and simpler approximation of stable matchings”  In _Algorithms_ 7.2 Multidisciplinary Digital Publishing Institute, 2014, pp. 189–202
  * [22] Hiroki Yanagisawa  “Approximation algorithms for stable marriage problems”  In _PhD thesis, Kyoto University, Graduate School of Informatics_ , 2007
  * [23] Yu Yokoi  “An approximation algorithm for maximum stable matching with ties and constraints”  In _arXiv preprint arXiv:2107.03076_ , 2021