Almost Disjoint Paths and Separating by Forbidden Pairs

Oliver Bachtler, Tim Bergner, Sven O. Krumke

By Menger's theorem the maximum number of arc-disjoint paths from a vertex s to a vertex t in a directed graph equals the minumum number of arcs needed to disconnect s and t, i.e.,…