Popular Edges with Critical Nodes

Kushagra Chatterjee, Prajakta Nimbhorkar

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$ h…