% file:         u-flow2 
% author:       Tomomi MATSUI 
% organization: Math. Eng. #2 Lab. (Tomomi MATSUI)
% email:        tomomi@misojiro.t.u-tokyo.ac.jp
% title:        Is a Given Flow Uncontrollable?
% keywords:     network flow, NP-completeness
% language:     English

@techreport   {u-flow2,
    AUTHOR="T. Matsui",
    TITLE="Is a Given Flow Uncontrollable?",
    YEAR=1995,
    INSTITUTION="University of Tokyo",
    TYPE="to appear in IEICE Trans. Fundamentals"}

\begin{abstract}
An $s$-$t$ flow in a directed network is called ``uncontrollable'',
  when the flow is representable as a positive sum of
  elementary $s$-$t$ path flows.
In this paper,
  we discuss the problem ``Is a given flow uncontrollable?''.
We show that the problem is NP-complete.
\end{abstract}