The Approximate Capacity of Half-Duplex Line Networks

Yahya H. Ezzeldin, Martina Cardone, Christina Fragouli, Daniela Tuninetti

Research output: Contribution to journalArticlepeer-review


This paper investigates the problem of characterizing the capacity of Half-Duplex (HD) line networks, where a source node communicates to a destination node through a multi-hop path of N relays. If the relays operate in Full-Duplex (FD), it is well known that the capacity of the line network equals the minimum among the point-to-point link capacities in the path. In contrast, this paper considers a different case where the relays operate in HD. In the first part of the paper, it is shown that the approximate capacity (optimal up to a constant additive gap that only depends on the number of nodes in the network) of an HD N-relay line network equals half the minimum of the harmonic means of the point-to-point link capacities of each two consecutive links in the path. It is then proved that the N+1 listen/transmit states (out of the 2 N possible ones) sufficient to characterize the approximate capacity can be found in linear time. In the second part of the paper, it is shown that the problem of finding the path that has the largest HD approximate capacity in a network that can be represented as a graph is NP-hard. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomial-time algorithm can indeed be designed.

Original languageEnglish (US)
Article number9103123
Pages (from-to)4449-4467
Number of pages19
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 2020

Bibliographical note

Publisher Copyright:
© 1963-2012 IEEE.


  • Half-duplex (HD) line networks
  • NP-hardness
  • approximate capacity
  • efficient relays scheduling


Dive into the research topics of 'The Approximate Capacity of Half-Duplex Line Networks'. Together they form a unique fingerprint.

Cite this