Popular Edges with Critical Nodes

Abstract

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^{\prime }$ such that the number of vertices that prefer $M^{\prime }$ to $M$ is more than the number of vertices that prefer $M$ to $M^{\prime }$. 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.

Selected in ISAAC 2022 Conference