English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We continue and extend previous work on the parameterized complexity analysisof the NP-hard Stable Roommates with Ties and Incomplete Lists problem, therebystrengthening earlier results both on the side of parameterized hardness aswell as on the side of fixed-parameter tractability. Other than for its famoussister problem Stable Marriage which focuses on a bipartite scenario, StableRoommates with Incomplete Lists allows for arbitrary acceptability graphs whoseedges specify the possible matchings of each two agents (agents are representedby graph vertices). Herein, incomplete lists and ties reflect the fact that inrealistic application scenarios the agents cannot bring all other agents into alinear order. Among our main contributions is to show that it is W[1]-hard tocompute a maximum-cardinality stable matching for acceptability graphs ofbounded treedepth, bounded tree-cut width, and bounded disjoint paths modulatornumber (these are each time the respective parameters). However, if we `only'ask for perfect stable matchings or the mere existence of a stable matching,then we obtain fixed-parameter tractability with respect to tree-cut width butnot with respect to treedepth. On the positive side, we also providefixed-parameter tractability results for the parameter feedback edge setnumber.

Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters