3 papers
cs.DM2026
The canonical facets of multi-separator polytopes
Bjoern Andres, Silvia Di Gregorio, Jannik Irmai +2
We initiate a polyhedral study of the graph multi-separator problem proposed by Irmai et al. (2024) as an alternative to the lifted multicut problem for application to the task of…
cs.LG2026
Graph Neural Networks with Triangle-Based Messages for the Multicut Problem
Jannik Irmai, Lucas Fabian Naumann, Bjoern Andres
The multicut problem is an NP-hard combinatorial optimization problem with diverse applications in fields such as bioinformatics, data mining and computer vision. Graph neural netw…
cs.DM2024
Chorded cycle facets of the clique partitioning polytope
Jannik Irmai, Lucas Fabian Naumann, Bjoern Andres
The -chorded -cycle inequalities are a class of valid inequalities for the clique partitioning polytope. It is known that for , these inequalitie…