Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 18, 2021, 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 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. For special graph classes Yuster showed that Exact Matching is in P for K_3,3-minor free graphs, which include planar graphs. Karzanov showed that it is in P for complete and bipartite complete graphs. In this talk I will show how to solve Exact Matching on graphs of bounded independence number. This is joint work with Raphael Steiner.
Automatic MiSe System Software Version 1.4803M | admin login