Algorithmics and Computational Complexity Research GroupTalk 25.04.2019

# Structural Parameterizations of Stable Roommates with Ties

Klaus  Heeger (TU Berlin)

Given a set of agents with strict preferences over all other agents, the polynomial-time solvable Stable Roommates problem asks to find a stable matching of the agents. A matching is stable if there is no pair of agents who both prefer each other over their partners in the matching.
We consider the well-known NP-complete generalization Stable Roommates with Ties and Incomplete Preferences (SRTI). In SRTI, agents can be unacceptable (that is, some pairs of agents cannot be matched) and agents are allowed to tie two or more persons in their preference list.
We study the parameterized complexity of this problem, focussing on graph-theoretic parameters. Solving an open question by Adil et al. (TCS 2018), we show that SRTI is W[1]-hard when parameterized by tree-width. In fact we even show that SRTI is W[1]-hard for feedback vertex set size as well as for tree-depth. On the positive side SRTI becomes fixed-parameter tractable when parameterized by feedback edge set or tree-cut-width. Furthermore, we show that finding a maximum-size stable matching is W[1]-hard for tree-cut-width, but there exists an algorithm that computes a factor-two approximation in FPT time for this parameter.

Date
Speaker
Location
Language
25.04.2019
16:15
Klaus Heeger
TEL 512
English

Back to the research colloquium site.