  Particle physics experiments often require the simultaneous reconstruction of
many interaction vertices. Usually, this problem is solved by ad hoc heuristic
algorithms. We propose a universal approach to address the multiple vertex
finding through a principled formulation as a minimum-cost lifted multicut
problem. The suggested algorithm is tested in a typical LHC environment with
multiple proton-proton interaction vertices. Reconstruction errors caused by
the particle detectors complicate the solution and require the introduction of
special metrics to assess the vertex-finding performance. We demonstrate that
the minimum-cost lifted multicut approach outperforms heuristic algorithms and
works well up to the highest vertex multiplicity expected at the LHC.
