Keynote
|
Date : 22 mai 2025 14:00 - Salle :Amphi 3 - Pôle commun
Odd Paths, Cycles, Cuts: Connections and AlgorithmsAndras Sebö, DR CNRS - G-SCOP |
Minimizing the weight of an edge-set satisfying parity constraints is a challenging branch of combinatorial optimization as witnessed by the binary hypergraph chapter of Alexander Schrijver's book [Combinatorial Optimization, Springer-Verlag, 2003, Chapter 80]. This framework contains relevant graph theory problems including open cases of the Max Cut problem and some multiflow problems.
We clarify the interconnections between some particularly interesting problems of this area, establishing new results on their complexity, including the solution of a long-standing open question asked by Lov\'asz (Open Problem 27 in Schrijver's book [Combinatorial Optimization, Springer-Verlag, 2003]).
After clarifying some negative, and some positive complexity behaviors of some mistreated problems , we idenfify a main open challenge, state some new related conjectures and provide some partial results towards their solution.
https://en.wikipedia.org/wiki/Andr%C3%A1s_Seb%C5%91
https://pagesperso.g-scop.grenoble-inp.fr/~seboa/