  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., the minimum size of an s-t-cut. The max-flow problem
in a network with unit capacities is equivalent to the arc-disjoint paths
problem. Moreover the max-flow and min-cut problems form a strongly dual pair.
We relax the disjointedness requirement on the paths, allowing them to be
almost disjoint, meaning they may share up to one arc. The resulting almost
disjoint paths problem (ADP) asks for k s-t-paths such that any two of them are
almost disjoint. The separating by forbidden pairs problem (SFP) is the
corresponding dual problem and calls for a set of k arc pairs such that every
s-t-path contains both arcs of at least one such pair.
  In this paper, we explore these two problems, showing that they have an
unbounded duality gap in general and analyzing their complexity. We prove that
ADP is NP-complete when k is part of the input and that SFP is
Sigma_2P-complete, even for acyclic graphs. Furthermore, we efficiently solve
ADP when k<=2 is fixed and present a polynomial time algorithm based on dynamic
programming for ADP when k is constant and the considered graphs are acyclic.
