Uncrossing a family of set-pairs

Frank and Jordan [1] proved an important min-max result on covering a cross ing family of set-pairs. As an application, among others they can solve the unweighted node-connectivity augmentation problem for directed graphs in p olynomial time. In this paper, we show how to solve the dual packing proble m in polynomial time. To decompose a fractional dual optimum as a convex co mbination of integer vertices, besides the ellipsoid method, we use a polyn omial-time algorithm for uncrossing a family of set-pairs. Our main result is this uncrossing algorithm.