  In the popular edge problem, the input is a bipartite graph $G = (A \cup
B,E)$ where $A$ and $B$ denote a set of men and a set of women respectively,
and each vertex in $A\cup B$ has a strict preference ordering over its
neighbours. A matching $M$ in $G$ is said to be {\em popular} if there is no
other matching $M'$ such that the number of vertices that prefer $M'$ to $M$ is
more than the number of vertices that prefer $M$ to $M'$. The goal is to
determine, whether a given edge $e$ belongs to some popular matching in $G$. A
polynomial-time algorithm for this problem appears in \cite{CK18}. We consider
the popular edge problem when some men or women are prioritized or critical. A
matching that matches all the critical nodes is termed as a feasible matching.
It follows from \cite{Kavitha14,Kavitha21,NNRS21,NN17} that, when $G$ admits a
feasible matching, there always exists a matching that is popular among all
feasible matchings. We give a polynomial-time algorithm for the popular edge
problem in the presence of critical men or women. We also show that an
analogous result does not hold in the many-to-one setting, which is known as
the Hospital-Residents Problem in literature, even when there are no critical
nodes.
