  The problem of operating a Gaussian Half-Duplex (HD) relay network optimally
is challenging due to the exponential number of listen/transmit network states
that need to be considered. Recent results have shown that, for the class of
Gaussian HD networks with N relays, there always exists a simple schedule,
i.e., with at most N +1 active states, that is sufficient for approximate
(i.e., up to a constant gap) capacity characterization. This paper investigates
how to efficiently find such a simple schedule over line networks. Towards this
end, a polynomial-time algorithm is designed and proved to output a simple
schedule that achieves the approximate capacity. The key ingredient of the
algorithm is to leverage similarities between network states in HD and edge
coloring in a graph. It is also shown that the algorithm allows to derive a
closed-form expression for the approximate capacity of the Gaussian line
network that can be evaluated distributively and in linear time. Additionally,
it is shown using this closed-form that the problem of Half-Duplex routing is
NP-Hard.
