This set of problems focuses on finding a mathing in a graph. One very popular variant is stable marriage problem where the goal is to create a matching on a bipartite graph, where each vertex has its preference list of neighbors, such that no pair of non-matched vertices want to be with each other more than their current match – that would be so called blocking pair.
On February of 2018 Chen, Hermelin, Sorge, and Yedidsion 1 studied the Egalitarian optimal stable matchings, in which we want to minimize the sum of chosen indices over all the preference lists, and with Matchings with minimum number of blocking pairs, where we want to minimize the number of blocking pairs. For the egalitarian version they show that parametrized by the resulting sum it is fixed-parameter tractable. On the other hand, for the second variant they show it is W-hard when parametrized by number of blocking pairs.
March 2018 Gupta, Misra, Saurabh, and Zehavi 2.
January 2018 Chen and Niedermeier 3.
June 2018 Faenza, Kavitha, Powers, and Zhang 4.