Efficiently Finding Simple Schedules in Gaussian
Half-Duplex Relay Line Networks

arXiv:1701.04426v2 [cs.IT] 21 Jun 2017

†

Yahya H. Ezzeldin† , Martina Cardone† , Christina Fragouli† , Daniela Tuninetti∗
UCLA, Los Angeles, CA 90095, USA, Email: {yahya.ezzeldin, martina.cardone, christina.fragouli}@ucla.edu
∗ University of Illinois at Chicago, Chicago, IL 60607, USA, Email: danielat@uic.edu

Abstract—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 polynomialtime 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 NPHard.

I. I NTRODUCTION
Computing the capacity of a wireless relay network is a
long-standing open problem. For Half-Duplex (HD) networks,
where the N relays cannot simultaneously transmit and receive, such problem is more challenging due to the 2N possible
listen/transmit configuration states that need to be considered.
Recently, in [1] the authors proved the conjecture posed in [2],
which states that simple schedules (i.e., with at most N + 1
active states) suffice for approximate (i.e., up to a constant
gap) capacity characterization. This result is promising as it
implies that the network can be operated close to its capacity
with a limited number of state switches. However, to the best
of our knowledge, it is not clear yet if such simple schedules
can be found efficiently.
The main result of this work is an algorithm design that
allows to compute a simple schedule that achieves the approximate capacity of the N -relay Gaussian HD line network
with complexity O(N 2 ). The algorithm leverages similarities
between network states in HD and edge coloring in a graph,
by associating different colors to links that cannot be activated
simultaneously. In addition, the algorithm allows to derive the
approximate capacity of the Gaussian HD line network in
closed form. This expression has two appealing features: (i) it
can be evaluated in linear time and (ii) it can be distributively
computed among the N relays. The novelty and applicability
of the results presented in this paper are two-fold: (i) they
shed light on how to operate a class of Gaussian HD relay
networks close to the capacity with the minimum number of
state switches and (ii) they represent the first approximate

capacity characterization in closed form for a class of Gaussian
HD relay networks with general number of relays.
Related Work. The capacity of the N -relay Gaussian HD
network is not known in general. Recent results in [3], [4]
showed that the capacity can be approximated to within
a constant gap by the cut-set upper bound evaluated with
independent inputs and a schedule, which is independent of
the transmitted and received signals. In the rest of the paper,
we refer to this bound as the approximate capacity. To the
best of our knowledge, the tightest known gap for Gaussian
HD relay networks is of 1.96(N + 2) bits per channel use,
independently of the channel parameters [5].
In general, the evaluation of the approximate capacity is cast
as an optimization problem over 2N listen/transmit states. As
N increases, this evaluation, as well as determining an optimal
schedule of listen/transmit states, become computationally
expensive. The authors in [6] designed an iterative algorithm to
determine an approximately optimal schedule when the relays
use decode-and-forward. In [7], the authors proposed a ‘grouping’ technique to address the complexity of the aforementioned
optimization problem. This technique allows to compute the
approximate capacity in polynomial-time for certain classes of
Gaussian HD relay networks that include the line network as
special case. While the results in [6] and [7] show that the
approximate capacity can be efficiently obtained for special
network topologies by solving a linear program, it is not clear
how to construct (in polynomial time) a schedule that achieves
the approximate capacity. Differently, in this work we design
a polynomial-time algorithm that outputs a simple schedule,
which achieves the approximate capacity of Gaussian HD line
networks and allows to compute this quantity in closed form.
Paper Organization. Section II describes the N -relay Gaussian HD line network and presents known capacity results.
Section III discusses our main results and their implications.
Section IV simplifies the approximate capacity expression for
Gaussian HD line networks. Section V designs an algorithm
for finding a simple schedule for a Gaussian HD line network
that achieves the approximate capacity. Section VI concludes
the paper. Some of the proofs are delegated to the Appendix.
Particularly, Appendix E proves that the problem of find the
best Half-Duplex route in a network is NP-Hard.
II. S YSTEM M ODEL
We consider the N -relay Gaussian HD line network L
where a source node (node 0) wishes to communicate to

a destination node (node N + 1) through a route of N
relays where each relay is operating in HD. The input/output
relationship for the line network L is
Yi = (1 − Si ) hi,i−1 Xi−1 Si−1 + Zi , ∀i ∈ [1 : N + 1], (1)
where: (i) Xi (respectively, Yi ) denotes the channel input
(respectively, output) at the i-th node; (ii) Si is the binary
random variable which represents the state of node i, i.e.,
if Si = 0 then node i is receiving, while if Si = 1 then
node i is transmitting; notice that S0 = 1 (i.e., the source
always transmits) and SN +1 = 0 (i.e., the destination always
receives); (iii) Zi indicates the additive white Gaussian noise
at node i, where the noises are assumed to be independent
and identically distributed as CN (0, 1); (iv) hi,j denotes the
complex channel coefficient from node j to node i and
hi,j = 0 whenever j 6= i − 1; the channel gains are assumed
to be constant for the whole transmission duration and hence
known to all nodes; (v) the channel inputs satisfy an average
power constraint E[|Xi |2 ] ≤ 1, ∀i ∈ [0 : N ]. We denote the
point-to-point link capacity from node i − 1 to node i with

`i = log 1 + |hi,i−1 |2 , ∀i ∈ [1 : N + 1].
The capacity of the Gaussian HD line network L described
in (1) can be approximated to within a constant gap G =
O(N ) [3], [4], [8], [9]1
X
X
CL = max min
λs
`i , (2)
λ∈Λ A⊆[1:N ]

s∈[0:1]N

i∈{N +1}∪{Rs ∩A}
i−1∈{0}∪{Ts ∩Ac }
N

where: (i) the schedule λ ∈ R2 determines the fraction of
time the network operates in each of the states s ∈ [0:1]N ,
i.e., λs = Pr (Si = si , ∀i ∈ [1 : N ]); (ii) Λ = {λ : λ ∈
N
R2 , λ ≥ 0, kλk1 = 1} is the set of all possible schedules;
(iii) Rs (respectively, Ts ) represents the set of indices of
relays receiving (respectively, transmitting) in the relaying
state s ∈ [0:1]N ; (iv) Ac = [1:N ]\A.
We can equivalently write the expression in (2) as
X
X
CL = max min
λs
`0i,s ,
(3)
λ∈Λ A⊆[1:N ]

where

`0i,s =

(
`i,
0,

s∈[0:1]N

i∈{N +1}∪A
i−1∈{0}∪Ac

if i ∈ Rs ∪{N +1} and i−1 ∈ Ts ∪ {0}
(4)
otherwise.

Similarly, we denote with CλL , the HD rate achieved by the
line network L when operated with the fixed schedule λ, i.e.,
X
X
CλL = min
λs
`0i,s .
(5)
A⊆[1:N ]

s∈[0:1]N

i∈{N +1}∪A
i−1∈{0}∪Ac

Note that for all possible schedules λ, CλL ≤ CL .
Definition 1. We say that a schedule λ is simple if the number
of active states (i.e., states s such that λs 6= 0) is less than or
equal to N + 1. In other words, we have kλk0 ≤ N + 1.
1 In

[9], it was observed that information can be conveyed by randomly
switching the relay between transmit and receive modes. However, this only
improves the capacity by a constant, at most 1 bit per relay.

III. M AIN R ESULTS AND D ISCUSSION
Our main result, stated in the theorem below, is two-fold: (i)
it designs a polynomial-time algorithm that outputs a simple
schedule optimal for approximate capacity and (ii) it provides
a closed-form expression for the approximate capacity of the
HD line network that can be evaluated in linear time.
Theorem 1. For the N -relay Gaussian HD line network L
described in (1), a simple schedule optimal for approximate
capacity can be obtained in O(N 2 ) time and the approximate
capacity CL in (3) is given by


`i `i+1
.
(6)
CL = min
i∈[1:N ] `i + `i+1
Converse. It is not hard to argue that the right-hand side of (6)
is an upper bound on CL . This can be seen by assuming that,
for a given i ∈ [1 : N ], node i − 1 perfectly cooperates with
node 0 and similarly node i+1 perfectly cooperates with node
N + 1. Clearly, the capacity of this new line network is an
upper bound on CL and it has an approximate capacity equal
`i+1
. Since this is true for all i ∈ [1 : N ], then CL is
to ``i i+`
i+1
less than or equal to the right-hand side of (6). The heart of
the proof is thus to prove the achievability of (6).
Before we delve into the proof of the achievability in
Theorem 1, we highlight the following remarks to motivate
the need to search for a simple schedule for the line network.
Remark 1. Are two active states sufficient for approximate
capacity characterization? Consider a line network with one
relay. For this network, the schedule that achieves the approximate capacity has only two active states, which activate the
links alternatively. Intuitively, one might think that this would
extend to general number of relays. For example, for a network
with N = 3, can we achieve the approximate capacity by only
considering the listen/transmit states s1 = 010, s2 = 101?
Surprisingly, the answer to this question is negative as we
illustrate through the following example with N = 3 and
`1 = 2R, `2 = 2R, `3 = 3R, `4 = R,

(7)

where R > 0. By considering only the two aforementioned
states, we can achieve a rate of 2/3R. However, in Section V,
we consider this network as our running example and show
that using N + 1 = 4 states, we can achieve 3/4R.
Remark 2. Can we a priori limit our search over a
polynomial number of states? For the Full-Duplex (FD) line
network, we can a priori limit our search for the minimum cut
over N + 1 cuts (instead of 2N ). This reduction in the number
of cuts is also possible for the HD line network as we prove
in the next section. This fact raises the question whether we
can also a priori reduce the search space for the active states
to a polynomial set (instead of 2N ). This is not possible as we
state in the theorem below, which is proved in Appendix B.
Theorem 2. With only the knowledge that relays are arranged
in a line, the cardinality of the smallest search space of states
over which a schedule optimal for approximate capacity can
be found is Ω(2N/3 ).

Remark 3. Theorem 1 has two appealing consequences:
1) The capacity of the line network with N relays can
be computed in linear time in N . This improves on the
result in [7], where the approximate capacity can be found in
polynomial time (but not linear in the worst case) by solving
a linear program with O(N ) variables.
2) The approximate capacity in Theorem 1 can be computed
in a distributive way as follows. Each relay i ∈ [1 : N ]
computes the quantity


`i `i+1
, mi−1 ,
mi = min
`i + `i+1
where m0 = ∞, and sends it to relay i + 1. With this, at
the end we have mN = CL . In other words, for approximate
capacity computation, it is only required that each relay knows
the capacity of the incoming and outcoming links.
IV. F UNDAMENTAL C UTS IN HD L INE N ETWORKS
In this section, we prove that in a Gaussian HD line network,
we can compute the approximate capacity CL in (3) by
considering only N + 1 cuts, which are the same that one
would need to consider if the network was operating in FD.
For the Gaussian line network L, when all the N relays
operate in FD, the FD capacity is given by
X
CFD
`i = min {`i } ,
(8)
L = min
A⊆[1:N ]

i∈[1:N +1]

i∈{N +1}∪A,
i−1∈{0}∪Ac

that is, without explicit knowledge of the values of `i or
their ordering, the number of cuts over which we need to
optimize (see CFD
L in (8)) is N + 1. We refer to these cuts as
fundamental. Let F denote the set of these fundamental cuts
(which are of the form A = [i : N ], i ∈ [1 : N ] or A = ∅),
then for any cut A of the network, there exists a fundamental
cut F (A) ∈ F such that:
X
X
`i ≤
`i .
(9)
i∈{N +1}∪F (A),
i−1∈{0}∪F (A)c

i∈{N +1}∪A,
i−1∈{0}∪Ac

Furthermore, the function F (·) does not depend on the values
of `i . We next prove that the fundamental cuts in HD equal
those in (8) for FD. Consider a fixed schedule λ. Then, by
using (9) for the inner summation in (5), for each s ∈ [0 : 1]N
we have
X
X
`0i,s ≤
`0i,s .
i∈{N +1}∪F (A),
i−1∈{0}∪F (A)c

i∈{N +1}∪A,
i−1∈{0}∪Ac

Thus, we can simplify (5) as
X
CλL = min
λs
A⊆[1:N ]

X

= min

A∈F

s∈[0:1]N

X

`0i,s
`0i,s

i∈{N +1}∪A
i−1∈{0}∪Ac

!
=

min
i∈[1:N +1]

X
s∈Si

λs

`i ,

Si ={s ∈ [0 : 1]N |i ∈ {N + 1} ∪ Rs , i − 1 ∈ {0} ∪ Ts }.
The set Si ⊆ [0 : 1]N represents the collection of states that
activate the i-th link. For illustration consider a network with
N = 3. We have
S1 = {000, 001, 010, 011}, S2 = {100, 101},
S3 = {010, 110},

(10)

S4 = {001, 011, 101, 111}.

Using the same arguments as in (10), we can similarly simplify
the expression of CL in (3). Thus, the result presented in this
section explicitly provides the N + 1 cuts (out of the 2N
possible ones) over which it is sufficient to minimize in order
to obtain CL in (3).
V. F INDING A S IMPLE S CHEDULE O PTIMAL FOR
A PPROXIMATE C APACITY
In this section, we design a polynomial-time algorithm
that finds a simple schedule, which achieves the approximate
capacity of the N -relay Gaussian HD line network. The
algorithm leverages similarities between network states in
HD and edge coloring in a graph. In particular, an edge
coloring assigns colors to edges in a graph such that no two
adjacent edges are colored with the same color. Similarly in
HD, a network state cannot be a receiver and a transmitter
simultaneously. Thus, if we assign one color to all activated
links (viewed as edges) in a network state, this does not violate
the rules of edge coloring in a graph. In what follows, we
first explain how the algorithm makes use of these similarities
assuming that the link capacities `i are all integers and later
in the section, we show how the algorithm extends to rational
and real values of `i .
A. An Algorithm for Networks with Integer Link Capacities
We highlight the algorithm procedure in the following main
steps and provide intuitions for each step. As a running
example to illustrate the different steps we consider the line
network L with N = 3 relays described in (7) with R = 1.
Step 1. Let M be a common multiple of the link capacities
`i . For the line network L we construct an associated graph
GL where: (i) the set of nodes is the same as in the network
L and (ii) each link with capacity `i in L is replaced by ni
parallel edges, where
ni =

i∈{N +1}∪A
i−1∈{0}∪Ac

λs

s∈[0:1]N

X

where

M
,
`i

∀i ∈ [1 : N + 1].

(11)

Clearly, computing M and ni requires O(N ) operations. The
main motivation behind this step is that from (10), it is not
difficult to see that a good schedule would try to assign more
weights λs to a link with a smaller capacity. Hence, if we
treat edge colors as equally weighted, a link with a smaller
capacity should get more colors. Thus, the main idea above is
to assign ni adjacent edges inversely proportional to `i .
Running Example. We have
M = 6 and n1 = 3, n2 = 3, n3 = 2, n4 = 6.

Step 2. In this step, our goal is to edge color the graph GL . By
noting that GL is a bipartite graph, we know that an optimal
coloring can be performed with ∆ colors, where ∆ is the
maximum node degree and is equal to
∆ = max {ni + ni+1 } .
i∈[1:N ]

(12)

In particular, we define our coloring by the interval of colors
Ci ⊂ [1 : ∆] that are assigned to the ni edges that connect
node i−1 to node i such that |Ci | = ni . Specifically, we assign
Ci for i ∈ [1 : N +1] as
(
[1 : ni ],
i even
Ci =
(13)
[∆−ni +1 : ∆], i odd.

by rows of Λ. The algorithm finally outputs the variables Λ
and w. The complexity of steps 2 and 3 is O(N 2 ).
Running example. Algorithm 1 outputs
I1 = [7 : 8],

Λ(1, :) = 010,

w(1) = 2/8,

I2 = [6 : 6],

Λ(2, :) = 001,

w(2) = 1/8,

I3 = [4 : 5],

Λ(3, :) = 111,

w(3) = 2/8,

I4 = [1 : 3],

Λ(4, :) = 101,

w(4) = 3/8.

Finally, we note that since pu has at most N + 2 terms, then
the number of states output by the algorithm is at most N + 1,
i.e., the schedule is simple as also stated in Theorem 1.
Algorithm 1 Grouping Edge Colors
(`)

The complexity of this step is O(N ), since for each i ∈ [1 :
N + 1] we only compute two numbers that define the interval
(`)
(r)
Ci , that is the two limit points Ci and Ci of the interval,
(`)
(r)
i.e., Ci = [Ci : Ci ].
Running example. Since we have ∆ = 8, then the assigned
color intervals are
C1 = [6 : 8], C2 = [1 : 3], C3 = [7 : 8], C4 = [1 : 6].
Step 3. From the previous step, we have ∆ colors each of
which corresponds to a network state running for 1/∆ fraction
of time. However, some of these colors can represent the same
operation states. For instance, in our running example, the
colors 7 and 8 appear in both C1 and C3 (and nowhere else).
Therefore, we can group the time fractions of colors 7 and
8 together, since they operate the network in the same way.
To perform this color grouping, we run an iterative algorithm
over the color intervals Ci , i ∈ [1 : N + 1] constructed in the
previous step, which outputs a schedule for the network. The
algorithm pseudocode is shown in Algorithm 1 and can be
summarized as follows:
1) We first find a descendingly ordered set of colors pu at
which the network state changes. The network state changes
whenever an interval Ci begins or ends. Therefore in this step,
we sort the unique elements of an array p that contains the
(`)
(r)
Ci and Ci + 1 for all i ∈ [1 : N + 1]. Since there are N + 1
different Ci then this operation takes O(N log N ) time. At this
(r)
point, it is worth noting that for odd i, we have Ci = ∆ while
(`)
for even i, we have Ci = 1. Thus, the descendingly ordered
array pu has at most N + 2 unique elements.
Running example. We have pu = {9, 7, 6, 4, 1}.
2) Next, we go through the array pu to construct the group of
colors Ij . Each set Ij represents a network state and all colors
in a set Ij operate the network in the same way. To do this
(`)
(r)
we compute the endpoints Ij , Ij for each Ij . The fraction
of time the network operates in the state represented by Ij is
stored in the vector w and is calculated as |Ij |/∆.
3) For each Ij constructed, the algorithm performs a loop of
N iterations in order to determine the state of each node in
this particular network configuration state and records this in
a row of the matrix Λ. Thus, the active states are represented

(r)

Input N, ∆, (Ci , Ci ), ∀i ∈ [1 : N + 1]
Output Λ, w
for each i ∈ [1 : N + 1] do
(`)
(r)
p(i) ← Ci , p(i+N +1) ← Ci + 1
pu ← U niqueDescSort(p)
for each j ∈ [1 : length(pu ) − 1] do
(r)
(`)
Ij ← pu (j) − 1, Ij ← pu (j + 1)
(r)
(`)
w(j) ← (Ij − Ij + 1)/∆, state ← 1
for each i ∈ [1 : N + 1] do
(`)
(r)
if [Ij : Ij ] ⊆ Ci then
state ← 0
if i < N + 1 then Λ(j, i) ← 0
if i > 1 then Λ(j, i − 1) ← 1
else if i < N + 1 then
Λ(j, i) ← state
B. Rate Achieved by the Schedule
In the previous subsection we developed an algorithm that
outputs a simple schedule for the N -relay Gaussian HD line
network L. We now derive the rate that the constructed schedule achieves. Let λ be the schedule output by Algorithm 1,
then we have the following relation ∀i ∈ [1 : N + 1]
X
X
X |Ij |
ni
λs =
w(j) =
= ,
(14)
∆
∆
s∈Si

j∈[1:K],
Λ(j,:)∈Si

j∈[1:K],
Λ(j,:)∈Si

where K is the number of network configuration states output
by Algorithm 1 and Si is the set of states which make the link
of capacity `i active and is defined in (10). From (10), (11)
and (14), we can simplify the achievable rate CλL as
!
X
ni (11) M
(14)
CλL = min
λs `i = min
`i =
. (15)
∆
i∈[1:N +1]
i∈[1:N +1] ∆
s∈Si

From the definition of maximum degree ∆ in (12), we obtain


∆
1
1
1
=
max {ni + ni+1 } = max
+
. (16)
M
M i∈[1:N ]
`i+1
i∈[1:N ] `i
Finally, by substituting (16) into (15) we obtain that the simple
schedule λ constructed from our proposed polynomial-time
algorithm achieves the right-hand side of (6). This concludes
the proof of Theorem 1 when the link capacities are integers.

C. Extension to Real Link Valued Capacities
The extension of the algorithm in Section V-A to networks
with rational link capacities is straightforward, by simply
multiplying each of the link capacities with a common multiple
of the denominators. In this subsection, we focus on how the
algorithm can be used to find a schedule for the line network
L with real link capacities such that the rate achieved by this
schedule is at most a constant gap ε away from CL .
For a fixed ε > 0, let Lq,ε be a line network with rational
link capacities qi such that
∀i ∈ [1 : N + 1],

qi ∈ Q, `i − ε ≤ qi ≤ `i .

(17)

Such Lq,ε always exists (but it is not unique) since the set
of rationals Q is dense in R. We now relate CLq,ε and CL by
appealing to the lemma below, which we prove in Appendix A.
Lemma 3. Let L be a line network with real link capacities
`i , then ∀ε > 0, we have
?q

CLq,ε ≤ CλL

≤ CL ≤ CLq,ε + ε,

(18)

where the line network Lq,ε is constructed as in (17) and λ?q
is an optimal schedule of the line network Lq,ε .
The result in Lemma 3 has the following implications:
1) The statement of Lemma 3 directly implies that
?q
CL − CλL
≤ ε. Since this holds for all ε > 0, then
we can use the algorithm in Section V-A on Lq,ε to get
?q
a simple schedule λ?q,ε that achieves a rate CλL that is
at most ε away from CL .
2) From Lemma 3, we have that


lim CLq,ε ≤ CL ≤ lim CLq,ε + ε .
ε→0

ε→0

Additionally, from Section V-B, we know that for the
network Lq,ε with rational link capacities qi , we have


qj qj+1
lim CLq,ε = lim min
ε→0
ε→0 j∈[1:N ] qj + qj+1


`j `j+1
= min
.
j∈[1:N ] `j + `j+1
These two observations imply that, for any line network
L with real link capacities, we have


`j `j+1
CL = min
.
j∈[1:N ] `j + `j+1
This concludes the proof of Theorem 1 for real link capacities.
VI. C ONCLUSION
In this work we developed a polynomial-time algorithm for
finding a simple schedule (one with at most N + 1 active
states) that achieves the approximate capacity of the N -relay
Gaussian HD line network. We characterized the rate achieved
by the constructed schedule in closed form, hence providing
a closed-form expression for the approximate capacity of the
Gaussian HD line network. To the best of our knowledge,
this is the first work which provides a closed-form expression
for the approximate capacity of an HD relay network with
general number of relays and designs an efficient algorithm to
find simple schedules which achieve it.

A PPENDIX A
P ROOF OF L EMMA 3
The second inequality in (18) is straightforward from the
definition of CL . Therefore, we need to prove the first and third
inequalities. To prove the first inequality note that, from (10),
we can upperbound CLq,ε as
!
X
?q
CLq,ε = min
λs qi
i∈[1:N +1]

s∈Si

!

(a)

≤

min
i∈[1:N +1]

X

?q

λ?q
s

`i = CλL ,

s∈Si

where the inequality in (a) follows since, from the construction
in (17), ∀i ∈ [1 : N + 1], we have qi ≤ `i . This proves the
first inequality. To prove the third inequality, we use the fact
that, from the construction in (17), ∀i ∈ [1 : N + 1], we have
qi ≥ `i − ε. This implies that for any schedule λ, we have
"
! #
X
λ
λs `i − ε
CL − ε =
min
i∈[1:N +1]

≤

s∈Si

!

(a)

min
i∈[1:N +1]

X

λs

(`i − ε)

s∈Si

!
≤

min
i∈[1:N +1]

X

λs

qi = CλLq,ε ,

(19)

s∈Si

P
where the inequality in (a) follows since s∈Si λs ≤ 1. By
letting λ = λ? , with λ? being an optimal schedule for L, we
?
have CL −ε ≤ CλLq,ε ≤ CLq,ε , which proves the third inequality.
A PPENDIX B
P ROOF OF T HEOREM 2
In this section, we prove the result in Theorem 2 by proving
the following relations in the following subsections.
1) We first prove that the set of fundamental 2 states in
a Gaussian HD line network is equivalent to the set
of fundamental maximum cuts in a Gaussian FD line
network.
2) We next show that the problem of finding the set of
fundamental maximum cuts for an N -relay Gaussian
FD line network is equivalent to the problem of finding
subsets of non-consecutive integers in [1 : N ].
3) Finally, we show that the number of subsets of nonconsecutive integers in [1 : N ] is exponential in N .
A. Set of Fundamental Maximum Cuts
In Section IV we proved that we can compute the approximate capacity CL in (3) by considering only N +1 cuts, which
are the same that one would need to consider if the network
2 When states or cuts are referred to as fundamental of a certain type (e.g.,
maximum, minimum), we mean that they form the smallest set of that type
that only depends on the network topology (i.e., relays are arranged in a line)
and is independent of the actual values of the point-to-point link capacities.

was operating in FD. This implies that we can write (3) as the
linear program (LP)
CL =

maximize x
subject to 1N +1 x ≤ Aλ
and
1T2N λ = 1, λ ≥ 02N , x ≥ 0,
N

where A ∈ R(N +1)×2

(20a)

where
o
n
MA = i ∈ [1:N +1] i ∈ A ∪ {N +1}, i − 1 ∈ Ac ∪ {0} .

has non-negative entries
[A]i,j =

`0i,j ,

(20b)

where: (i) i ∈ [1 : N + 1], j ∈ [1 : 2N ]; (ii) `0i,j is defined
in (4). Clearly, the LP in (20) is feasible. The dual of the LP
in (20) is given by
CL =

minimize y
subject to 12N y ≥ AT v
and
1TN +1 v ≥ 1, v ≥ 0N +1 ,

(21)

where A is defined in (20b). Since the LP in (21) is a
minimization and the entries of A are non-negative, then it
is not hard to see that for all optimal solutions of (21), we
have 1TN +1 v = 1. As a result, an optimal solution of (21) is
a solution of
CL =

the unique optimal schedule, i.e., λsAc = 1. For an arbitrary
A ∈ FM , define the network with the link capacities

1 if i ∈ MA
`i =
,
∞ otherwise

minimize y
subject to 12N y ≥ AT v
and
1TN +1 v = 1, v ≥ 0N +1 .

From the aforementioned network construction, it is not hard
to see that the unique optimal schedule (one for which
CL = CLFD ) is sAc = 1Ac , i.e., λsAc = 1. Therefore, for
this particular network construction, the state sAc is necessary
and hence we cannot further reduce the sufficient set to a
subset of FM , i.e., we need to consider the network states
corresponding to every element of FM .
This result implies that, to find the smallest set of states
over which we should search for an optimal schedule for
approximate capacity, we should find the set of maximum
cuts in FD and then consider their dual multipliers in (20).
In what follows, we focus on estimating the cardinality of the
set of fundamental maximum cuts FM in a FD Gaussian line
network, which, as shown above, gives the cardinality of the
smallest search space for an optimal schedule.
B. Finding the Set of Possible Maximum Cuts through an
Equivalent Problem

(22)

We start by introducing some definitions, which will be
extensively used in the rest of this section.

Since in the LP in (21) we are seeking to minimize the
objective function, this implies that at least one of the constraints of the type 12N y ≥ AT v (i.e., the maximum) is
satisfied with equality. We can interpret (22) as the problem
of finding the least maximum FD cut among a class of line
networks LV derived from the original network L, where
V = {v ∈ RN +1 | v ≥ 0, kvk1 = 1}. For each v ∈ V,
we define a line network Lv ∈ LV , where the capacities are
(v)
modified by v as `i = `i vi .
Let FM be the fundamental set of maximum cuts in a
FD line network, i.e., the smallest set of cuts over which we
need to search for the maximum cut in FD without explicit
knowledge of the values of the link capacities or their ordering.
It is clear from definition of FM that it is also sufficient to
find the least maximum FD cut among the class of Gaussian
line networks LV . With this, the rows of AT (constraints
in (22)) corresponding to FM are sufficient to find an optimal
solution in (22). As a consequence of strong duality, the
dual multipliers (the states λs in (20)) corresponding to the
fundamental maximum cuts in FM are also sufficient to find
a schedule optimal for approximate capacity. We now prove
that, without any knowledge of the link capacities, we need
to consider the network states associated to every element of
FM , i.e., considering only the network states corresponding
to a subset of FM is not sufficient to achieve the approximate
capacity. To prove that, it suffices to provide a network
example, where for each A ∈ FM the state scA = 1Ac is

Definition. For a set of consecutive integers [a:b], we call H a
“punctured” subset of [a:b] if ∀i, j ∈ H with i 6= j, we have
|i−j|>1, i.e., H contains no consecutive integers of [a:b].
Definition. We call H a “primitive punctured” subset of [a : b]
if H is a punctured subset of [a : b] and ∀i ∈ [a : b]\H,
H ∪ {i} is not a punctured set, i.e., H is not a subset of any
other punctured subset of [a : b]. We denote by P(a, b) the
collection of all primitive punctured subsets of [a : b].
We now use the two above definitions to state the following
lemma, which is proved in the rest of this section.
Lemma 4. The problem of finding the set of possible maximum
cuts for a Gaussian FD line network is equivalent to the
problem of finding P(1, N +1), i.e., the collection of primitive
punctured subsets of [1 : N + 1].
Proof. We start by defining two problems, namely P1 and P2 ,
which are important for the rest of the proof:
X
P1 :
max g1 (A) =
`i ,
(23a)
A⊆[1:N ]

P2 :

max

B⊆[1:N +1]
B is punctured

i∈A∪{N +1}
i−1∈Ac ∪{0}

g2 (B) =

X

`i .

(23b)

i∈B

Note that P1 is the problem of finding the maximum FD cut
in an N -relay Gaussian line network. To relate the solutions
of P1 and P2 , we make use of the following definition.

Definition. Given a problem P, we denote with suf(P) the
smallest set of feasible solutions among which an optimal
solution can be found for any instance of the problem.
The proof is organized as follows:
1) Step 1: We prove that P1 and P2 are equivalent;
as a consequence, there exists a function f such that
suf (P1 ) = f (suf (P2 )).
2) Step 2: Next we prove that suf (P2 ) ⊆ P(1, N + 1),
which implies that
suf (P1 ) ⊆ f (P(1, N + 1)) .
3) Step 3: The previous step implies that the set M of
possible maximum cuts is a subset of f (P(1, N + 1)).
We finally prove that M = f (P(1, N + 1)).
Once proved, these steps imply that we can map the problem
of finding the set of possible maximum cuts for a Gaussian
FD line network to the problem of finding P(1, N + 1). We
prove these three steps in Appendix C.
Example. Consider the Gaussian FD line network with N =
7. To find the set of possible maximum cuts, according to
Lemma 4, we need to find the primitive punctured subsets of
[1 : 8]. This turns out to be:
n
P(1, 8) = {1, 4, 7}, {2, 4, 7}, {2, 5, 7}, {2, 5, 8}, {1, 3, 5, 7},
o
{1, 3, 6, 8}, {1, 4, 6, 8}, {2, 4, 6, 8}, {1, 3, 5, 8} .
It turns out that we can retrieve the candidate maximum cuts
Ai from P(1, 8) as follows:
Ai = Hi \{8}, Hi ∈ P(1, 8),

∀i ∈ [1 : |P(1, 8)|] .

To conclude the proof of Theorem 2, we need to understand
how the size of P(1, N + 1) grows with N , which is the goal
of the following subsection.
C. The Size of the Collection of Primitive Punctured Subsets
In this subsection, we prove that the size of the collection of
primitive punctured subsets of [1 : N + 1] grows exponentially
in N . In particular, we prove the following lemma.
Lemma 5. Let T (N ) be the number of primitive punctured
subsets of [1 : N ]. Then, we have the following relation,
T (N ) = T (N − 2) + T (N − 3).
The proof of the above lemma can be found in Appendix D.
Remark 4. The result in Lemma 5 suggests that T (N ) grows
exponentially fast. This can be proven as follows:
T (N ) = T (N − 2) + T (N − 3)
≥ 2 T (N − 3) ≥ 2k T (N − 3k)
≥

T (1)
2

N/3

2

,

∀N ≥ 4.

This implies that T (N ) = Ω(2N/3 ).
Since the number of candidate active states is equal to the
number of candidate maximum cuts in FD (see the discussion

in Appendix B-A) and this is equal to the number of primitive
punctured subsets of [1 : N + 1] (see Lemma 4), then the
N
number of candidate active states grows as Ω(2 3 ). This
concludes the proof of Theorem 2.
Remark 5. Using the recurrence relation in Lemma 5, it is
not hard to prove that in fact T (N ) = Θ(β N ) where β is the
unique real root of the polynomial x3 − x − 1 = 0.
A PPENDIX C
P ROOF OF L EMMA 4
We here prove each of the three steps in the proof of Lemma 4.
Step 1: We first start by proving that any feasible solution for
P1 can be transformed into a feasible solution for P2 with the
same value for the objective function. i.e., ∀A ∈ [1 : N ],
∃ punctured BA ∈ [1 : N + 1], s.t. g1 (A) = g2 (BA ).
To show this, for A ⊆ [1 : N ], we simply define BA as
o
n
BA = i ∈ [1:N +1] i ∈ A ∪ {N +1}, i−1 ∈ Ac ∪ {0} .
(24)
It is clear that BA is a punctured set as ∀i ∈ BA , i − 1 ∈
/ BA .
Additionally, (24) directly gives us the desired relation as
X
X
g1 (A) =
`i =
`i = g2 (BA ).
(25)
i∈BA

i∈A∪{N +1}
i−1∈Ac ∪{0}

What remains to prove now is that any feasible solution B for
P2 gives a feasible solution AB for P1 and g1 (AB ) = g2 (B).
For a punctured subset B of [1 : N + 1], let
n
o
AB = fAB (B) = i ∈ [1 : N ] i > sup(B) ∪ B\{N + 1} .
{z
}
{z
} |
|
Atail

Amain

(26)
It is not hard to see that by applying the transformation in (24)
on AB , we get back B, i.e., BAB = B. This is due to the
fact that applying (24) removes Atail which is composed of a
consecutive number of integers while keeping Amain which,
since B is punctured, is also punctured. Given this, we can
directly see from (25) that g1 (AB ) = g2 (BAB ) = g2 (B). This
concludes the proof of Step 1.
Step 2: We prove this step by showing that, if there exists an
optimal solution B ? of P2 that is not primitive, then there also
exists a primitive punctured set B 0 such that g2 (B ? ) = g2 (B 0 ).
Since B ? is not a primitive punctured set, then there exists
another punctured set B 0 such that B ? ⊂ B 0 and
X
X
g2 (B ? ) =
`i ≤
`i = g2 (B 0 ).
i∈B?

i∈B0

If we take the largest such B 0 we end up with a primitive
punctured set. However, by definition (i.e., since B ? is an
optimal solution) we have that ∀B punctured, g2 (B) ≤ g2 (B ? ).
This shows that g2 (B ? ) = g2 (B 0 ) and therefore, suf (P2 ) ⊆
P(1, N + 1). This concludes the proof of Step 2.

Step 3: In the first two steps, we proved that P1 and P2
are equivalent and that suf (P2 ) ⊆ P(1, N + 1). This implies
that suf (P1 ) ⊆ fAB (P(1, N + 1)), where fAB (·) is defined
in (26). We here prove that suf (P1 ) = fAB (P(1, N + 1)).
Consider an arbitrary set A ∈ fAB (P(1, N + 1)). To prove
that A ∈ suf (P1 ), it suffices to provide a network (an instance
of P1 ) for which A is the unique maximizer of P1 . Towards
this end, for the selected A, we define BA as in (24). We know
that BA is a primitive punctured set and g1 (A) = g2 (BA ).
Now consider the network with link capacities

1 if i ∈ BA
`i =
.
0 otherwise
For this network, it is not hard to see that g2 (B) = |B ∩ BA |,
for any punctured set B. We now want to show that ∀A0 ∈
fAB (P(1, N + 1)) \A, we have g1 (A0 ) < g1 (A). Let BA0 be
defined as in (24). Again, from the proof of the previous steps
the set BA0 is primitive punctured and g1 (A0 ) = g2 (BA0 ).
Moreover, since BA0 and BA are both primitive we have that
BA0 ∩ BA ⊂ BA . Thus, we obtain
g2 (BA0 ) =|BA0 ∩ BA | < |BA | = g2 (BA )
=⇒ g1 (A0 ) < g1 (A).
Since this is true for any arbitrary A ∈ fAB (P(1, N + 1)),
then it is true ∀A ∈ fAB (P(1, N + 1)). This implies that
each element in fAB (P(1, N + 1)) is a unique maximum
cut for some network construction. Therefore, without any
information about the link capacities `i , we cannot further
reduce the set of possible maximum cuts and thus we have
suf (P1 ) = fAB (P(1, N + 1)). This concludes the proof of
Step 3 and hence the proof of Lemma 4.
A PPENDIX D
P ROOF OF L EMMA 5
To compute the size of P(a, b), it is helpful to first prove
some properties of P(a, b) and primitive punctured subsets
that will help throughout the proof.
Property 1. Let H be a primitive punctured subset of [a : b],
then min{H} ≤ a + 1.
Proof. We prove this result by contradiction. Assume that for
some primitive punctured set H, we have min{H} ≥ a + 2.
This implies that H ⊂ [a + 2 : b]. Let Ĥ = H ∪ {a}. Since
H is a punctured set, then Ĥ is also a punctured set because
∀i ∈ H, |a − i| > 1. But since H ⊂ Ĥ, then H is not a
primitive punctured set, which is a contradiction.
Property 1 implies that, for a primitive punctured subset of
[a : b], the minimum element is either a or a + 1. Therefore,
we can write P(a, b) as
P(a, b) = P1 (a, b) ] P2 (a, b),
where P1 (a, b) (respectively, P2 (a, b)) is the collection of
primitive punctured sets with minimum element a (respectively, a + 1). Clearly, P1 and P2 are disjoint (we use ] to

indicate that the union is over disjoint sets). Next, we prove
some properties of P1 (a, b) and P2 (a, b).
Property 2. P2 (a, b) = P1 (a + 1, b).
Proof. Let H be a primitive punctured subset of [a+1 : b] that
contains the element a + 1. H is also a primitive punctured
subset of [a : b]. This follows since we cannot add {a} to
H to get a larger set of non-consecutive elements. Therefore,
H ∈ P1 (a + 1, b) =⇒ H ∈ P2 (a, b). The reverse implication
is straightforward since, by definition, P2 (a, b) is a primitive
punctured subset which contains the element a + 1.
For the next property, we need to define a new operation
on the collection of sets. For a collection of sets Q, define the
operation {i} t Q = {{i} ∪ H | H ∈ Q}. We then have the
following property of P1 (a, b).
Property 3. P1 (a, b) = {a} t P(a + 2, b).
Proof. Let H be a primitive punctured subset of [a + 2 : b]
and define Ĥ = {a} ∪ H. Since H is a primitive punctured
subset of [a + 2 : b], this means that @i ∈ [a + 2 : b]\H
such that {i} ∪ H is a punctured sequence of [a + 2 : b].
This implies that @i ∈ [a : b]\[H ∪ {i}] such that {i} ∪ Ĥ is
a punctured sequence of [a : b]. Therefore Ĥ is a primitive
punctured sequence of [a : b], i.e., Ĥ ∈ P1 (a, b). To prove
e ∈ P1 (a, b). We need to prove that
the reverse, consider H
e
Ĥ = H\{a}
is a primitive punctured subset of [a + 2 : b].
Note that the definition of primitive subset of [a : b] implies
e H
e ∪ {i} is not a punctured set. Since
that ∀i ∈ [a + 2 : b]\H,
e ∪ {i}
a 6∈ [a + 2 : b], this implies that ∀i ∈ [a + 2 : b]\Ĥ, H
e ∈ P1 (a, b) then
is not a punctured set. Now note that since H
e Therefore, ∀i ∈ [a + 2 : b] removing the element a
a + 1 6∈ H.
e
from H ∪ {i} does not make it a punctured set. We therefore
conclude that, ∀i ∈ [a + 2 : b]\Ĥ, Ĥ ∪ {i} is not a punctured
e
set and as a result Ĥ = H\{a}
is a primitive punctured subset
of [a + 2 : b].
We now have all the necessary tools to prove Lemma 5. We
obtain
P(1, N ) = P1 (1, N ) ] P2 (1, N )
(a)

= P1 (1, N ) ] P1 (2, N )




= {1} t P(3, N ) ] {2} t P(4, N ) ,

(b)

where the equality in (a) follows from Property 2 and the
equality in (b) follows from Property 3. Now note that
[{i} t P(a, N )] = P(a, N ) = P(1, N − a + 1)
= T (N − a + 1),
since the number of sets in each collection remain the same.
Therefore, we have
T (N ) = |P(1, N )|
= [{1} t P(3, N )] ] [{2} t P(4, N )]
= [{1} t P(3, N )]

+ [{2} t P(4, N )]

= T (N − 2) + T (N − 3).

This concludes the proof of Lemma 5.
S

D

A PPENDIX E
H ALF -D UPLEX ROUTING IS NP-H ARD
We are given a directed graph G with set of vertices G(V ),
edges E(G) and a source (S) and destination (D) vertices. For
a graph with N +2 vertices, we denote the source vertex as v0
and the destination vertex as vN +1 . For each edge e ∈ E(G),
we have an associated edge capacity c(e) > 0. For a path
P = vk1 − vk2 − vk3 − · · · − vkm+1 of length m in G, the
Half-Duplex capacity is defined as


c(eki−1 ki ) c(eki ki+1 )
.
(27)
CP = min
i∈[2:m] c(eki−1 ki ) + c(eki ki+1 )
An S-D path is a path such that vk1 = v0 and vkm +1 =
vN +1 . The capacity expression in (27) can be regarded as half
the minimum harmonic mean of the capacities of each two
consecutive edges in the path.
Our goal in this section, is to prove that the problem of
finding the S-D simple path with the best Half-Duplex capacity
in a graph is NP-Hard. Towards proving this, we first prove
that the related decision problem “HD-Path” is NP-complete.
Definition 2 (HD-Path problem). Given directed graph G and
a scalar value Z, does there exist an S-D simple path in G
whose Half-Duplex capacity is greater than or equal Z ?
Since the decision problem can be reduced in polynomial
time to finding the S-D simple path with the best Half-Duplex
capacity, then by proving the NP-completeness of the decision
problem, we also prove that the search problem is NP-Hard.
The HD-Path problem is NP because given a guess for
a path, we can verify in polynomial time whether it is
simple (i.e., no repeated vertices) and whether its Half-Duplex
capacity is greater than or equal Z by evaluating the expression
in (27).
To prove that the NP-completeness of the HD-Path problem,
we are going to show that we can reduce to this decision
problem from the classical 3SAT problem which is NPcomplete in polynomial time. For the 3SAT problem, we are
given a boolean expression B in 3-conjunctive normal form,
B =(p11 ∨ p12 ∨ p13 ) ∧ (p21 ∨ p22 ∨ p23 )
∧ · · · ∧ (pm1 ∨ pm2 ∨ pm3 ).

(28)

B is a conjuction of m clauses {C1 , C2 , . . . , Cm } which
each are a disjunction of at most three literals. A literal
pij is either a boolean variable xk or its negation x̄k . The
boolean expression B is satisfiable if the variables {xk } can be
assigned boolean values so that B is true. The 3SAT problem
answers the question: Is the given B satisfiable? We next prove
the main result in this section through the following Lemma.
Lemma 6. There exists a polynomial time reduction from
3SAT to the HD-Path problem.
Proof. To prove this statement, we are going to create a
sequence of graphs based on the Boolean statement B given to
the 3SAT problem. In each of these graphs, we shall show that

Fig. 1: Graph GB constructed from boolean expression
B = (x̄1 ∨ x2 ∨ x3 ) ∧ (x4 ∨ x1 ∨ x̄2 ) ∧ (x̄1 ∨ x3 ∨ x̄5 ).

the existence of a satisfying assignment for B is equivalent to
a particular feature in the graph. Our final step would give
us a Half-Duplex network where the feature equivalent to a
satisfying assignment of B is to find a Half-Duplex path with
approximate capacity greater than or equal to 1. Our proof
follows four steps of graph constructions as follows:
1) Assume that the boolean expression B is made of m
clauses. For each clause Ci in B, construct a gadget digraph
Gi with vertices
V (Gi ) = {ti , vi1 , vi2 , vi3 , ri } and edges
S3
E(Gi ) = j=1 {(ti , vij ), (vij , ri )}. Now we join the gadget
graphs Gi by adding directed edges (ri , ti+1 ), ∀i ∈ [1 : m−1].
Finally, we introduce a source vertex S and destination vertex
D and the directed edges (S, t1 ) and (rm , D). We denote this
new graph construction by GB .
Example. An illustration of the construction of GB for the
boolean expression B = (x̄1 ∨ x2 ∨ x3 ) ∧ (x4 ∨ x1 ∨ x̄2 ) ∧
(x̄1 ∨ x3 ∨ x̄5 ) can be seen in Fig. 1.
Note that each vertex vij in GB represents a literal pij in
the boolean expression B. We call a pair of vertices (vij , vk` )
in GB , with i < k, as forbidden if pij = pk` in B. Let
F be the set of all such forbidden pairs. Consider an S-D
path P = S − t1 − v1`1 − r1 , t2 − · · · − vm`m − rm − D
in the graph GB that contains at most one vertex from any
forbidden pair in F. Using the indexes characterizing the path
P , if we set the literals pi`i to be true ∀i ∈ [1 : m], then
this is a valid assignment (since P avoid all forbidden pairs
in F). Additionally, since we set one literal to be true in each
clause, then this assignment satisfies B. Hence the existence
of a path P in GB that avoids forbidden pairs implies that B
is satisfiable. Similarly, we can show that if B is satisfiable
then we can construct a path that avoids forbidden pairs in
GB using any assignment that satisfies B.
2) Next we modify the set of forbidden pairs F and the graph
GB such that each vertex appears at most once in F. For
each vertex vij that appears in at least one forbidden pair
of F, define VF (vij ) = {vi0 j 0 ∈ V (GB )|(vij , vi0 j 0 ) ∈ F}
and replace the vertex vij in GB with a path of the vertices
vij,k` , ∀vk` ∈ VF (vij ). We denote this new graph as G◦B . The
new set of forbidden pairs F ◦ is defined based on the set F
as F ◦ = { (vij,k` , vk`,ij )| (vij , vk` ) ∈ F}. Note that for this
new set of forbidden pairs, each vertex in G◦B appears in at
most one forbidden pair. Let VF ◦ be the set of vertices that
appear in F ◦ . Then ∀vij,kl ∈ VF ◦ , we replace vij,kl with a
path made of three vertices. In particular, for any vertex vij,k` ,
we replace it with a directed path aij,kl −vij,kl −bij,kl . We call
this new graph G?B and the forbidden pair set F ? = F ◦ . The

S

D

S

Fig. 2: Graph G?B and the forbidden list F ? constructed
from boolean expression B = (x̄1 ∨ x2 ∨ x3 )∧
(x4 ∨ x1 ∨ x̄2 ) ∧ (x̄1 ∨ x3 ∨ x̄5 ).

D

Fig. 3: Graph G•B for expression B = (x̄1 ∨ x2 ∨ x3 )∧
(x4 ∨ x1 ∨ x̄2 ) ∧ (x̄1 ∨ x3 ∨ x̄5 ) and the associated edge
capacities.

newly introduced vertices aij,k` and bij,k` are called a-type
and b-type vertices respectively.
Example. For our running example, the graph G?B and the
forbidden pair set F ? are shown in Fig. 2.
Similar to our argument earlier for GB , note that a path in
G?B that avoid forbidden pairs in F ? gives a valid satisfying
assignment to satisfy the boolean argument B. In the reverse
direction, if we have an assignment that satisfies B, then by
taking one true literal from each clause Ci , we can choose
ti − ri paths that avoid forbidden pairs. By joining these paths
together, we get an S-D path in G?B that avoids forbidden
pairs.
3) Our next step is to modify G? to incorporate F ? directly
into the structure of the graph. For each (vij,k` , vk`,ij ) ∈ F ?
introduce a new vertex fij,k` to replace vij,k` and vk`,ij . All
edges that were incident from (to) vij,k` , vk`,ij are now incident from (to) fij,k` . We call these newly introduced vertices
as f-type vertices and denote this new graph as G•B . Note that
in G•B , we now have an incident edge from aij,k` , ak`,ij to
fij,k` and edges incident from fij,k` to vertices bij,k` , bk`,ij .
A path in G?B that avoids forbidden pairs in F ? gives as a
path in G•B that follows the following rules:
1) Rule 1: If any f-type vertex is visited, then it is visited
at most once.
2) Rule 2: If an f-type vertex is visited then the preceding
a-type vertex and the following b-type vertex both share
the same index (i.e., we don’t have aij,k` − fij,k` − bk`,ij
or ak`,ij − fij,k` − bij,k` as a subset of our path in G•B ).
It is not hard to see that an S-D path in G•B that abides to the
two aforementioned rules can be appropriated to give a path
that avoids forbidden pairs F ? in G?B . This can be particularly
seen by treating the subpath (aij,k` − fij,k` − bij,k` ) in G•B as
passing through (aij,k` − vij,k` − bij,k` ) in G?B and similarly
(ak`,ij − fij,k` − bk`,ij ) for (ak`,ij − vk`,ij − bk`,ij ). In other
words, a problem of finding a path in G?B that avoids forbidden
pairs in F ? is equivalent to finding a path in G•B that satisfies
Rule 1 and Rule 2.
Example. For our running example, the graph G•B is shown
in Fig. 3.
4) Our next step is to modify G•B by introducing edge
capacities. For any edge e ∈ E(G•B ) that is not incident
from or to an f-type vertex, we set the capacity of that edge
c(e) = ∞. For an f-type vertex fij,k` , let e1 , f1 be the
edges incident to it from aij,k` and incident from it to bij,k` .

Similarly, let e2 , f2 be the edges incident from ak`,ij and to
bk`,ij . Then we set the edge capacities of these edges as
c(e1 ) = c(f2 ) = Z,

c(f1 ) = c(e2 ) = ∞.

We now need to show that finding a path satisfying Rules
1 and 2 is equivalent to finding a simple path in G•B with
Half-Duplex capacity ≥ Z. It is not hard to see that a path that
follows Rules 1 and 2 is simple and has a Half-Duplex capacity
≥ Z (by avoiding subpaths aij,k` −fij,k` −bk`,ij ). To prove the
equivalence, we need to show that a simple path with capacity
greater than or equal Z satisfies Rules 1 and 2. Towards this
end, note that Rule 1 is inheriently satisfied since the path is
simple (i.e., it visits any vertex at most once). For Rule 2, we
argue that both subpaths are avoided by contradiction.
Assume that the simple path selected contains a subpath of
the form aij,k` −fij,k` −bk`,ij . By our construction of the edge
capacities, both the edges (aij,k` , fij,k` ) and (fij,k` , bk`,ij )
have a capacity equal to Z. This gives us a contradiction
since half the harmonic mean between the capacities of these
two consecutive edge is equal to Z/2. Since the Half-Duplex
capacity of a path is minimum of half the harmonic means
of its consecutive edges, then the selected path cannot have
a Half-Duplex capacity greater than or equal Z which is a
contraction.
Now assume that the simple path selected with Half-Duplex
capacity ≥ Z contains (for some i0 , j 0 , k 0 and `0 ) a subpath of
the form ak0 `0 ,i0 j 0 − fi0 j 0 ,k0 `0 − bi0 j 0 ,k0 `0 . Note that as per our
construction in graph G•B , we have that i0 < k 0 . Let i? be
the smallest index i0 for which such a subpath exists in our
selected path. Since for the subpath in question we have that
i? < k 0 , then to reach ak0 `0 ,i? j 0 from S, we already visited ri?
earlier in the path. However to move from bi? j 0 ,k0 `0 to D (after
the subpath in question), we need to pass through ri? once
more. This gives a contradiction with the fact that the path
is simple. This proves the fact that finding a path satisfying
Rules 1 and 2 is equivalent to finding a simple path in G•B
with Half-Duplex capacity ≥ Z. The second statement is an
instant of the HD-Path problem.
Note that in each of the four graph constructions described
earlier, we construct one from the other using a polynomial
number of operations. Thus, this proves by construction that
there exists a polynomial reduction from the 3SAT problem
to the HD-Path problem.

R EFERENCES
[1] M. Cardone, D. Tuninetti, and R. Knopp, “The approximate optimality
of simple schedules for half-duplex multi-relay networks,” in IEEE
Information Theory Workshop (ITW), April 2015, pp. 1–5.
[2] S. Brahma, C. Fragouli, and A. Özgür, “On the complexity of scheduling
in half-duplex diamond networks,” IEEE Transactions on Information
Theory, vol. 62, no. 5, pp. 2557–2572, May 2016.
[3] A. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, “Wireless network
information flow: A deterministic approach,” IEEE Transactions on
Information Theory, vol. 57, no. 4, pp. 1872–1905, April 2011.
[4] A. Özgür and S. N. Diggavi, “Approximately achieving Gaussian relay
network capacity with lattice-based QMF codes,” IEEE Transactions on
Information Theory, vol. 59, no. 12, pp. 8275–8294, December 2013.
[5] M. Cardone, D. Tuninetti, R. Knopp, and U. Salim, “Gaussian halfduplex relay networks: improved constant gap and connections with the
assignment problem,” IEEE Transactions on Information Theory, vol. 60,
no. 6, pp. 3559 – 3575, June 2014.
[6] L. Ong, M. Motani, and S. J. Johnson, “On capacity and optimal
scheduling for the half-duplex multiple-relay channel,” IEEE Transactions
on Information Theory, vol. 58, no. 9, pp. 5770–5784, June 2012.
[7] R. Etkin, F. Parvaresh, I. Shomorony, and A. Avestimehr, “Computing
half-duplex schedules in Gaussian relay networks via min-cut approximations,” IEEE Transactions on Information Theory, vol. 60, no. 11, pp.
7204–7220, November 2014.
[8] S. Lim, Y.-H. Kim, A. El Gamal, and S.-Y. Chung, “Noisy network
coding,” IEEE Transactions on Information Theory, vol. 57, no. 5, pp.
3132 –3152, May 2011.
[9] G. Kramer, “Models and theory for relay channels with receive constraints,” in 42nd Annual Allerton Conference on Communication, Control, and Computing, September 2004, pp. 1312–1321.

