Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00364609" target="_blank" >RIV/68407700:21240/22:00364609 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1016/j.ic.2022.104943" target="_blank" >https://doi.org/10.1016/j.ic.2022.104943</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ic.2022.104943" target="_blank" >10.1016/j.ic.2022.104943</a>
Alternative languages
Result language
angličtina
Original language name
Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
Original language description
We continue and extend previous work on the parameterized complexity analysis of the NP-hard STABLE ROOMMATES WITH TIES AND INCOMPLETE LISTS problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem STABLE MARRIAGE which focuses on a bipartite scenario, STABLE ROOMMATES WITH INCOMPLETE LISTS allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded disjoint paths modulator number (these are each time the respective parameters). Moreover, we obtain that 'only' asking for perfect stable matchings or the mere existence of a stable matching is fixed-parameter tractable with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Information and Computation
ISSN
0890-5401
e-ISSN
1090-2651
Volume of the periodical
289
Issue of the periodical within the volume
November
Country of publishing house
US - UNITED STATES
Number of pages
41
Pages from-to
—
UT code for WoS article
000914897100016
EID of the result in the Scopus database
2-s2.0-85136132643