Carl Feghali, chercheur au LIP, dans l'équipe MC2 a reçu le prix du Best paper ISAAC 2023.
The 34th International Symposium on Algorithms and Computation (ISAAC 2023)
https://www.kurims.kyoto-u.ac.jp/isaac/isaac2023/
Titre : Matching Cuts in Graphs of High Girth and H-Free Graphs (avec Felicia Lucke, Daniël Paulusma et Bernard Ries)
The matching cut problem is to decide if a connected graph has a matching that is also an edge cut. We prove that the matching cut problem is NP-complete for graphs with arbitrary large fixed girth and bounded maximum degree.
This resolves a 20-year old problem that was reiterated several times in the literature.
Moreover, we prove a number of complementary results on the matching cut problem and variants thereof.
En savoir plus : https://arxiv.org/abs/2212.12317
LIP / Équipe MC2