We consider the stable marriage problem in the presence of tied preferences and critical vertices. The input to our problem is a bipartite graph G = (A ∪ B, E) where A and B denote sets of vertices which need to be matched. Each vertex in A ∪ B possesses a preference ordering over its neighbours, which may include ties. Additionally, a subset of vertices is designated as critical, with the objective of producing a matching that accommodates as many critical vertices as possible. Such matchings are commonly referred to as critical matchings in the literature. In our setting, we aim to compute a matching that is both critical and optimal based on the preferences of the vertices.

Stability is a widely accepted notion of optimality in the context of two-sided preferences. There are simple examples that show that in the presence of critical vertices (even without ties in preferences), a matching that is both critical and stable may not exist. Popularity is another extensively studied notion of optimality in the two-sided preference list setting. However, in the presence of ties (even without critical vertices), the existence of a popular matching is not guaranteed. We, therefore, consider the notion of relaxed stability, which was introduced and studied by Krishnaa et al. (SAGT 2020).

We present a multi-level Gale and Shapley algorithm for computing critical matching, which is relaxed stable. This proves that in our setting, a critical matching that is relaxed stable always exists, although computing a maximum-sized relaxed stable matching turns out to be NP-hard. To achieve a good approximation to the size of maximum size critical relaxed stable matching, we combine our multi-level algorithm with Kiraly's algorithm. Our algorithm matches the best-known approximation guarantee of 3/2, known for the stable matching problem with ties (without critical vertices).