License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.54
URN: urn:nbn:de:0030-drops-173399
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17339/
Go to the corresponding LIPIcs Volume Portal

Chatterjee, Kushagra ; Nimbhorkar, Prajakta

Popular Edges with Critical Nodes

pdf-format:
LIPIcs-ISAAC-2022-54.pdf (0.7 MB)

Abstract

In the popular edge problem, the input is a bipartite graph G = (A ∪ B,E) where A and B denote a set of men and a set of women respectively, and each vertex in A∪ B has a strict preference ordering over its neighbours. A matching M in G is said to be 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 [Cseh and Kavitha, 2018].
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 [Telikepalli Kavitha, 2014; Kavitha, 2021; Nasre et al., 2021; Meghana Nasre and Prajakta Nimbhorkar, 2017] 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.

BibTeX - Entry

@InProceedings{chatterjee_et_al:LIPIcs.ISAAC.2022.54,
  author =	{Chatterjee, Kushagra and Nimbhorkar, Prajakta},
  title =	{{Popular Edges with Critical Nodes}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17339},
  URN =		{urn:nbn:de:0030-drops-173399},
  doi =		{10.4230/LIPIcs.ISAAC.2022.54},
  annote =	{Keywords: Matching, Stable Matching, Popular feasible Matching}
}

Keywords: Matching, Stable Matching, Popular feasible Matching
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI