Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 18, 2023, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Nicolas El Maalouly
In the Exact Matching problem, we are given a graph with edges colored red and blue, and an integer k. The goal is to output a perfect matching with exactly k red edges. After introducing the problem in 1982, Papadimitriou and Yannakakis conjectured it to be NP-hard. Soon after, however, Mulmuley et al. proved in 1987 that it can be solved in randomized polynomial time, which makes it unlikely to be NP-hard. Determining whether Exact Matching is in P remains an open problem and very little progress has been made towards that goal. The study of EM resulted in the definition of several new matching problems. In this talk I will introduce some of these problems and show how they are related.
Automatic MiSe System Software Version 1.4803M | admin login