Title: A Typing Theory for Flow Networks (Part I)
Author:Assaf Kfoury
Date: December 31, 2012
Abstract:
A flow network N is a capacited finite directed graph, with multiple
sources (or input arcs) and multiple sinks (or output arcs). A flow f
in N is feasible if it satisfies the usual flow-conservation condition
at every node and lower-bound/upper-bound capacity constraints at
every arc. We develop an algebraic theory of feasible flows in such
networks with several beneficial consequences.
We define and prove the correctness of an algorithm to infer, from a
given flow network N, an algebraic characterization T of all
assignments f of values to the input and output arcs of N that can be
extended to feasible flows g. We call such a characterization T a
principal typing for N, as there are other typings which are only
valid for N because they define subsets of all input-output
assignments f that can be extended to feasible flows g. A typing for N
turns out to define a bounded convex polyhedral set (or polytope) in
the n-dimensional vector space over real numbers where n is the total
number of input and output arcs in N. We then establish necessary and
sufficient conditions for an arbitrary typing to be a principal typing
for some flow network.
Based on these necessary and sufficient conditions, we define
operations on typings that preserve their principality (to be typings
for flow networks), and examine the implications for a typing theory
of flow networks. These also support a divide-and-conquer approach to
the design and analysis of flow-network algorithms.