  The Flow Decomposition problem, which asks for the smallest set of weighted
paths that "covers" a flow on a DAG, has recently been used as an important
computational step in transcript assembly. We prove the problem is in FPT when
parameterized by the number of paths by giving a practical linear fpt
algorithm. Further, we implement and engineer a Flow Decomposition solver based
on this algorithm, and evaluate its performance on RNA-sequence data.
Crucially, our solver finds exact solutions while achieving runtimes
competitive with a state-of-the-art heuristic. Finally, we contextualize our
design choices with two hardness results related to preprocessing and weight
recovery. Specifically, $k$-Flow Decomposition does not admit polynomial
kernels under standard complexity assumptions, and the related problem of
assigning (known) weights to a given set of paths is NP-hard.
