During the 34th International Symposium on Algorithms and Computations 2023 (ISAAC 2023), which was held in Kyoto (Japan), Prof. Bernard Ries together with his PhD student Felicia Lucke, with Prof. Daniël Paulusma (Durham University, UK) and with Dr. Carl Feghali (ENS Lyon, France) received the Best Paper Award for their paper entitled Matching Cuts in Graphs of High Girth and H-Free Graphs.
In this paper, they contribute with new computational complexity results regarding the Matching Cut Problem with a focus on graphs having large girth, i.e. where the length of a shortest cycle is large, as well as graphs forbidding a fixed induced subgraph. One of their results resolves a 20-years old open problem. Thanks to these results, a better insight is gained in the complexity of the abovementioned problem.
