The Unimodular Intersection Problem
Technion - Israel Institute of Technology
Minisymposium: GENERAL SESSION TALKS
Content: We show that finding minimally intersecting n paths from s to t in a directed graph or n perfect matchings in a bipartite graph can be done in polynomial time. This holds more generally for unimodular set systems.