Matchings:

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[1]-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}.