[IEEE Trans. on Information Theory, November 2006, pp. 5067-5077]
Nonreversibility and Equivalent Constructions of Multiple Unicast Networks
Randall Dougherty and Kenneth Zeger
Abstract
We prove that for any finite directed acyclic network,
there exists a corresponding multiple unicast network,
such that for every alphabet,
each network is solvable if and only if the other is solvable,
and, for every finite field alphabet,
each network is linearly solvable if and only if the other is linearly solvable.
The proof is constructive
and creates an extension of the original network by adding exactly
s + 5m(r-1) new nodes
where, in the original network,
m is the number of messages,
r is the average number of receiver nodes demanding each source message,
and s is the number of messages emitted by more than one source.
The construction is then used to create a solvable multiple unicast network which becomes
unsolvable over every alphabet size if all of its edge directions are reversed
and if the roles of source-receiver pairs are reversed.