k-splittable flow problem

Question

The maximum k-splittable s-t flow problem(MkSF) that aims to find a maximum k-splittable flow between a given source and sink node is NP-hard. We do not require the paths to be disjoint, not even different.

As a special case, just to be sure, is still computation of the k-splittable s-t flow in a directed network NP-hard if we consider only k disjoint paths?

Next, is it true if I say that for a directed network with finite number of nodes and arcs, the number of disjoint paths between two given nodes is still finite?

Answer 1

The answer of the the first part is yes; restricting the paths to be disjoint makes still the problem NP-hard.

Based on the Menger theorem, the number of disjoint paths between two given nodes is the minimum number of arcs whose removal makes the given nodes disconnected. This means that the number of disjoint paths between two nodes in a graph with polynomial number of nodes and arcs is finite.