Matching under preferences is a research area that finds numerous applications in practice as diverse as assigning colleges to students, workers to firms, kidney donors to recipients and users to servers in a distributed internet service, to just name a few. Indeed this topic is at the heart of the intersection between Computer Science and Economics, and has been recognized as such by a Nobel prize in Economics. Various real-life applications require us to "solve" computationally hard matching problems. Parameterized Complexity provides the algorithmic and computational tools to handle these problems.
In this talk we will focus on two canonical concepts in this area namely, stable matching and its generalization popular matching. In the first part, we will discuss the stable matching problem and its various avatars. In the second part, I will outline a new result that resolved the arguably main open problem in the subarea of popular matching: In an arbitrary graph, deciding if a popular matching exists is NP-hard. The computational complexity of this problem has been unknown for over a decade, during which it was repeatedly posed as a fundamental open question.