Быстрые алгоритмы разложения потоков

Пусть задана направленная сеть с двумя источниками $s_1$, $s_2$, одним стоком $t$ и потоком $f$ в ней. Тогда несложно заметить, что $f$ можно разложить в сумму $f_1 + f_2$ двух потоков: первый из $s_1$ в $t$, а другой — из $s_2$ в $t$. Подобные разложения встречаются в качестве подзадачи в ряде алгоритмов комбинаторной оптимизации. Насколько быстро их можно построить?
Используя стандартный метод разложения потока на элементарные (вдоль простых путей и циклов) эту задачу можно найти за время $O(VE)$. Эта оценка, однако, далека от оптимальной. На докладе будут обсуждаться более быстрые алгоритмы, имеющие сложность, близкую к линейной. Все они основаны на известной из комбинаторики идее отщепления (splitting), позволяющей обратимым образом упростить граф сети.