We consider s,t-flow problems in connected graphs with the
additional requirement that one can decompose the flow into at most
k paths for a given number k. Such flows are called k-splittable
flows. In the multi-commodity case they generalize unsplittable flows.
In this paper, we consider the problem MkSF, which means to
find a maximum k-splittable s,t-flow. We show complexity
and approximability results for this problem depending on k. Results work
for directed and undirected graphs. Firstly, we show that for all constant
integer k > 1 MkSF is strongly NP-hard and
cannot be approximated with a guarantee better than 5/6. This is
the first constant bound for the non-approximability of this problem. Secondly,
we study MkSF with k depending on m, the number of edges, and n,
the number of nodes of the graph. We prove that MkSF is NP-hard
for 2 <= k <= m-n+1. We show that it is polynomially solvable for
k >= m-n+2. Thus, there is no gap in the analysis. For the special case of
simple graphs we show that MkSF is polynomially solvable for k = m - c
for each integer constant c. That also holds for k=m-(log log p(m,n))^eps
for every polynom p in n and m, eps in (0,1).
It is well known that every flow in a graph can be decomposed into at most m
paths and cycles. We show as a general result that the number of paths in such
a decomposition can always be limited to m - n + 2.
