Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Information and Computation

ISSN

0890-5401

e-ISSN

1090-2651

Svazek periodika

289

Číslo periodika v rámci svazku

November

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

41

Strana od-do

—

Kód UT WoS článku

000914897100016

EID výsledku v databázi Scopus

2-s2.0-85136132643