Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 08, 2020, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
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. In this talk I show some new approaches and partial results that give new hope in resolving this long standing open problem.
Automatic MiSe System Software Version 1.4803M | admin login