I need explanation about what exactly node-disjoint paths? and How to determine maximum number of node-disjoint path between two nodes Source(s) and Sink(t) in a directed graph. Can anyone explain with graphically.
A path is sequence of vertices: s, v_1, .., v_m, t. Two paths s, v_1, .., v_m, t and s, u_1, ..., u_k, t are called node-disjoint if v_i != u_j for any valid i and j.
We can reduce this problem to finding the maximum number of edge-disjoint paths by splitting each vertex (except for the source and the target) into two, adding an edge from the first copy to the second copy, redirecting all edges that end in this vertex to the first copy and all outgoing edges from the second copy. After that, the answer is the maximum flow in this graph (all edges should have a unit capacity).