2022/12/07 by Ildikó Schlotter, Schlotter, Ildikó
Computer Science · Economics, Econometrics and Finance · #68Q27 (Primary) 68Q25 #91A68 #91B10 #91B68 (Secondary) #Advanced Algebra and Logic #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2212.03521
openalex publication_date 2022/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A preference system I is an undirected graph where vertices have preferences over their neighbors, and I admits a master list if all preferences can be derived from a single ordering over all vertices. We study the problem of deciding whether a given preference system I is close to admitting a master list based on three different distance measures. We determine the computational complexity of the following questions: can I be modified by (i) k swaps in the preferences, (ii) k edge deletions, or (iii) k vertex deletions so that the resulting instance admits a master list? We investigate these problems in detail from the viewpoint of parameterized complexity and of approximation. We also present two applications related to stable and popular matchings.