Schlotter, Ildikó Anna (2024) Recognizing when a preference system is close to admitting a master list. THEORETICAL COMPUTER SCIENCE, 994. No. 114445. ISSN 0304-3975
|
Text
ms_TCS.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (602kB) | Preview |
Abstract
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. © 2024 The Author(s)
| Item Type: | Article |
|---|---|
| Additional Information: | HUN-REN Centre for Economic and Regional Studies, Budapest, Hungary Budapest University of Technology and Economics, Budapest, Hungary Export Date: 8 March 2024 CODEN: TCSCD Correspondence Address: Schlotter, I.; HUN-REN Centre for Economic and Regional StudiesHungary; email: schlotter.ildiko@krtk.hun-ren.hu Funding details: Magyar Tudományos Akadémia, MTA, LP2021-2 Funding text 1: Supported by the Hungarian Academy of Sciences under its János Bolyai Research Scholarship and its Momentum Programme ( LP2021-2 ). |
| Uncontrolled Keywords: | Preference system, Master list, Parameterized complexity, Approximation, Preference swap, Vertex/edge deletion |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 09 Sep 2024 13:58 |
| Last Modified: | 09 Sep 2024 13:58 |
| URI: | https://real.mtak.hu/id/eprint/204564 |
Actions (login required)
 |
Edit Item |
