Report
Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
| العنوان: | Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs |
|---|---|
| المؤلفون: | Kawase, Sota, Miyazaki, Shuichi |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computer Science and Game Theory, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms |
| الوصف: | The Seat Arrangement Problem is a problem of finding a desirable seat arrangement for given preferences of agents and a seat graph that represents a configuration of seats. In this paper, we consider decision problems of determining if an envy-free arrangement exists and an exchange-stable arrangement exists, when a seat graph is an $\ell \times m$ grid graph. When $\ell=1$, the seat graph is a path of length $m$ and both problems have been known to be NP-complete. In this paper, we extend it and show that both problems are NP-complete for any integer $\ell \geq 2$. Comment: Typos and errors are corrected |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2411.10719 |
| رقم الانضمام: | edsarx.2411.10719 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |