A long-standing open question in information theory is to characterize the
unicast capacity of a wireless relay network. The difficulty arises due to the
complex signal interactions induced in the network, since the wireless channel
inherently broadcasts the signals and there is interference among
transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear
deterministic model that takes into account the shared nature of wireless
channels, focusing on the signal interactions rather than the background noise.
They generalized the min-cut max-flow theorem for graphs to networks of
deterministic channels and proved that the capacity can be achieved using
information theoretical tools. They showed that the value of the minimum cut is
in this case the minimum rank of all the adjacency matrices describing
source-destination cuts.

In this paper, we develop a polynomial time algorithm that discovers the
relay encoding strategy to achieve the min-cut value in linear deterministic
(wireless) networks, for the case of a unicast connection. Our algorithm
crucially uses a notion of linear independence between channels to calculate
the capacity in polynomial time. Moreover, we can achieve the capacity by using
very simple one-symbol processing at the intermediate nodes, thereby
constructively yielding finite length strategies that achieve the unicast
capacity of the linear deterministic (wireless) relay network.