Cuts and Disjoint Paths in the Valley-Free Path Model

graph is valid if it consists of a sequence of forward edges
followed by a sequence of backward edges. This model is
motivated by routing policies of autonomous systems
in the Internet. We give a $2$-approximation algorithm for
the problem of computing a maximum number of edge- or
vertex-disjoint valid paths between two given vertices
$s$ and $t$, and we show that no better approximation
ratio is possible unless $\PP=\NP$. Furthermore, we
give a $2$-approximation for the problem of computing
a minimum vertex cut that separates $s$ and $t$ with
respect to all valid paths and prove that the problem
is APX-hard. The corresponding problem for edge cuts
is shown to be polynomial-time solvable. We present
additional results for acyclic graphs.