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
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 יוני 2021

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1703???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Popular Matching in Roommates Setting Is NP-hard'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי