  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 = (A U B, E) where A and 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 A U 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 a critical matching which is relaxed stable always exists in our
setting although computing a maximum-sized relaxed stable matching turns out to
be NP-hard. Our main contribution is a 3/2 approximation to the maximum-sized
critical relaxed stable matching for the stable marriage problem with two-sided
ties and critical vertices.
