Half-Duplex Routing is NP-hard

arXiv:1708.03347v1 [cs.IT] 10 Aug 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—Routing is a widespread approach to transfer information from a source node to a destination node in many
deployed wireless ad-hoc networks. Today’s implemented routing
algorithms seek to efficiently find the path/route with the largest
Full-Duplex (FD) capacity, which is given by the minimum among
the point-to-point link capacities in the path. Such an approach
may be suboptimal if then the nodes in the selected path are
operated in Half-Duplex (HD) mode. Recently, the capacity (up
to a constant gap that only depends on the number of nodes in
the path) of an HD line network i.e., a path) has been shown to
be equal to half of the minimum of the harmonic means of the
capacities of two consecutive links in the path. This paper asks
the questions of whether it is possible to design a polynomialtime algorithm that efficiently finds the path with the largest HD
capacity in a relay network. This problem of finding that path
is shown to be NP-hard in general. 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.

I. I NTRODUCTION
In recent years there have been promising advances in the
design of Full-Duplex (FD) transceivers [1], [2]. Proposed FD
designs however require complex self-interference cancellation
techniques. Given this, in the near future it is envisioned that
nodes will continue to operate in HD mode – as recently
announced, for example, in 3GPP Rel-13 [3].
Today’s wireless ad-hoc networks route information from a
source node to a destination node through a single multi-hop
path, consisting of consecutive point-to-point links. Routing
is considered an appealing option since a route/path can be
efficiently operated, while providing energy savings (since
only the nodes along the path are operated) and limiting the
level of interference in the network. A rich body of literature
on wireless routing exists [4], [5], [6]. In this paper we revisit
the problem of HD routing in wireless networks starting from
the following observation.
Many routing algorithms seek to efficiently find the
path/route with the largest FD capacity, which is given by
the minimum among the point-to-point link capacities in the
path. Such an approach may be suboptimal if then the nodes
in the selected path are operated in HD mode, as shown by
the example in Fig. 1. Recall that, given a path that connects
node k0 to node kN +1 through N intermediate HD relays and
point-to-point link capacities cki−1 ,ki , ∀i ∈ [1 : N + 1], the
HD capacity (up to a constant gap that only depends on the
number of nodes in the path) is given by [7]


cki−1 ,ki cki ,ki+1
C = min
.
(1)
i∈[1:N ] cki−1 ,ki + cki ,ki+1

D

5
20

5

15

20

S
Best FD
path

20

100

Best HD
path

Fig. 1: Example where the best FD and HD paths are
different. Edge labels represent the point-to-point link
capacities of the edges.
By applying the expression in (1), we find that the best HDroute (within the blue box in Fig. 1) has an HD capacity of
13.04, which is 30% higher than the HD capacity of the best
FD-route (within the red box in Fig. 1, with FD capacity of
20 but HD capacity of 10). With best FD (resp. HD) route we
refer to the path that has the largest (FD resp. HD) capacity.
The above example shows that in general it is suboptimal
to find the best HD path by using as optimization metric the
FD capacity of the path. In fact, one can show that there exist
networks for which routing based on the FD capacities yields
a route with HD capacity equal to half that of the best HD
route [8]. This observation naturally suggests the question:
Does there exist an efficient (polynomial-time) algorithm that
finds the route in a network with the best HD capacity?
Contribution. The main result of this paper is that the problem
of finding the best HD route is NP-hard in general. Our proof is
based on a reduction from the 3SAT problem [9]. Additionally,
we provide a sufficient criterion – based on the number of
cycles in the network – for the existence of a polynomial-time
algorithm for some networks.
Related Work. An HD route connecting a source node to
a destination node through N relays is an N -relay HD line
network. For an HD line network, although the capacity is
known to be given by the cut-set bound (since the line network
is a degraded relay channel [10]), a closed-form expression of
it as a function of the point-to-point link capacities is not yet
available. Recent results in [11], generalized an observation
in [12], by showing that the HD capacity of a Gaussian relay
network can be approximated to within a constant gap (i.e.,
which is independent on the channel parameters and only
depends on the number of relays N ) by the cut-set upper
bound evaluated with a deterministic schedule independent

of the transmitted and received signals and with independent
inputs. Throughout the paper, we refer to this as the approximate capacity. Recently, in [7] we provided a closed-form
characterization of the approximate capacity for a Gaussian
HD line network (see the expression in (1)) and we developed
an algorithm to calculate the deterministic schedule needed to
achieve this approximate capacity in O(N 2 ) time.
A line of work in routing algorithms [13], [14], [15] focused
on finding a route between the source and the destination while
assuming that the point-to-point link capacities can only take
values of 0 or 1. Under this assumption, the route selection
based on the FD capacities is optimal. Finding the route with
the largest FD capacity is equivalent to the problem of finding
the widest-path between a pair of vertices in a graph [16]. This
can be solved efficiently (i.e., in polynomial-time) by adapting
any algorithm that finds the shortest path between a pair of
vertices in a graph (e.g., Dijkstra’s algorithm [17]). For routing
with multi-rate link capacities, several heuristic metrics have
been proposed to enhance the selection of routes in an ad-hoc
wireless network [4], [5].
Differently, we are here interested in selecting the route
with the largest HD approximate capacity, by also trying to
fundamentally address the complexity of finding such a path.
Paper Organization. Section II describes the setting of our
problem and the known capacity results for HD line networks.
Section III proves the NP-hardness of finding the best HD
route in a network. Section IV describes special network
classes for which a polynomial-time algorithm for finding the
best HD route exists. Section V concludes the paper.
II. S YSTEM M ODEL
We consider a network represented by the directed graph
G where V(G) and E(G) are the set of vertices (communication nodes) and the set of edges (point-to-point links) in G,
respectively. The point-to-point link between any two nodes is
assumed to be a discrete memoryless channel. For each edge
e ∈ E(G), we represent the point-to-point link capacity with
c(e) > 0. Over this graph, information flows from a source
node S ∈ V(G) to a destination node D ∈ V(G). For the graph
G with N + 2 vertices, we denote the source vertex as v0 and
the destination vertex as vN +1 .
A path P = vk1 − vk2 − . . . − vkm+1 of length m
in G is a sequence of vertices vki ∈ V(G), ∀i ∈ [1 : m + 1].
An S-D simple path in G is a path for which vk1 = v0 and
vkm +1 = vN +1 and all m + 1 vertices in P are distinct, i.e.,
there are no cycles in P. The HD approximate capacity of the
S-D simple path P is [7]


c(eki−1 ,ki ) c(eki ,ki+1 )
,
(2)
CP = min
i∈[2:m] c(eki−1 ,ki ) + c(eki ,ki+1 )
where eki−1 ,ki , i ∈ [1 : m + 1], represents the edge from
node vki−1 ∈ P to node vki ∈ P. The approximate capacity
expression in (2) is half of the minimum harmonic mean of
the capacities of each two consecutive edges in P.
Remark 1. The expression in (2) was derived in [7] in the
context of Gaussian noise networks. However, the analysis

directly extends if we replace each of the Gaussian point-topoint link with any discrete memoryless channel. This holds
since the cut-set bound is tight for any HD line network (i.e.,
degraded relay network [10]) where point-to-point links are
discrete memoryless channels assuming we allow for dynamic
schedules [12]. As a result, deterministic schedules would only
reduce the capacity by at most 1 bit per relay, thus providing
the same constant-gap approximation needed in [7].
III. HD ROUTING IS NP- HARD
IN this section, our goal in this section is to prove that the
problem of finding the best HD route in a network is NPhard. Towards this end, we start by showing that, if we want
to find the path P with the largest value of CP in (2), then it
is necessary to restrict our search over simple paths.
A. Non-simple paths are misleading in HD
Practically, a communication route through a network is
expected to be a simple path, i.e, a path that contains no
cycles. This is due to the fact that for a non-simple path, e.g.,
Pcyclic = S − v1 − v2 − · · · − vm − v2 − D, we know that
– from the degraded nature of the network – the information
sent from vm to v2 is a noisy version of the information that is
already available at v2 (since v2 appeared earlier in the path).
Thus, for the simple path Psimple = S − v1 − v2 − D, we
fundamentally have that
CPcyclic ≤ CPsimple .

(3)

This observation is true for both FD and HD paths in the
network and therefore the best path (in FD or HD) is naturally
a simple path. When routing using the FD capacities (to
select the best FD route), this observation turns out to be
just a technicality since the expression for the FD capacity
already exhibits the fundamental property described in (3).
Particularly, we have that E(Psimple ) ⊆ E(Pcyclic ), which
directly implies that
CFD
Pcyclic =

min
e∈E(Pcyclic )

{c(e)} ≤

min
e∈E(Psimple )

{c(e)} = CFD
Psimple .

Thus, an algorithm that selects a route in FD can end up with
either type of paths (simple or cyclic). If the path is cyclic,
then we can prune it to get a simple path while ensuring that
pruning can only improve the computed capacity.
Differently, for HD routing, it is very important to restrict
ourselves to searching over simple paths as the HD approximate capacity expression in (2) only applies to simple paths.
Furthermore, applying the expression in (2) to a path with a
cycle can actually increase the approximate capacity (in contradiction to the fundamental property in (3)). To illustrate this,
consider the network example shown in Fig. 2. From Fig. 2, we
now focus on the two paths: the simple path P1 = S − v1 − D
and the non-simple path P2 = S − v1 − v2 − v3 − v1 − D. Note
that P1 is a simple path and P2 is a cyclic extension of P1 by
adding the cycle v1 − v2 − v3 − v1 . If we apply the expression
in (2) on both paths, we get the value equal to 7.5 for P1
and for P2 we get 13.05. Thus, if an algorithm is allowed to
consider non-simple paths, then it would output the path P2

To prove the NP-completeness of the HD-Path problem,
we now show that the classical 3SAT problem (which is NPcomplete) [9] can be reduced in polynomial-time to the HDPath decision problem in Definition 1. For 3SAT, we are given
a boolean expression B in 3-conjunctive normal form,

S

15
20

D

15
20

Fig. 2: A network example in which a non-simple path can
appear to have a larger HD approximate capacity than its
simple subpath.

even though we know fundamentally that CP1 ≥ CP2 . This is
the first major problem that arises when we allow an algorithm
to output non-simple paths based on the expression in (2). The
second problem arises when we observe that P3 = S − v4 − D
in Fig. 2 is actually the best HD simple path from S to D.
However, since applying (2) for P2 yields 13.05, which is
larger than what we get for P3 (i.e., 10), then the algorithm
will output a non-simple path P2 which when pruned does not
yield the best HD path. Thus, an algorithm designed with the
goal to find the best HD path needs to be aware of the type
of paths that it processes. In other words, we can no longer
rely on pruning non-simple paths that an algorithm outputs as
these non-simple paths in HD can mislead the algorithm into
not selecting the best HD path as illustrated in this example.
As a consequence of the above discussion, in the rest of the
section, we focus on the problem of finding the simple (i.e.,
acyclic) path with the largest HD approximate capacity.

B(x1 , x2 , . . . , xn ) =(p11 ∨ p12 ∨ p13 ) ∧ (p21 ∨ p22 ∨ p23 )
∧ · · · ∧ (pm1 ∨ pm2 ∨ pm3 ),

(4)

where: (i) B is a conjunction of m clauses {C1 , C2 , . . . , Cm },
each containing a disjunction of three literals and (ii) a literal
pij is either a boolean variable xk or its negation x̄k for some
k ∈ [1 : n]. The boolean expression B is satisfiable if the
variables x[1:n] 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 of this section
through the following lemma.
Lemma 1. There exists a polynomial-time reduction from the
3SAT problem 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 show that
the existence of a satisfying assignment for B is equivalent
to a particular feature in the graph. Finally, we construct
an HD network where the feature equivalent to a satisfying
assignment of B is to find a simple path with HD approximate
capacity greater than or equal to Z. In particular, our proof
follows four steps of graph constructions, which are explained
in details in what follows. To illustrate these four steps we use
the following boolean expression as a running example:
B = (x̄1 ∨ x2 ∨ x3 ) ∧ (x4 ∨ x1 ∨ x̄2 ) ∧ (x̄1 ∨ x3 ∨ x̄5 ), (5)
where, with the notation in (4), the literals are assigned as
(p11 , p12 , p13 ) = (x̄1 , x2 , x3 ),

(6a)

B. Find the best HD simple path is NP-hard

(p21 , p22 , p23 ) = (x4 , x1 , x̄2 ),

(6b)

Our goal in this subsection, is to prove that the search
problem of finding the S-D simple path with the largest HD
approximate capacity in a graph is NP-hard. Towards proving
this, we first show that the related decision problem “HDPath”, which is defined below, is NP-complete.

(p31 , p32 , p33 ) = (x̄1 , x3 , x̄5 ).

(6c)

Definition 1 (HD-Path problem). Given a directed graph G
and a scalar Z > 0, does there exist an S-D simple path in
G with an HD approx. capacity greater than or equal to Z?
Since the decision problem defined above can be reduced
in polynomial-time to finding the S − D simple path with
the largest HD approximate capacity, then by proving the NPcompleteness 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 HD approximate
capacity is greater than or equal to Z by simply evaluating the
expression in (2).

1) Assume that the boolean expression B is made of m
clauses. For each clause Ci , i ∈ [1 : m], in B, construct a
gadget digraph Gi with
V(Gi ) = {ti , vi1 , vi2 , vi3 , ri }

S3 vertices
and edges E(Gi ) = j=1 eti ,vij , evij ,ri . Now we connect
the gadget graphs Gi , i ∈ [1 : m], by adding directed edges
eri ,ti+1 , ∀i ∈ [1 : m−1]. Finally, we introduce a source vertex
S and a destination vertex D and the directed edges eS,t1 and
erm ,D . We denote this new graph construction by GB . 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, by our definition, P avoids all
forbidden pairs in F). Additionally, since we set one literal

S

D

Fig. 3: Graph GB and set of forbidden pairs F for the boolean expression in (5).
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.
Example. The boolean expression in (5) has m = 3 clauses.
Hence, we construct 3 gadget digraphs that are connected to
form GB as represented in Fig. 3. Since each vertex vij , i ∈
[1 : m], j ∈ [1 : 3], in GB represents a literal pij in the
boolean expression in (5) (i.e., pij = vij ) and the literals are
assigned as described in (6), then the set of forbidden pairs is
given by
F = {(v11 , v22 ), (v12 , v23 ), (v22 , v31 )}

(7)

as also shown in Fig. 3.
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 }.
Then, for each VF (vij ), we create |VF (vij )| vertices and we
label them as vij,k` , ∀vk` ∈ VF (vij ). We finally replace the
vertex vij in GB with a path connecting the vertices vij,k` ,
◦
∀vk` ∈ VF (vij ). We denote this new graph as GB
. 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 GB
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 that consists
of three vertices. In particular, for any vertex vij,k` ∈ VF ◦ , we
replace it with a directed path aij,kl − vij,kl − bij,kl . We call
?
this new graph GB
and the forbidden pair set F ? = F ◦ . The
newly introduced vertices aij,k` and bij,k` are called a-type
and b-type vertices, respectively.
Similar to our earlier argument for GB , note that a path in
?
GB
that avoids forbidden pairs in F ? gives a valid satisfying
assignment for 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 , i ∈ [1 : m], we can
choose ti − ri paths that avoid forbidden pairs. By connecting
?
these paths together, we get an S-D path in GB
that avoids
forbidden pairs.

Example. For our running example, given the set of forbidden
pairs F in (7), we have
VF (v11 ) = {v22 } =⇒ v11 ← v11,22 ,
VF (v22 ) = {v11 , v31 } =⇒ v22 ← v22,11 − v22,31 ,
VF (v12 ) = {v23 } =⇒ v12 ← v12,23 ,
VF (v23 ) = {v12 } =⇒ v23 ← v23,12 ,
VF (v31 ) = {v22 } =⇒ v31 ← v31,22 ,
◦
where y ← Y indicates that in GB
the vertex y is replaced by
the path Y. The set of forbidden pairs F ◦ is then given by

F ◦ = {(v11,22 , v22,11 ), (v22,31 , v31,22 ), (v12,23 , v23,12 )} (8)
and hence VF ◦ = {v11,22 , v22,11 , v22,31 , v31,22 , v12,23 , v23,12 }.
?
by replacing
Given this, we can now construct the graph GB
◦
any vertex inside VF as follows
v11,22 ← a11,22 − v11,22 − b11,22 ,
v22,11 ← a22,11 − v22,11 − b22,11 ,
v22,31 ← a22,31 − v22,31 − b22,31 ,
v31,22 ← a31,22 − v31,22 − b31,22 ,
v12,23 ← a12,23 − v12,23 − b12,23 ,
v23,12 ← a23,12 − v23,12 − b23,12 ,
as shown in Fig. 4. Furthermore, we have F ◦ = F ? , where
F ◦ is defined in (8).
?
3) Our next step is to modify GB
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` and 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 GB
.
•
Note that in GB
, we now have incident edges from aij,k` and
ak`,ij to fij,k` and edges incident from fij,k` to vertices bij,k`
?
and bk`,ij . A path in GB
that avoids forbidden pairs in F ?
•
gives a path in GB 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 do not have aij,k` −fij,k` −bk`,ij
•
or ak`,ij − fij,k` − bij,k` as a subpath of our path in GB
).

S

D

?
?
Fig. 4: Graph GB
and set of forbidden pairs F ? . The graph GB
is constructed from GB in Fig. 3.

•
It is not difficult to see that an S-D path in GB
that abides
to the two aforementioned rules represents a feasible path that
?
avoids forbidden pairs F ? in GB
. Specifically, this can be seen
•
by treating the subpath (aij,k` − fij,k` − bij,k` ) in GB
as the
?
subpath (aij,k` − vij,k` − bij,k` ) in GB
and similarly (ak`,ij −
fij,k` − bk`,ij ) for (ak`,ij − vk`,ij − bk`,ij ). In other words, the
?
problem of finding a path in GB
that avoids forbidden pairs
?
•
in F is equivalent to finding a path in GB
that satisfies Rule
1 and Rule 2.
•
is shown
Example. For our running example, the graph GB
?
•
in Fig. 5. In particular, GB is constructed from GB in Fig. 4,
?
?
) such that
) and vk`,ij ∈ V(GB
where each vij,k` ∈ V(GB
?
?
(vij,k` , vk`,ij ) ∈ F , with F being defined in (8), is now
•
replaced by fij,k` in GB
, which is connected to the other nodes
as explained above.
•
by introducing edge
4) Our next step is to modify GB
•
capacities. For any edge e ∈ E(GB ) that is not incident from or
to an f-type vertex, we set the capacity of that edge c(e) = 3Z.
For an f-type vertex fij,k` , let g1 and h1 be the edges incident
to it from aij,k` and incident from it to bij,k` , respectively.
Similarly, let g2 and h2 be the edges incident from ak`,ij and
to bk`,ij , respectively. Then, we set the edge capacities of these
edges as

c(g1 ) = c(h2 ) = 1.5Z,

c(g2 ) = c(h1 ) = 3Z.

We now need to show that finding a path satisfying Rules 1
•
and 2 is equivalent to finding a simple path in GB
with HD
approximate capacity greater than or equal to Z. It is not
difficult to see that a path that follows Rules 1 and 2 is simple
and has an HD approximate capacity greater than or equal to
Z (by avoiding subpaths aij,k` − fij,k` − bk`,ij ). To prove the
equivalence, we now need to show that a simple path with
capacity greater than or equal to Z satisfies Rules 1 and 2.
Towards this end, note that Rule 1 is inherently satisfied since
the path is simple (i.e., it visits any vertex at most once).
For Rule 2, we next 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 eaij,k` ,fij,k` and efij,k` ,bk`,ij
have a capacity equal to 1.5Z. This gives us a contradiction
since half of the harmonic mean between the capacities of

these two consecutive edges is equal to 0.75Z. Since the HD
approximate capacity of a path is the minimum of half of the
harmonic means of its consecutive edges, then the selected
path cannot have an HD approximate capacity greater than
or equal to Z, which leads to a contraction. Thus, a subpath
aij,k` −fij,k` −bk`,ij is always avoided. We now need to prove
that also the path ak`,ij − fij,k` − bij,k` is always avoided.
Towards this end, assume that the simple path selected with
HD approximate capacity greater than or equal to 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 the
•
graph GB
, 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 have 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. Clearly,
since the path is simple, this leads to a contradiction. Thus,
a subpath ak`,ij − fij,k` − bij,k` is also always avoided. This
completes the proof that a simple path with capacity greater
than or equal to Z satisfies Rule 2. Therefore, finding a path
satisfying Rules 1 and 2 is equivalent to finding a simple path
•
with HD approximate capacity greater than or equal to
in GB
Z. The second statement is an instance of the HD-Path problem
in Definition 1.
Note that in each of the four graph constructions described earlier, we construct one graph 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. This concludes the
proof of Lemma 1.
Example. For our running example the assignment of the edge
capacities is shown in Fig. 5, where black and blue edges have
a capacity of 3Z and red edges have a capacity of 1.5Z.
IV. S OME INSTANCES WITH POLYNOMIAL - TIME
SOLUTIONS

In this section, we discuss a special class of networks
for which there exists a polynomial-time algorithm to find
a simple path with the largest HD approximate capacity. In
particular, we focus on networks where the number of cycles is
polynomial, i.e., the number of cycles is at most N α for some
constant α > 0, where N +2 is the total number of nodes in the

S

D

•
•
?
Fig. 5: Graph GB
and the associated edge capacities. The graph GB
is constructed from GB
in Fig. 4.

network. Our approach is based on relating paths in a network
(described by the digraph G) to paths in the line digraph of
G denoted as LG . We describe the relation in the following
subsection and then present an algorithm that finds the best
HD simple path in polynomial-time for the aforementioned
class of networks.

1

S’

S

Definition 2 (Line digraph LG ). For a given digraph G, its line
digraph LG is a digraph defined by the set of vertices V(LG )
and the set of directed edges E(LG ). The set V(LG ) is defined
as V(LG ) = {vij |ei,j ∈ E(G)} where ei,j is the directed edge
from vertex vi to vertex vj . The set of edges E(LG ) is defined
as E(LG ) = {eij,k` |k = j, vij , vk` ∈ V(LG )}.
An illustration of a digraph and its associated line digraph is
shown in Fig. 6. We can make the two following observations
on how simple HD paths are represented in the line digraph.
1) HD paths in G are equivalent to FD paths in LG . Note
that a path P in a network G can be equivalently defined as
the sequence of its adjacent edges (instead of vertices), i.e.,
we can equivalently write the path P = vk1 − vk2 − · · · − vkm
in G as P = ek1 ,k2 − ek2 ,k3 − · · · − ekm−1 ,km . Given this and
from the definition of the line digraph LG , the path P in G is
equivalent to the path PL = vk1 k2 − vk2 k3 · · · − vkm−1 km in
LG . For each edge eij,jk ∈ E(LG ), we define the capacity for
the edge eij,jk as
cL (eij,jk ) =

c(ei,j )c(ej,k )
,
c(ei,j ) + c(ej,k )

(9)

where c(ei,j ) is the point-to-point link capacity of the edge
(link) ei,j in G. Thus, we have that the FD capacity of the
path PL in LG is given by
CFD
PL =

{cL (eij,jk )}


c(ei,j ) c(ej,k )
= CP ,
=
min
eij,jk ∈E(PL ) c(ei,j ) + c(ej,k )
min

eij,jk ∈E(PL )

(10)

where CP is defined in (2). From (10) and our previous
discussion, we can conclude that, to find the path with the

3

2

5

4

16

S1

A. The line digraph perspective to the best HD path problem
A line digraph of a digraph G is defined as follows.

6

10

63

D
7

10

3D

5
S’S

21

32

10

10
25

42

10

DD’

5

10
S4

10

10

10

D’

1

10
5D

10

Fig. 6: An example of a digraph G with its corresponding
line digraph LG . For ease of notation, indexes ij instead of
vij are used and the edge capacities are only shown on LG .
largest HD approximate capacity in the network described
by the digraph G, we can first find the path in LG that has
the largest FD capacity (where the link capacities in LG are
defined as in (9)) and then map this path in LG into its
equivalent in G.
2) Simple paths in G are equivalent to simple chordless
paths in LG . We start by defining chordal and chordless paths
in digraphs.
Definition 3 (Chordal and chordless paths). A path in the
digraph G 0 is chordal if there exists an edge e ∈ E(G 0 ) such
that its endpoints are two non-consecutive vertices in the path.
A path that is not chordal is called chordless.
For example, with reference to Fig. 6, the path S 0 − S −
v4 − v2 − v1 − v6 − v3 − D − D0 is a chordal path in G since
e3,2 ∈ E(G) and the vertices v3 and v2 belong to the path but
are non-consecutive. Thus, e3,2 is a chord for this path in G.
A similar reasoning holds for eS,1 .
Consider a cyclic path Pcycle in G. This implies that some
vertex vk ∈ Pcycle appears at least twice in the path. Denote
with vq1 the node following vk in its first appearance in Pcycle
and with vq2 the node preceding vk in its second appearance in

the path Pcycle . Then, if we write the line digraph equivalence
of Pcycle , we have

S’S

PLcycle = · · · − vkq1 − · · · − vq2 k − . . . .
From the construction of E(LG ) in Definition 2, we see that the
edge eq2 k,kq1 ∈ E(LG ), which implies that PLcycle is chordal.
Differently, for a simple path Psimple , any vertex vk ∈
Psimple appears only once. Thus, in the line digraph equivalent
path PLsimple , the index k appears only in two consecutive
vertices, which implies that PLsimple is chordless. This shows
the equivalence described in our observation between simple
paths in G and simple chordless paths in LG .
Given the two observations above, we can now equivalently
describe our HD routing problem on the line digraph as
follows: Can we find the chordless simple path in LG that
has the largest FD capacity?
B. An algorithm on the line digraph LG

10

10

(i)

Step 1. Given the line digraph LG and an existing best FD
(i)
path spanning tree Ti , check whether the path PL from vS 0 S
to vDD0 defined by Ti is chordless. If it is chordless, terminate
the algorithm since we have found the chordless path from
vS 0 S to vDD0 with the largest FD capacity. Otherwise, if it is
not chordless, then proceed to Step 2.
(0)
Example. We use the line digraph from Fig. 6 as our LG .
Then, for i = 0, we have the spanning tree T0 (from Dijkstra’s
(0)
algorithm) and the selected path PL as shown in Fig. 7. The
(0)
(0)
(0)
path PL is chordal since e32,21 ∈ LG and e42,25 ∈ LG .
(i)

Step 2. Let CP be the set of edges in LG that are chords
(i)
for the path PL from vS 0 S to vDD0 discussed in the earlier
(i)
(i)
step. Let CP,first ∈ CP be the first chord that appears along
(i)
(i)
the path PL . We denote the endpoints of CP,first as vk1 k2

5

S1

42

10

21

10
10
7

16

63

3D

10

10

The goal of the algorithm described in this section is to
find the chordless simple path in LG that has the largest FD
capacity. The algorithm described here is a modification of
the result proposed in [18] for selecting shortest paths while
avoiding forbidden subpaths. To start, we first modify our
given network (described by G) so that the source S and
the destination D have at most degree one. In particular, we
modify the digraph G by adding two new nodes (namely, S 0
and D0 ) that are connected only to S and D with edges eS 0 ,S
and eD,D0 (similar to Fig. 6). These two added edges have
point-to-point capacities equal to X → ∞. Denote this new
digraph by G 0 and create the line digraph associated with G 0
(0)
(0)
and denote it by LG . In LG , we now consider the node vS 0 S
as our source and the node vDD0 as our intended destination.
The algorithm is based on incrementally applying Dijkstra’s
algorithm [17]. We first try to find the best FD path from vS 0 S
(i)
to vDD0 in LG by running Dijkstra’s algorithm. Note that
Dijkstra’s algorithm returns a spanning tree rooted at vS 0 S
that describes the best FD path from vS 0 S to each vertex v 0
(i)
in LG . We denote the tree from our initial run as T0 . From
this point, the algorithm iterates (until termination) over four
main steps described as follows (starting with i = 0).

(i)

S4

32

10

5D

10

25

DD’

(0)

Fig. 7: Spanning tree T0 for LG = LG in Fig. 6 (indexes ij
instead of vij are used for ease of notation). Boldface
numbers represent the FD capacity with which a node can be
reached from SS 0 using the tree T0 . The highlighted path is
the route selected from this tree T0 from S 0 S to DD0 .

and vkm km+1 , where vk1 k2 is the vertex that among the two
(i)
appears earlier in the path PL and where m is the length of
(i)
(i)
the subpath Pto−fix of PL connecting the two endpoints, i.e.,
(i)
we now have a path Pto−fix = vk1 k2 − vk2 k3 − · · · − vkm km+1 .
Notice that, with this, we have km+1 = k1 .
Example. For our running example and i = 0, we can see
(0)
(0)
from Fig. 6 and Fig. 7 that the set of chords for PL is CP =
(0)
{e32,21 , e42,25 }. The selected chord CP,first is e32,21 because
its effect on the path concludes earlier than e42,25 . Hence, we
(0)
have Pto−fix = v21 −v16 −v63 −v32 , which is of length m = 4.
(i)

Step 3. We now introduce new vertices to the graph LG by
(i)
replicating every intermediate vertex in Pto−fix . In particular,
0
we introduce a replica vertex vki0 ki+1
for vki ki+1 where i ∈
[2 : m−1]. We connect these replicas of vertices to each other
in the same way their corresponding originals are connected
(i)
0
0
0
in Pto−fix , i.e., we include the edge eki0 ki+1
∀i ∈ [2 :
,ki+1
ki+2
m−1] with the same edge capacity as eki ki+1 ,ki+1 ki+2 .
(i)

(i)

Then, for every vi0 j 0 ∈ V(LG )\V(Pto−fix ) such that
(i)
ei0 j 0 ,ki ki+1 ∈ E(LG ), we add an edge that connects vi0 j 0 to the
0
replica vertex of vki ki+1 , i.e., we add the edge ei0 j 0 ,ki0 ki+1
(with
the same edge capacity as ei0 j 0 ,ki ki+1 ). In other words, every
(i)
(i)
vertex in LG that is not in Pto−fix and has an edge incident on
(i)
an intermediate vertex vki ki+1 , i ∈ [2 : m − 1], of Pto−fix now
0
has a similar (replicated) edge incident on the replica vki0 ki+1
of vki ki+1 . Note that at this point: (i) the original vertices in
(i)
(i)
Pto−fix still form a chordal path in LG and (ii) the replica
vertices have every possible incident connection their original

16

S1

10

10

3D

S’S

21

32

10

10
1

10

1’6’

10

10

10
5
S’S

7

16

63

3D

10

32

DD’

S’S

5
10

10
1

10

1’6’

10

16

S1

10

10
10
10

7

10

1

DD’

10
25

5

1’6’

5

16

6’3’

5

63

32

5

5D

5

10

32

10

S1

21

10

3D

5

10

42

10

63

21

42

10

6’3’

10

10

S4

5D

10

5
S’S

10

25

42

10

7

3D

21

S1

21

10

10

10

S4

10

10

10
10

5

5D

6’3’

63

10

42

10

16

S1

10

10

25

42

S4

S4
DD’

5

10
S4

10

10

10

5

S’S

7

63

7

3D

7

DD’

10

5

25

5D

10

(0)
(1)
Fig. 8: LG from Fig. 6 and the corresponding LbG and
The replica vertices and the added edges are shown in
red while the deleted edges are dashed.

(1)
LG .

vertices had except connections to the two endpoint vertices
(i)
(i+1)
of Pto−fix . We denote the digraph at this point as LbG .
Now, our last change is to modify how the two endpoints
(i)
(i+1)
of the path Pto−fix in LbG
connect to the intermediate
vertices of the path and their replicas. We do this by adding the
0
0 ,k k
edge ekm−1
that connects the last replicated vertex
km
m m+1
(i)

0
0
to the endpoint vkm km+1 of Pto−fix and by removing
vkm−1
km
the edge ekm−1 km ,km km+1 that connected the original last
intermediate vertex to the endpoint. In particular, the new edge
0
0 ,k k
ekm−1
has the same capacity as ekm−1 km ,km km+1
km
m m+1

(i+1)

that was removed. Denote this new digraph as LG . Note
(i+1)
(i)
that in this new digraph LG , the path Pto−fix does not exist
anymore, while all the other chordless paths have stayed the
same. Thus, we have successfully eliminated a cycle (chordal
path) that appeared in the digraph before by replicating vertices and deleting edges.
Example. For our running example and i = 0, recall that
(0)
Pto−fix = v21 − v16 − v63 − v32 . The new generated digraphs
(1)
(1)
LbG and LG are shown in Fig. 8.
Step 4. In the fourth step, our goal is to create the spanning
tree Ti+1 of the best FD paths associated with the digraph
(i+1)
LG . To ensure termination of the algorithm, a condition
for this construction is that Ti+1 should be made as similar as
possible to Ti [18]. To do so, we run Dijkstra’s algorithm to

(1)

Fig. 9: Spanning trees T10 and T1 for LG in Fig. 8. Boldface
numbers represent the FD capacity with which a node can be
reached from SS 0 using each tree.

find the new spanning tree Ti+1 but we start at an intermediate
stage in the algorithm, since we already know part of the
spanning tree from Ti . In particular, we do the following
(i)
procedure. Recall our definition of Pto−fix and its endpoint
(i+1)
vkm km+1 in Step 2. Define Vredo to be the set of vertices for
which we need to find a new best FD path. In particular, we
(i+1)
define Vredo as the union of: (i) the set of all replica vertices
(i+1)
introduced in LG , (ii) the set of descendant vertices of
vkm km+1 in Ti , and (iii) the vertex vkm km+1 . For any vertex
(i+1)
v 6∈ Vredo , the path connecting vSS 0 to v in Ti does not pass
(i)
through Pto−fix . As a result, we can copy this part of Ti to
Ti+1 without loss of generality. Clearly, replica vertices never
(i+1)
existed before LG
so there is no known path for them in Ti .
Similarly, the path from vS 0 S to vkm km+1 (and its descendants)
(i)
passes through Pto−fix , thus we need to find a new route for
them now that the chordal path has been eliminated from the
(i+1)
graph. Also it is not difficult to see that any v 0 6∈ Vredo will
(i+1)
not be a descendant of v, ∀v ∈ Vredo as this would contradict
(i+1)
the need to find a new path for some vertex in Vredo .
As per our discussion above, we find the rest of Ti+1 by
initializing an intermediate point in the Dijkstra’s algorithm
and continue the execution of the algorithm from there. In
(i+1)
particular, we start from the point where ∀v 6∈ Vredo have

been expanded (and thus appear in Ti+1 with the same path
as in Ti ). We denote the intermediate version of Ti+1 at this
0
point as Ti+1
, which is a pruned version of the tree Ti . Note
that, at any iteration of the classical Dijkstra’s algorithm, a
yet to be expanded vertex v has a best so-far path from
vS 0 S of FD capacity c0 (v). This achievable FD capacity at
an unexpanded vertex v is based on the maximum capacity
achieved by each of the neighbor vertices that have already
0
been expanded and added to the spanning tree Ti+1
as well as
the capacities of incident edges from those neighbor vertices
to the vertex v. We denote the capacity of a neighbor vertex v 0
T
that was already expanded as ĉLi+1 (v 0 ). We now note that the
point from which we are going to start Dijkstra’s algorithm
(i+1)
is when the set of unexpanded vertices is Vredo and the
c
(i+1)
0
form the complement set Vredo . Thus, for
vertices in Ti+1
(i+1)
the vertices still unexpanded (i.e., in Vredo ), the capacities
currently achievable at them at this stage of the algorithm are
initialized as
n
o
b
cL (v) = max min cTLi (v), cL (ev0 ,v ) .
(i+1)

v 0 6∈Vredo

Now that we have the initialization of Dijkstra’s algorithm to
the state that we want, we run the standard routine of the
(i+1)
algorithm to continue expanding the vertices in Vredo . When
all the vertices have been expanded, we get the final tree Ti+1 .
Example. For our running example and i = 0, the tree T10
(which is a subset of T0 ) and the new generated tree T1 for
(1)
LG are shown in Fig. 9. It is worth noting that the spanning
(1)
tree T1 in Fig. 9 has the path PL = vSS 0 − vS4 − v42 −
v21 − v16 − v63 − v3D − vDD0 of capacity CFD(1) = 7 that is
PL
chordless. Hence the algorithm returns this path and terminates
(see Step 1).
It is important to note that, from the replication procedure
we do in Step 3, we add a number of replica vertices equal
(i)
to the length of Pto−fix minus two (since we do not replicate
the endpoints). Moreover, in addition to the replica vertices,
(i)
(i+1)
only one endpoint of Pto−fix is a member of Vredo (i.e., the
(i)

vertex vkm km+1 ). As a result Vredo ≤ |V(LG )| , ∀i. Thus,
the size of the network that Dijkstra’s algorithm processes in
Step 4 does not increase from one iteration to the next. This
implies that Step 4 of the algorithm has a complexity that is
at most O(VLG log VLG + ELG ) where VLG = |V(LG )| and
ELG = |E(LG )|. The time complexity of Steps 1, 2 and 3 is
linear in VLG and ELG . Let KG be the number of cycles in
G. From the observation in Section IV-A, this is equal to the
number of chordal paths in LG . Since in each iteration over the
four steps, we eliminate one chordal path, then for a line graph
with KG chordal paths, we make at most KG iterations. As a
result, the complexity of the described algorithm for finding
the simple chordless path with the largest FD capacity in LG
is O ((KG + 1)(VLG log VLG + ELG )).
Note that the number of vertices in LG is equal to the
number of edges in G and the number of edges in LG is
upper bounded by the number of edges in G multiplied by

the maximum vertex degree d. Additionally, the complexity of
constructing a line digraph LG from a digraph G is of order
O(|E(G)|d). Thus, the problem of finding the simple path in
G with the largest HD approximate capacity is equivalent to
creating the line digraph LG with FD capacities and then
finding the chordless path with the largest FD capacity in
that line digraph LG . The computational complexity of this
procedure is O (|E(G)|d + (KG + 1)(VLG log VLG + ELG )) =
O ((KG + 1)(|E(G)| log |E(G)| + |E(G)|d)).
Corollary 2. If the number of cycles in a network with N
relays (described by the digraph G) is at most polynomial
O(N α ), then we can find the simple path with the largest HD
approximate capacity in polynomial-time, i.e., in O((N α +
1)(|E(G)| log |E(G)| + |E(G)|d)). This holds even when we do
not have an a priori knowledge of the location of the cycles.
As a network example for which Corollary 2 applies, we
can study the layered network where the relays are arranged
as NL relays per layer over L layers. Every relay can only
communicate with the relays in the following layer of relays.
It is not difficult to see that for this particular network, the
number of cycles in the graph is equal to zero, i.e., KG = 0. In
addition, the maximum degree d of a vertex is O(NL ) and the
number of edges in the network is Θ(LNL2 ). By substituting
these values to the expression in Corollary 2, we get that
the complexity of finding a simple path with the largest HD
approximate capacity in a layered network is given by
O((KG + 1)(|E(G)| log |E(G)| + |E(G)|d))
= O(LNL2 log LNL2 + LNL2 NL )
= O(LNL2 log L + 2LNL2 log NL + LNL3 )
= O(LNL2 log L + LNL3 ).
V. C ONCLUSION
In this work we proved that, given a network with a source
node, a destination node and a number of relays, finding the
path from the source to the destination with the largest HD
approximate capacity is NP-hard in general. This represents
a surprising result and it is fundamentally different from the
FD counterpart, since the path with the largest FD capacity
can always be discovered in polynomial-time. We also showed
that, if the number of cycles inside the network is polynomial
in the number of nodes, then a polynomial-time algorithm
exists to find the best HD path.
Future work would include discovering alternative sufficient
conditions that allow to develop polynomial-time algorithms
(similar to the one on the number of cycles presented in this
paper) and designing low-complexity algorithms that, even if
not optimal, ensure that a significant portion of the best HD
path approximate capacity can always be achieved.
R EFERENCES
[1] M. Duarte, A. Sabharwal, V. Aggarwal, R. Jana, K. Ramakrishnan, C. W.
Rice, and N. Shankaranarayanan, “Design and characterization of a fullduplex multiantenna system for wifi networks,” IEEE Transactions on
Vehicular Technology, vol. 63, no. 3, pp. 1160–1177, 2014.

[2] E. Everett, C. Shepard, L. Zhong, and A. Sabharwal, “Softnull: Manyantenna full-duplex wireless via digital beamforming,” IEEE Transactions on Wireless Communications, vol. 15, no. 12, pp. 8077–8092, 2016.
[3] Y.-P. E. Wang, X. Lin, A. Adhikary, A. Grovlen, Y. Sui, Y. Blankenship,
J. Bergman, and H. S. Razaghi, “A primer on 3gpp narrowband internet
of things,” IEEE Communications Magazine, vol. 55, no. 3, pp. 117–123,
2017.
[4] B. Awerbuch, D. Holmer, and H. Rubens, “High throughput route
selection in multi-rate ad hoc wireless networks,” Wireless On-Demand
Network Systems, pp. 201–205, 2004.
[5] D. S. De Couto, D. Aguayo, J. Bicket, and R. Morris, “A high-throughput
path metric for multi-hop wireless routing,” Wireless networks, vol. 11,
no. 4, pp. 419–434, 2005.
[6] J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva, “A
performance comparison of multi-hop wireless ad hoc network routing
protocols,” in Proceedings of the 4th annual ACM/IEEE international
conference on Mobile computing and networking. ACM, 1998, pp.
85–97.
[7] Y. H. Ezzeldin, M. Cardone, C. Fragouli, and D. Tuninetti, “Efficiently
finding simple half-duplex schedules in Gaussian relay line networks,”
in IEEE International Symposium on Information Theory (ISIT), June
2017, pp. 471–475.
[8] M. Cardone, Y. H. Ezzeldin, C. Fragouli, and D. Tuninetti, “Network simplification in half-duplex: Building on submodularity,”
arXiv:1607.01441, July 2017.
[9] R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of computer computations. Springer, 1972, pp. 85–103.
[10] M. R. Aref, “Information flow in relay networks,” Ph.D. thesis, Stanford
University, 1981.
[11] 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.
[12] 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.
[13] C. E. Perkins and E. M. Royer, “Ad-hoc On-Demand Distance Vector
Routing,” in Proceedings of the Second IEEE Workshop on Mobile
Computer Systems and Applications, 1999, p. 90.
[14] T. Clausen and P. Jacquet, “Optimized Link State Routing Protocol
(OLSR),” RFC 3626, DOI 10.17487/RFC3626, 2003.
[15] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc
Wireless Networks,” in Mobile computing. Springer, 1996, pp. 153–
181.
[16] M. Pollack, “Letter to the editorthe maximum capacity through a
network,” Operations Research, vol. 8, no. 5, pp. 733–736, 1960.
[17] E. W. Dijkstra, “A note on two problems in connexion with graphs,”
Numerische mathematik, vol. 1, no. 1, pp. 269–271, 1959.
[18] M. Ahmed and A. Lubiw, “Shortest paths avoiding forbidden subpaths,”
in 26th International Symposium on Theoretical Aspects of Computer
Science STACS 2009. IBFI Schloss Dagstuhl, 2009, pp. 63–74.

