CNRS ENS Lyon inria 200x200 blurb
UCB Lyon logo univ lyon 200x200 blurb

Carl Feghali

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)

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 :