论文标题
关键节点的流行边缘
Popular Edges with Critical Nodes
论文作者
论文摘要
在流行的边缘问题中，输入是二分图$ g =（a \ cup b，e）$，其中$ a $ a $ a和$ b $分别表示一组男人和一组女性，每个顶点$ a \ cup b $ in $ a \ cup b $都有严格的偏好订单。如果没有其他匹配的$ m'$，则据说$ g $中的$ m $ $ $ g $，以至于偏爱$ m'$而不是$ m $的顶点的数量超过偏爱$ m $ to $ m'$的顶点的数量。目标是确定给定的边缘$ e $是否属于$ g $中的某些受欢迎的匹配。此问题的多项式时间算法出现在\ cite {ck18}中。当一些男人或女人被优先或关键时，我们认为流行的边缘问题。与所有关键节点匹配的匹配称为可行的匹配。从\ cite {kavitha14，kavitha21，nnrs21，nn17}开始，当$ g $允许可行的匹配时，总是存在一个在所有可行的匹配中很受欢迎的匹配。在关键男人或女性的存在下，我们为流行边缘问题提供多项式时间算法。我们还表明，类似的结果并不能在多一对一的环境中得出，即使没有关键的节点，也称为文献中的医院居民问题。
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.
