On Min-Cut Algorithms for Half-Duplex Relay Networks

Computing the cut-set bound in half-duplex relay networks is a challenging optimization problem, since it requires finding the cut-set optimal half-duplex schedule. This subproblem in general involves an exponential number of variables, since the number of ways to assign each node to either transmitter or receiver mode is exponential in the number of nodes. We present a general technique that takes advantage of specific structures in the topology of a given network and allows us to reduce the complexity of computing the half-duplex schedule that maximizes the cut-set bound (with i.i.d. input distribution). In certain classes of network topologies, our approach yields polynomial time algorithms. We use simulations to show running time improvements over alternative methods and compare the performance of various half-duplex scheduling approaches in different SNR regimes.