The disjoint paths problem is defined as follows:
Input:
a graph $G = (V,E)$ (directed or not),
a graph $H = (T,D)$ (directed iff $G$ is directed), where $T \subseteq V$ is a set of terminals, $D$ is a set of commodities.
Output:
decide whether there is a family of paths $(P_h)_{h \in D}$ (directed if $G$ is directed), such that $P_{uv}$ is a $(v,u)$-paths, with the additional constraint that the paths must be disjoint.
There are two possibilities for how we consider that two paths are disjoint:
edge-disjoint (arc-disjoint for directed $G$): their edge sets are disjoint,
vertex-disjoint: their sets of inner vertices are disjoint (openly disjoint, we ignore the endpoints).
In the first case, when $G$ is directed, we call it the arc-disjoint paths problem, and the edge-disjoint paths problem when $G$ is not directed. In the second case, we just call it the vertex -disjoint paths problem.
The disjoint paths problem is known to be very hard: it is np-complete in directed graphs even if $k = 2$, and $\Omega(m^{\frac{1}{2} - \varepsilon})$-hard to approximate in general.
Edge and arc-disjoint paths problem can be generalized to the integer multicommodity flow problem. In this setting, we add capacities $c: E \to \mathbb{R}^+$ and requests $r_1,\ldots,r_k$. Then we want $r_i$ paths from $s_i$ to $t_i$, such that no edge $e$ is used by more than $c(e)$ paths. Note that the integer multicommodity flow is harder to solve than the disjoint paths problems: we can simulate capacities by replicating edges as many time as their capacities, but this reduction is not polynomial in general. In the tableau we distinguish the following cases:
binary (bin) stands for integer multicommodity flow problems. Capacities and requests are encoded in binary, taking logarithmic space. These instances cannot be simulated by edge-disjoint paths instances.
unary (un) stands for edge-disjoint paths problems or more generally integer multicommodity flows with capacity and request functions encoded in unary. With that encoding, replicating the edges does not blow up exponentially the size of an instance. It is often convenient to use small capacities in an edge-disjoint paths problem, but that can also be a source for confusion.
we also consider instances where the total request is fixed (fix), for instance, the problem of finding $k$ disjoint paths, where $k$ is not part of the input but a parameter. As a special case, consider the two-disjoint paths problem.
Notice that adding capacities on edges for the vertex-disjoint paths problem would not make sense. Instead, one could add capacities on vertices. By replicating vertices, capacities could be simulated in the same way unary capacities on edges are simulated in the edge-disjoint paths problem. However, this reduction does not preserve the topological properties of $G$ (we may lose the planarity of $G$ for instance). The present version of the tableau gives only the complexity of the uncapacitated version of vertex-disjoint paths problems.
In the tableau, we consider various cases. We use the following notations:
$|E(H)|$ can be:
arbitrary (arb), the number of commodities is not bounded.
fixed (fix), the number of commodities is bounded by a parameter of the problem.
2 , specializing the latter case to the simplest non-trivial possibiity.
$r$, the request function, can be:
encoded in binary (bin),
encoded in unary (un),
fixed (fix), that is $r(E(H)) \leq k$ for a fixed parameter $k$.
as a special case, $r(E(H)) = 2$, that is we are looking for two disjoint paths.
$G$ can be directed, directed acyclic, or undirected.
we distinguish the edge-disjoint or arc-disjoint cases (E-d) from the vertex-disjoint case (V-d).
in the edge (or arc)-disjoint case, we can impose the Eulerian condition on $G+H$ (Eul) or not (Gen). The Eulerian condition is that the in-capacity of a vertex is equal to its out-capacity in the directed case, or that the incident capacity is even in the undirected case. When counting the capacities for the Eulerian condition, we take into account $r+c$, and not just $c$.
