Popular Matching in Roommates Setting Is NP-hard

Sushmita Gupta, Pranabendu Misra, Saket Saurabh, Meirav Zehavi

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

An input to the POPULAR MATCHING problem, in the roommates setting (as opposed to the marriage setting), consists of a graph G (not necessarily bipartite) where each vertex ranks its neighbors in strict order, known as its preference. In the POPULAR MATCHING problem the objective is to test whether there exists a matching M∗such that there is no matching M where more vertices prefer their matched status in M (in terms of their preferences) over their matched status in M∗. In this article, we settle the computational complexity of the POPULAR MATCHING problem in the roommates setting by showing that the problem is NP-complete. Thus, we resolve an open question that has been repeatedly and explicitly asked over the last decade.

اللغة الأصليةإنجليزيّة أمريكيّة
رقم المقال9
دوريةACM Transactions on Computation Theory
مستوى الصوت13
رقم الإصدار2
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يونيو 2021

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!Computational Theory and Mathematics

بصمة

أدرس بدقة موضوعات البحث “Popular Matching in Roommates Setting Is NP-hard'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا