Critical Relaxed Stable Matchings with Two-Sided Ties

Abstract

We consider the stable marriage problem in the presence of ties in preferences and critical vertices. The input to our problem is a bipartite graph $G = (\mathcal {A}\cup \mathcal {B}, E)$ where $\mathcal {A}$ and $\mathcal {B}$ denote sets of vertices which need to be matched. Each vertex has a preference ordering over its neighbours possibly containing ties. In addition, a subset of vertices in $\mathcal {A}\cup \mathcal {B}$ are marked as critical and the goal is to output a matching that matches as many critical vertices as possible. Such matchings are called critical matchings in the literature and in our setting, we seek to compute a matching that is critical as well as optimal with respect to the preferences of the vertices.

Stability, which is a well-accepted notion of optimality in the presence of two-sided preferences, is generalized to weak-stability in the presence of ties. It is well known that in the presence of critical vertices, a matching that is critical as well as weakly stable may not exist. Popularity is another well-investigated notion of optimality for the two-sided preference list setting, however, in the presence of ties (even with no critical vertices), a popular matching need not exist. We, therefore, consider the notion of relaxed stability which was introduced and studied by Krishnaa et. al. (SAGT 2020). We show that in our setting a critical matching which is relaxed stable always exists although computing a maximum-sized relaxed stable matching turns out to be NP-hard. Our main contribution is a $\frac{3}{2}$-approximation to the maximum-sized critical relaxed stable matching for the stable marriage problem where ties as well as critical vertices are present on both the sides of the bipartition.

1 Introduction

We study the stable marriage problem in the presence of ties in preferences and critical vertices. Formally, the input to our problem is a bipartite graph $G=(\mathcal {A}\cup \mathcal {B},E)$, where $\mathcal {A}$ and $\mathcal {B}$ are two sets of vertices and E denotes the set of all the acceptable vertex-pairs. Each vertex $u \in \mathcal {A}\cup \mathcal {B}$ ranks a subset of vertices in the other partition (its neighbours in G) in the order of its preference possibly involving ties – this ordering is denoted as ${\textsf{Pref}(u)}$. For a vertex u let $v_1$ and $v_2$ be two of its neighbours in G. The vertex u strictly prefers $v_1$ over $v_2$ (denoted as $v_1 \succ _u v_2$) if the rank of the edge $(u, v_1)$ is smaller than the rank of the edge $(u, v_2)$. The vertex u is tied between $v_1$ and $v_2$ (denoted as $v_1 =_u v_2$) if the ranks on the edges $(u, v_1)$ and $(u, v_2)$ are the same. We use $v_1\succeq _u v_2$ to denote that the rank of $v_1$ is at least as good as the rank of $v_2$ in ${\textsf{Pref}(u)}$. In addition, the input consists of a set $\mathcal {C}\subseteq (\mathcal {A}\cup \mathcal {B})$ of critical vertices. Our goal is to compute an assignment which minimizes the number of unassigned critical vertices.

Formally, an assignment or a matching $M\subseteq E$ in G is a set of edges that do not share an end-point. For each vertex $u\in \mathcal {A}\cup \mathcal {B}$, we denote by M(u), the neighbour of u that is assigned to u in M. In the presence of critical vertices, we consider that the most important attribute of a matching is to match as many critical vertices as possible. A matching M is critical [11] if there is no matching that matches more critical vertices than M. In this work, we are interested in computing a critical matching that is optimal with respect to the preferences of the vertices in an instance of our setting.

Critical vertices or lower-quota positions naturally arise in applications like the Hospitals/Residents problem [7], where rural hospitals must be prioritized to ensure sufficient staffing. Another example is the problem of assigning sailors to billets [28] in the US Navy, where some critical billets cannot be left vacant [25, 29]. Ties in preferences is yet another important practical consideration in matching problems and has been extensively investigated in the literature [2, 8, 9, 13, 18, 19, 24]. However, there is a limited investigation (see for example [5]) of matching problems with ties as well critical vertices and ours is the first work that allows ties as well as critical vertices on both sides of the bipartition.

Stability, which is the de-facto notion of optimality for two-sided preferences, is defined by the absence of a blocking pair. Informally, an assignment is stable if no unassigned pair wishes to deviate from it.

Definition 1

(Stable Matchings). Given a matching M, a pair $(a,b)\in E\setminus M$ is called a blocking pair w.r.t. M if (i) either a is unmatched or $b \succ _a M(a)$ and (ii) either b is unmatched or $a\succ _b M(b)$. A matching M is stable if there is no blocking pair w.r.t. M.

When all preferences are strict, that is, there are no ties, every instance of the stable marriage problem admits a stable matching, and it can be computed using the well-known Gale and Shapley algorithm [3]. In addition, it is also known [26, 27] that all stable matchings have the same size.

Stable Matchings in the Presence of Ties: When preferences are allowed to have ties, the notion of stability defined above is called as weak stability (referred to as stability in the rest of the paper). We remark that, for a pair (a, b) to block a matching M, both a and b prefer each other strictly over their current partners in M. Every instance of the stable marriage problem with ties admits a stable matching, and it can be efficiently computed. However, unlike in the case of strict lists, all the stable matchings need not have the same size, and the problem of computing a maximum or minimum size stable matching is NP-hard [18] under severe restrictions – e.g. when ties occur at the end of preference lists and only on one side of the bipartition, there is at most one tie per list, and each tie is of length two.

Stable/Popular Matching in the Presence of Critical Vertices: When we have critical vertices as a part of the input, a stable matching which is also critical, may not exist – for example, consider an instance of the stable matching problem with strict lists obtained by arbitrarily breaking ties in the preference lists of all agents in the example shown in Fig. 1. Any critical matching in the instance must match $b_2$ with $a_1$, resulting in the blocking edge $(a_1,b_1)$. Since stability and criticality are not simultaneously guaranteed, an alternate notion of optimality, namely popularity [4], is extensively investigated in the literature [11, 20, 22] for the case of strict lists. The goal is to compute a matching which is popular amongst the set of critical matchings. Informally, a matching M is popular in a set of matchings if no majority of vertices wish to deviate from M to any other matching in that set. It is known [11, 22] that an instance with strict preference lists always admits a matching which is popular amongst critical matchings, and such a matching can be computed efficiently. Hence, it is natural to consider popularity in the presence of critical vertices and ties.

However, popular matchings are not guaranteed to exist even when ties are present in the preferences only on one side of the bipartition, without any critical vertices. Moreover, in the presence of ties, deciding whether a popular matching exists is NP-hard [1]. In light of this, we explore the notion of relaxed stability.

Relaxed Stability in the Presence of Ties and Critical Vertices: The notion of relaxed stability was introduced and studied by Krishnaa et al. [14] for the Hospitals/Residents problem with lower quotas (HRLQ). In their setting, preferences are assumed to be strict. The HRLQ setting is a many-to-one matching problem where a hospital h can accept at most $q^+(h)$ many residents and has $q^-(h) \le q^+(h)$ many critical positions. To satisfy the critical positions at a hospital, certain residents may be forced to be matched to the hospital. The notion of relaxed stability allows only such residents to participate in blocking pairs. In addition, if a resident matched to h participates in a blocking pair then the hospital h should not be surplus, that is $|M(h)| \le q^-(h)$.

In the HRLQ setting, preferences are strict, hospitals have capacities, and critical positions are allowed only for hospitals. In contrast, we allow ties in preferences as well as critical vertices to appear on both sides of the bipartition. However, our setting is one-to-one.

We now define the notion of relaxed stability (RSM) for our setting. Intuitively, a matching M is an RSM if every blocking pair (a, b) w.r.t. M is justified by either a or b or both. A vertex a justifies the blocking pair if M(a) is a critical vertex. That is, M(a) forces a to be matched to a lower-preferred vertex than b. Similarly, the vertex b can justify the blocking pair (a, b).

Definition 2

(Relaxed stability in our setting). A matching M is RSM if for every blocking pair (a, b) w.r.t. M at least one of the following holds:

• 1. a is matched and $b'= M(a)$ is critical, or

• 2. b is matched and $a'= M(b)$ is critical.

Fig. 1.

Red vertices are critical, black vertices are non-critical. The numbers on the edges denote the ranks of the respective end-points. The instance does not admit any critical stable matching because $b_2$ remains unmatched in every stable matching. $M_1=\{(a_1,b_2),(a_2,b_1),(a_3,b_3)\}$ is critical but not RSM because the blocking edge $(a_2,b_4)$ is not justified. $M_2=\{(a_1,b_2),(a_2,b_4),(a_3,b_3)\}$ is CRITICAL-RSM because the only blocking edge $(a_1,b_1)$ is justified. (Color figure online)

A matching M is called a critical relaxed stable matching (CRITICAL-RSM) if it is critical as well as relaxed stable. In the instance shown in Fig. 1, the matching $M_1$ is critical but not RSM whereas $M_2$ is CRITICAL-RSM.

Our first contribution is to show that a CRITICAL-RSM always exists in our setting. We remark that when $\mathcal {C}=\emptyset$, an instance of our setting is the same as the stable marriage setting with ties but without critical vertices, and hence the set of CRITICAL-RSM is the same as the set of stable matchings. This immediately implies that computing a maximum size critical RSM is NP-hard [18] and hard to approximate within any factor smaller than $\frac{21}{19}$ [6]. For the problem of computing a maximum-sized stable matching when ties appear on both sides of the bipartition, the current best approximation factor [13, 19, 24] is $\frac{3}{2}$. The main result (Theorem 1) provides the same approximation size guarantee for a maximum sized CRITICAL-RSM in our setting.

Theorem 1

Let $G=(\mathcal {A}\cup \mathcal {B},E)$ be an instance of the stable marriage problem where ties and critical vertices can appear in both the bipartitions of G. Then G always admits a CRITICAL-RSM M such that $|M|\ge \frac{2}{3}|M'|$, where $M'$ is a maximum size CRITICAL-RSM in G. Moreover, M can be computed in polynomial-time.

Related Work: As mentioned earlier, the generalizations of the stable marriage problem to allow either ties in preferences or critical vertices/lower-quota positions has been extensively investigated. Very recently, Goko et al. [5] and Makino et al. [17] have considered the instances with both ties and critical vertices. They study the Hospitals/Residents problem with lower-quotas where ties appear on both sides. In their setting, only one side of the bipartition can have critical vertices. They define a matching with maximum satisfaction ratio, which for our one-to-one setting, coincides with critical matchings. However, their goal is to compute a matching that matches the maximum possible critical vertices amongst all stable matchings.

For strict preferences and lower-quotas/critical vertices, various notions like envyfreeness [15, 30], popularity [11, 20, 22, 23], and relaxed stability [14, 15] have been studied. Relaxed stability and popularity do not define the same set of matchings even in the one-to-one strict-list setting and critical vertices restricted to one side only (see full version [21]) for the details. Hamada et al. [7] consider the problem of computing a matching with minimum number of blocking pairs or blocking residents, and give approximation algorithms for the same.

For the stable marriage problem with ties (without critical vertices) there is a long line of investigation [2, 9, 10, 12, 13, 19, 24] in order to improve the approximation ratio of the maximum size stable matching under various restricted settings. The best-known approximation algorithm for the case when ties are allowed only in one bipartition of the graph is by Lam and Plaxton [16] whereas the best-known for the case where ties are allowed on both sides is by [13, 19, 24]. We use Király’s algorithm [13] in our work.

2 Preliminaries

Our algorithm described in the next section combines the ideas in (i) Király’s algorithm [13] for computing a stable matching in instances where ties appear on both sides and (ii) Multi-level algorithm for computing popular critical matching [23] for strict preferences. We give an overview of the algorithms and also define terminology useful for our algorithm.

Overview of Király’s Algorithm [13]. Király’s algorithm [13] is a proposal-based algorithm where vertices in $\mathcal {A}$ propose and vertices in $\mathcal {B}$ accept or reject. We need the term uncertain proposal from [13] which is defined below.

Definition 3

(Uncertain Proposal). Let b be some $k^{th}$ rank neighbour of a in ${\textsf{Pref}(a)}$. During the course of the algorithm, the proposal from a to b is uncertain if there exists another $k^{th}$ rank neighbour $b'$ of a which is unproposed by a and unmatched in the matching. Once a proposal (a, b) is uncertain, it remains uncertain until b rejects a.

Each time an $a\in \mathcal {A}$ proposes to its favourite neighbour b (we define favourite neighbour formally in Definition 4), the vertex b accepts/rejects as follows:

• 1. If b is unmatched then b immediately accepts the proposal.

• 2. If b is matched, say to $a'$, and $(a',b)$ is an uncertain proposal, then b rejects $a'$ and accepts the proposal from a, irrespective of the ranks of a and $a'$ in ${\textsf{Pref}(b)}$. In this case, b is marked by $a'$.

• 3. If b is matched, say to $a'$, and $(a',b)$ is not an uncertain proposal, then

  (i) if $a \succ _b a'$ then b rejects $a'$ and accepts the proposal from a, or

  (ii) if $a' \succeq _b a$ then b rejects a.

The reason for $a'$ marking the vertex b in (2) is as follows: In this case, b rejects the uncertain proposal from $a'$ and accepts a irrespective of b’s preference between a and $a'$. Later, when $a'$ gets its chance to propose, and if none of the neighbours of $a'$ at the rank of b accept the proposal from $a'$, then $a'$ will propose to the marked vertex b before proposing to the next lower-ranked neighbours. In contrast in (3)(i) above, when the proposal $(a', b)$ is not uncertain and $a \succ _b a'$ then $a'$ does not mark b. Note that a vertex $b\in \mathcal {B}$ can be part of an uncertain proposal at most once. Once a vertex receives its first proposal, it will remain matched and thereafter cannot be part of any uncertain proposal. Thus, any $b\in \mathcal {B}$ can be marked at most once during the course of the algorithm.

Now, we define the favourite neighbour of a vertex a, which is an adaptation of the definition in [13].

Definition 4

(Favourite neighbour of a). Assume that k is the best rank at which some unproposed or marked neighbours of a exist in ${\textsf{Pref}(a)}$. Then b is the favourite neighbour of a if one of the following conditions holds:

• (i) there exists at least one unmatched neighbour of a at the $k^{th}$ rank and b has the lowest index among all such unmatched neighbours, or

• (ii) all the $k^{th}$ ranked neighbours of a are matched and b is the lowest index among all such neighbours which are unproposed by a, or

• (iii) all the $k^{th}$ ranked neighbours are already proposed by a and b has the lowest index among all the vertices which are marked by a.

Király’s algorithm begins with every vertex $a \in \mathcal {A}$ being active. As long as there exists an active vertex which is unmatched and has not exhausted its preference list, the vertex proposes to its favourite neighbour. If $a\in \mathcal {A}$ remains unmatched after exhausting its preference list, it achieves a ‘$*$’ status and starts proposing to vertices in ${\textsf{Pref}(a)}$ with $*$ status. The $*$ status of a vertex a can be interpreted as improving the rank of a in ${\textsf{Pref}(b)}$ by 0.5 for any neighbour b of a. Thus, the $*$ status vertex is used to decide between vertices in a tie, but does not affect strict preferences. It is shown in [13] that the resulting matching is a $\frac{3}{2}$-approximation of a maximum size stable matching.

Overview of the Popular Critical Matching Algorithm [23]. Now, we briefly describe the algorithm in [23] for computing the maximum size popular critical matching in the one-to-one strict list setting. Let ${s}$ and ${t}$ denote the number of critical vertices in $\mathcal {A}$ and $\mathcal {B}$, respectively. The algorithm in [23] is a multi-level algorithm which first matches as many critical vertices from $\mathcal {B}$ as possible. This is achieved by restricting unmatched vertices in $\mathcal {A}$ at levels $0,\ldots ,{t}-1$ to propose only to critical vertices on the $\mathcal {B}$-side. At the level ${t}$, each vertex $a\in \mathcal {A}$ is allowed to propose all its neighbours. If a vertex $a\in \mathcal {A}$ remains unmatched even after exhausting its preference list at level ${t}$, a raises its level to ${t}+1$ and proposes to its neighbours until it is matched or it exhausts its preference list at the level ${t}+1$. If a critical vertex a remains unmatched then a raises its level above ${t}+1$ and continues proposing to all its neighbours until it is matched, or it exhausts its preference list at the highest level ${s}+{t}+1$. A vertex b which receives the proposal always prefers a higher level vertex a over any lower level vertex $a'$ irrespective of the ranks of a and $a'$ in ${\textsf{Pref}(b)}$. It is shown in [23] that the resulting matching is a maximum size popular matching among all the critical matchings.

3 Algorithm for Computing CRITICAL-RSM

Our algorithm (see Algorithm 1) is a combination of Király’s algorithm and the popular critical matching algorithm discussed in the previous section. In each level, vertices in $\mathcal {A}$ propose and vertices in $\mathcal {B}$ accept or reject. The set of vertices from $\mathcal {B}$ that $a\in \mathcal {A}$ proposes to depends on the level of a. Furthermore, depending on the level of a, the preference list at that level may be strict or may contain ties. Throughout Algorithm 1, b uses its original preference list ${\textsf{Pref}(b)}$ which possibly contains ties. For a vertex $a \in \mathcal {A}$, let ${\textsf{PrefS}(a)}$ denote a strict preference list obtained by breaking ties in ${\textsf{Pref}(a)}$ in such a way that the vertices in ties are ordered by increasing order of their indices. Furthermore, let ${\textsf{PrefSC}(a)}$ be the strict list obtained from ${\textsf{PrefS}(a)}$ by omitting all the non-critical vertices from ${\textsf{PrefS}(a)}$. For example, assume ${\textsf{Pref}(a)}= (b_2, b_1), b_5, (b_3, b_4)$ where $b_4$ and $b_5$ are critical vertices. Here, a ranks $b_1$ and $b_2$ as rank-1, $b_5$ as rank-2 and $b_3$ and $b_4$ as rank-3. We have ${\textsf{PrefS}(a)}= b_1, b_2, b_5, b_3, b_4$ and ${\textsf{PrefSC}(a)}= b_5, b_4$ where comma separated vertices denote a strict ordering.

Initially, all the vertices in $\mathcal {A}$ have their levels set to 0. A vertex a at level $\ell$ is denoted as $a^\ell$. At a level less than ${t}$, each $a\in \mathcal {A}$ proposes to vertices in ${\textsf{PrefSC}(a)}$ (see Lines 4–8 of Algorithm 1). Each time it remains unmatched, it proposes to its most preferred neighbour b. The most preferred neighbour in ${\textsf{PrefSC}(a)}$ or ${\textsf{PrefS}(a)}$ is the best-ranked neighbour b to whom a has not yet proposed at the current level. If a remains unmatched after proposing to all its neighbours in ${\textsf{PrefSC}(a)}$ at a level $\ell <{t}- 1$, then a raises its level to $\ell +1$ and again proposes to vertices in ${\textsf{PrefSC}(a)}$. In this part of the algorithm, we invoke CriticalPropose() which encodes the level-based accept/reject by b. A vertex $b\in \mathcal {B}$ prefers $a_i^\ell$ over $a_j^{\ell '}$ if :

• (i) either $\ell > \ell '$ (ranks of $a_i$ and $a_j$ in ${\textsf{Pref}(b)}$ do not matter) or

• (ii) $\ell = \ell '$ and $a_i\succ _b a_j$.

If vertex a remains unmatched after exhausting ${\textsf{PrefSC}(a)}$ at level ${t}-1$, a attains level ${t}$ where it uses its original preference list ${\textsf{Pref}(a)}$ which may contain ties. At level ${t}$ our algorithm executes Király’s algorithm [13]. This corresponds to Lines 10–13 of Algorithm 1. Király’s algorithm is encoded in the procedure TiesPropose(). Since we have ties on both sides of the graph, at this level, we need the notion of a favourite neighbour and uncertain proposal defined in Sect. 2. If the vertex a remains unmatched after exhausting ${\textsf{Pref}(a)}$ at level ${t}$, it attains the $*$ status, and for this, we have the sub-level ${t}^*$. The interpretation of the $*$ status is the same as discussed in Sect. 2.

If a critical vertex a remains unmatched after exhausting its preference list ${\textsf{Pref}(a)}$ at level ${t}^*$, a raises its level to ${t}+1$, and starts proposing to vertices in ${\textsf{PrefS}(a)}$ (see Lines 16–20 of Algorithm 1). It continues to do so until either it is matched or it has exhausted ${\textsf{PrefS}(a)}$ at level ${s}+{t}$. In contrast, if a non-critical vertex a remains unmatched after exhausting its preference list ${\textsf{Pref}(a)}$ at level ${t}^*$, a does not propose any further. Recall that ${\textsf{PrefS}(a)}$ is a strict preference list containing all the neighbours (not restricted to critical vertices). Here, Algorithm 1, again invokes CriticalPropose() for the level-based accept/reject by b. The algorithm terminates when either (i) all the vertices in $\mathcal {A}$ are matched or (ii) all unmatched critical $a\in \mathcal {A}$ have exhausted ${\textsf{PrefS}(a)}$ at level ${s}+{t}$ and all unmatched non-critical $a\in \mathcal {A}$ have exhausted ${\textsf{Pref}(a)}$ at level ${t}^*$. We note that ${s}+{t}=|\mathcal {C}|=O(n)$, where $n=|\mathcal {A}\cup \mathcal {B}|$ and each edge of G is explored at most ${s}+{t}+3$ times (at most three times at level ${t}$, the Király’s step, and at most once at every other level). Thus, the running time of our algorithm is $O(n\cdot |E|)$.

It is worth noting that in our algorithm, not all vertices in $\mathcal {A}$ propose at all levels. Similarly, not all vertices in $\mathcal {B}$ receive proposals from vertices at all levels. In other words, only critical vertices in $\mathcal {B}$ are allowed to receive proposals from vertices in $\mathcal {A}$ at levels at most ${t}-1$, and only critical vertices in $\mathcal {A}$ are allowed to propose at levels above ${t}$. Also, note that when a vertex in $\mathcal {A}$ transitions to a higher level, it proposes to possibly a superset of vertices that it proposes to in the lower level (recall that ${\textsf{Pref}(a)}$ and its strict counterpart ${\textsf{PrefS}(a)}$ are both a superset of ${\textsf{PrefSC}(a)}$). Therefore, we have the following useful observation.

Observation 1

If a vertex $b\in \mathcal {B}$ receives a proposal from some $a'\in \mathcal {A}$ at a level z then b receives proposals from all its neighbours who exhausted their preference list at level z.

4 Correctness of Our Algorithm

We prove that the matching M output by Algorithm 1 is

• (I) Critical as well as relaxed stable (RSM) and

• (II) A $\frac{3}{2}$ approximation to the maximum size CRITICAL-RSM in G.

We define a partition of the vertices in $\mathcal {A}\cup \mathcal {B}$ based on the levels of vertices in $\mathcal {A}$ and the matching M. This partition is useful to establish the correctness of our algorithm.

Partition of Vertices: The vertex set $\mathcal {A}$ is partitioned into $\mathcal {A}_0\cup \mathcal {A}_1\cup \ldots \cup \mathcal {A}_{{t}}\cup \ldots \cup \mathcal {A}_{{s}+{t}}$, and the vertex set $\mathcal {B}$ is partitioned into $\mathcal {B}_0\cup \mathcal {B}_1\cup \ldots \cup \mathcal {B}_{{t}}\cup \ldots \cup \mathcal {B}_{{s}+{t}}$. For every matched vertex $a\in \mathcal {A}$ there exists $x\in \{0,\ldots ,{s}+{t}\}$ such that $(a^x,b)\in M$. We use x to partition the vertex set. Note that if $(a^{{t}^*},b)\in M$ then for the purpose of partitioning we consider ${t}^*={t}$ as ${t}^*$ is a sub-level of the level ${t}$.

• Matched vertices in $\mathcal {A}\cup \mathcal {B}$: Let $a\in \mathcal {A}, b\in \mathcal {B}$ and $(a^x,b)\in M$ for some $x\in \{0,\ldots ,{s}+{t}\}$. We add a to $\mathcal {A}_x$ and b to $\mathcal {B}_x$.

• Unmatched vertices in $\mathcal {A}\cup \mathcal {B}$:

  • If a non-critical vertex $a\in \mathcal {A}$ is unmatched in M then we add a to $\mathcal {A}_{{t}}$.

  • If a critical vertex $a\in \mathcal {A}$ is unmatched in M then we add a to $\mathcal {A}_{{s}+{t}}$.

  • If a non-critical vertex $b\in \mathcal {B}$ is unmatched in M then we add b to $\mathcal {B}_{{t}}$.

  • If a critical vertex $b\in \mathcal {B}$ is unmatched in M then we add b to $\mathcal {B}_0$.

It is convenient to visualize the partitions as shown in Fig. 2. This particular drawing of the graph G is denoted by $G_M$ throughout the rest of the section. It is useful to assume that the edges in $G_M$ are implicitly directed from $\mathcal {A}$ to $\mathcal {B}$. By construction, the edges of M (shown in blue colour) are horizontal whereas the unmatched edges (shown as solid black edges) can be horizontal, upwards or downwards. We state the properties of the vertices and edges in $G_M$ with respect to this partition in Property 1 (see the full version [21] for justification).

Fig. 2.

The graph $G_M$. Red vertices are critical and black vertices are non-critical. Matched vertices are represented by circles, and unmatched vertices are represented by squares. The blue horizontal lines represent matched edges in M. Solid black lines represent edges which are not matched in M. Note that no edge in $G_M$ is of the form $\mathcal {A}_x\times \mathcal {A}_y$ for $y\le x-2$. (Color figure online)

Property 1

Let $a\in \mathcal {A}$ and $b\in \mathcal {B}$. Then the following hold in graph $G_M$.

• 1. If $a\in \bigcup _{x={t}+1}^{{s}+{t}}\mathcal {A}_x$ then a is critical. Thus, $|\bigcup _{x={t}+1}^{{s}+{t}}\mathcal {A}_x|\le {s}$.

• 2. If $b\in \bigcup _{x=0}^{{t}-1}\mathcal {B}_x$ then b is critical. Thus, $|\bigcup _{x=0}^{{t}-1}\mathcal {B}_x|\le {t}$.

• 3. If a is critical and is unmatched in M then $a\in \mathcal {A}_{{s}+{t}}$ and all the neighbours of a are matched and present in $\mathcal {B}_{{s}+{t}}$ only.

• 4. If a is not critical and is unmatched in M then $a\in \mathcal {A}_{{t}}$ and all the neighbours of a are matched and present in $\mathcal {B}_{x}$ for $x\ge {t}$.

• 5. If b is critical and is unmatched in M then $b\in \mathcal {B}_{0}$ and all the neighbours of b are present in $\mathcal {A}_{0}$ only.

• 6. If b is not critical and is unmatched in M then $b\in \mathcal {B}_{{t}}$ and all the neighbours of b are present in $\mathcal {A}_{x}$ for $x\le {t}$.

Let $(a, b)\in E$ be an edge such that $a \in \mathcal {A}_x$ and $b\in \mathcal {B}_y$. We say that such an edge is of the form $\mathcal {A}_x \times \mathcal {B}_y$. Lemma 1 below gives an important property about the edges which cannot be present in $G_M$. An edge of the form $\mathcal {A}_x \times \mathcal {B}_y$ with $x>y+1$ is referred to as a steep downward edge.

Lemma 1

The graph $G_M$ does not contain steep downward edges. That is, there is no edge in $G_M$ of the form $\mathcal {A}_x \times \mathcal {B}_y$ such that $x>y+1$.

Proof

Let (a, b) be any edge in $G_M$ such that $a\in \mathcal {A}_x$ and $b\in \mathcal {B}_y$. If b is unmatched, then irrespective of whether b is critical or not by Property 1(5) and Property 1(6), we have $x\le y$. Now suppose that b is matched and $(a',b)\in M$. If $a=a'$ then by construction of $G_M$, $(a,b)\in \mathcal {A}_x \times \mathcal {B}_x$. If $a\not =a'$, then we use Claim 1, which is given below. It is immediate from this claim that b is in $\mathcal {B}_y$ for $y\ge x-1$. $\square$

Claim 1

Let $(a,b)\in E\setminus M$ and b be matched in M to $\tilde{a}$ at level y, that is, $M(b)=\tilde{a}^y$. If the level x of a is at least 2 then $y\ge x-1$.

Proof

Suppose for contradiction that there exists $\tilde{a}\in \mathcal {A}$ such that $(\tilde{a}^y,b)\in M$ for $y<x-1$. The fact that $(a,b)\in E$ and a achieves the level x implies that a remains unmatched after $a^{x-1}$ exhausted its preference list ${\textsf{Pref}(a)}$, ${\textsf{PrefS}(a)}$ or ${\textsf{PrefSC}(a)}$ as appropriate. Since b is matched to a vertex at level $y<x-1$, and $a^{x-1}$ exhausted its preference list, by Observation 1, b received a proposal from $a^{x-1}$. At this time, b must accept this proposal by rejecting $\tilde{a}^y$ because $y<x-1$. This implies $(\tilde{a}^y,b)\notin M$ which contradicts our assumption that $(\tilde{a}^y,b)\in M$ for $y<x-1$. $\square$

Lemma 2

Let (a, b) be a blocking pair w.r.t. M. Then the corresponding edge in $G_M$ is an upward edge.

Proof

For the blocking pair (a, b) let a and b be at levels x and y, respectively. First, suppose that b is a critical vertex. Since (a, b) is a blocking pair, irrespective of whether a is matched or unmatched, $a^x$ must have proposed to the critical vertex b. Thus, b cannot remain unmatched. This implies M(b) exists. We consider the following two cases:

• 1. The proposal by a to b results in (a, b) to be uncertain: Note that $a^x$ is rejected by b because b receives another proposal, and hence $a^x$ marks b. Since (a, b) is a blocking pair, M(a) is ranked lower than b. However, before proposing to any vertex ranked strictly lower than b, $a^x$ must propose to the marked vertex b. At this point, either b is matched to a better preferred partner than a which contradicts that (a, b) blocks M, otherwise, b accepts the proposal from $a^x$. Thus, $a^x$ is matched to either b or to some other vertex on the same rank as b. This implies (a, b) is not a blocking edge.

• 2. The proposal by a to b does not result in (a, b) to be uncertain: The fact that $a\succ _b M(b)$ implies M(b) must be at a level y such that $y>x$. Thus, (a, b) edge is an upward edge in $G_M$.

Now, suppose that b is a non-critical vertex. Then by Property 1(2), $b\in \mathcal {B}_y$ for $y\ge {t}$. If $x<{t}$, then (a, b) is an upward edge, and we are done. Hence, assume that $x\ge {t}$. Since $x\ge {t}$, $a^x$ is proposes to all of its neighbours. Again, since (a, b) is a blocking pair, irrespective of whether a is matched or unmatched, $a^x$ must have proposed to b. Thus, b cannot be unmatched. Now, either b is matched to a better-preferred partner than a, which contradicts that (a, b) is a blocking pair or M(b) is at a higher level than a and hence (a, b) is an upward edge. $\square$

Lemma 3 below shows that the matching M output by Algorithm 1 is critical.

Lemma 3

The output matching M is critical for G.

Proof sketch:

We prove the criticality of M by using the level structure of the graph $G_{M}$. The idea is to show that there is no alternating path $\rho$ in $G_M$ with respect to M such that the number of critical vertices matched in $M\oplus \rho$ is more than the number of critical vertices matched in M. We prove the criticality for the individual parts, that is, for $\mathcal {A}$-part and for $\mathcal {B}$-part. In other words, we show that M matches maximum possible critical nodes from $\mathcal {A}$-side, and maximum possible critical nodes from the $\mathcal {B}$-side. This immediately implies that M matches the maximum possible critical nodes that can be matched in any matching. Hence, M is critical. For the $\mathcal {A}$-part we show that the path $\rho =\langle u_0,v_1,u_1,\ldots \rangle$ begins at the highest level ${s}+{t}$ with an unmatched critical vertex $u_0\in \mathcal {A}$. Using Property 1(5), we also show that at least the first two vertices on the $\mathcal {A}$-side ($u_0$ and $u_1$) on $\rho$ are at the same level ${s}+{t}$. Then we argue that the other end of $\rho$ must be at a level below ${t}+1$. Since there are no steep downward edges (Lemma 1), the path contains at least one vertex from each level ${t}+1, \ldots , {s}+{t}-1$. Thus, we have at least ${s}+1$ many vertices in $\mathcal {A}_{{t}+1}\cup \ldots \cup \mathcal {A}_{{s}+{t}}$. This contradicts Property 1(1). Proof for the $\mathcal {B}$-part is analogous. See full version [21] for the complete proof. $\square$

Lemma 4

The output matching M of Algorithm 1 is RSM for G.

Proof

If there is no blocking pair w.r.t. M then we are done. Hence, assume that (a, b) is a blocking pair w.r.t. M. By Lemma 2, (a, b) is an upward edge. We consider two cases based on the level of b.

Case 1: $b\in \mathcal {B}_y$ for $y\le {t}$. Clearly, $a\in \mathcal {A}_x$ for $x\le {t}-1$. Thus, by the construction of $G_M$, a is matched, and hence M(a) exists. Clearly, M(a) is at level at most ${t}-1$. By Property 1(2), M(a) is critical. Hence, the blocking pair (a, b) is justified by Condition 1 of Definition 2.

Case 2: $b\in \mathcal {B}_y$ for $y> {t}$. By construction of $G_M$, b is matched. Thus, M(b) exists and $M(b)\in \mathcal {A}_x$ for $x\ge {t}+1$. By Property 1(1), M(b) is critical. Hence, the blocking pair (a, b) is justified by Condition 2 of Definition 2. $\square$

Lemma 5

Let $M'$ be any maximum size CRITICAL-RSM and M be the output of Algorithm 1 for an instance of our problem. Then $|M|\ge \frac{2}{3}\cdot |M'|$.

Proof

We prove that $M \oplus M'$ does not admit any 1-length or 3-length augmenting path w.r.t. M. This immediately implies that $|M|\ge \frac{2}{3}\cdot |M'|$. If a is unmatched (critical or otherwise), we know from Property 1(3) and Property 1(4) that no neighbour b of a is unmatched in M. Thus, M is a maximal matching.

For contradiction assume that $M\oplus M'$ contains a 3-length augmenting path $\rho =\langle a_1,b,a,b_1\rangle$ w.r.t. M. Here $(a,b) \in M$ and the other two edges are in $M'$. We show that (a, b) blocks $M'$ and the blocking pair is not justified. This will contradict relaxed stability of $M'$. We first establish the levels of the vertices.

Levels of Vertices: The fact that $a_1$ remains unmatched in M implies that $a_1^{{t}^*}$ exhausted ${\textsf{Pref}(a_1)}$. Thus, $a_1$ is at level at least ${t}^*$. Since $b_1$ remains unmatched in M, a did not exhaust ${\textsf{Pref}(a)}$ at the level ${t}$. Thus, a is at level at most ${t}$. We claim that $a_1$ is not at level ${t}+1$ or higher. If $a_1$ is at level $x\ge {t}+1$ then $a_1^x$ must have proposed to b as $a_1$ is unmatched in M. Since a is at level at most ${t}$, b must reject a and accept $a_1$ – a contradiction to $(a,b)\in M$. Thus, we conclude that $a_1$ is at level ${t}^*$. Now, if a is at level $y<{t}$ then b must reject a and accept $a_1$ as $a_1$ at level ${t}^*$ proposed to it. Recall that ${t}^*$ is a sub-level of ${t}$ used in the algorithm, and ${t}^*$ does not appear as a separate level in $G_M$. Thus, the vertices $a,a_1\in \mathcal {A}_{{t}}$.

The Pair (a, b) Blocks $M'$: If $a_1\succ _b a$, then b would have accepted the proposal of $a_1^{{t}}$ by rejecting $a^{{t}}$. Thus, $a\succeq _b a_1$. Since $a_1^{{t}^*}$ was rejected by b, it implies $M(b)=a$ and $a_1$ cannot be in tie for b, otherwise b would not have rejected a $*$ status vertex over a non $*$ status vertex. Thus, $a\succ _{b} a_1$. Now, we show that $b\succ _{a} b_1$. Suppose not. Then, if $b_1\succ _{a} b$, then $a^{{t}}$ must have proposed to $b_1$ before b and got matched to it – a contradiction that $b_1$ is unmatched. Hence, assume that $b=_{a} b_1$. In this case, when $a^{{t}}$ proposes to b, the vertex b must also be unmatched; otherwise, b cannot be a favourite neighbour of $a^{{t}}$. This implies that $a_1$ proposes to b only after a proposes to b. Since $b_1$ was unmatched when a proposed to b, the proposal from a to b was uncertain. We claim that b must reject the proposal by a after the proposal (a, b) becomes uncertain due to a proposal by some vertex, possibly $a_1^{{t}}$. Such a vertex must exist because $a_1^{{t}}$ proposed to b after (a, b) becomes uncertain. Since a has an unmatched neighbour $b_1$ at the same rank, a must have proposed $b_1$ before proposing to b again. This implies $b_1$ is matched, a contradiction. Thus, $b\succ _{a} b_1$; hence (a, b) blocks $M'$.

The Blocking Pair (a, b) is not Justified: In order to prove this, we show $b_1= M'(a)$ and $a_1= M'(b)$ are both non-critical. Note that $b_1$ is unmatched in M, hence if it is critical then $b_1\in \mathcal {B}_0$ and the number of critical vertices on $\mathcal {B}$-side is at least 1 (that is ${t}\ge 1$). This implies that a cannot be at a level $\ge 1$ since it has not yet proposed to at least one critical neighbour, namely $b_1$. Thus, $b_1$ is not critical. We finish the proof by showing that $a_1$ is also not critical. Note that $a_1$ is unmatched in M, hence, if it is critical then $a_1\in \mathcal {A}_{{s}+{t}}$ and ${s}>0$. This is a contradiction that $a_1\in \mathcal {A}_{{t}}$. Thus, $a_1$ is not critical.

This finishes the proof that the claimed 3-length augmenting path w.r.t. M does not exist establishing the size guarantee. $\square$

Using Lemma 3, Lemma 4 and Lemma 5, we establish Theorem 1.

5 Conclusion

In this work, we consider the problem of computing a matching in the stable marriage problem where ties and critical vertices can appear on both sides of the bipartition. We investigate a recently introduced notion of optimality called relaxed stability for our setting. We show that every instance of our problem admits a Relaxed Stable Matching (RSM) which is also critical. It follows from the known results [6, 18] that computing a maximum size critical RSM is NP-hard and hard to approximate within any factor smaller than $\frac{21}{19}$. We present a polynomial-time algorithm to compute a $\frac{3}{2}$-approximation of the maximum size critical RSM.