Scheduling Wireless Ad Hoc Networks in
Polynomial Time Using Claw-free Conflict
Graphs

arXiv:1711.01620v1 [cs.IT] 5 Nov 2017

Alper Köse∗† , Muriel Médard∗
∗ Research Laboratory of Electronics, Massachusetts Institute of Technology,
77 Massachusetts Avenue, Cambridge, MA 02139, USA

† Department of Electrical Engineering, École Polytechnique Fédérale de Lausanne

Route Cantonale, 1015 Lausanne, Switzerland
{akose, medard}@mit.edu

Abstract—In this paper, we address the scheduling
problem in wireless ad hoc networks by exploiting the
computational advantage that comes when such scheduling
problems can be represented by claw-free conflict graphs.
It is possible to formulate a scheduling problem of network
coded flows as finding maximum weighted independent
set (MWIS) in the conflict graph of the network. We
consider activation of hyperedges in a hypergraph to model
a wireless broadcast medium. We show that the conflict
graph of certain wireless ad hoc networks are claw-free.
It is known that finding MWIS of a general graph is NPhard, but in a claw-free conflict graph, it is possible to
apply Minty’s or Faenza et al.’s algorithms in polynomial
time. We discuss our approach on some sample networks.
Keywords—Wireless ad hoc networks; Claw-free graph;
Conflict graph; Independent Set

I.

I NTRODUCTION

The problem of scheduling in wireless ad hoc networks is generally computationally expensive. In [1],
Arikan proves that scheduling is NP-complete in general
packet radio networks when both primary and secondary interference are considered. In spread spectrum
networks, complexity reduces as shown in [2], where
link-based scheduling can be done in polynomial time
when each node can converse with at most one other
node at a time. We schedule subsets of hyperedges in
the hypergraph model of the network instead of doing
classical link-based scheduling due to inability of linkbased scheduling to capture the character of network
coded flows. In [3], authors prove the NP-completeness
of scheduling broadcasts without tolerance of secondary
conflicts. Another perspective for evaluation of interference is K-hop interference models in which no two links
within K hops can successfully transmit simultaneously.
It is proved in [4] and [5] that link scheduling can be
completed in polynomial time when K = 1, otherwise
it is NP-hard. In [6], scheduling of network coded flows
with conflict graphs is considered, but without exploiting
any graph characteristic. The model we illustrate is
∗ This

work has been presented at the 2017 IEEE PIMRC.

closely related to [6]. Novelty of this paper comes
from the fact that polynomial time scheduling property
of wireless networks having claw-free conflict graphs
is not investigated, and we contribute to literature by
introducing some families of networks which can be
scheduled in polynomial time.
In a conflict graph of a network, each node symbolizes a valid transmission and an edge between two
nodes represents that these two transmissions cannot
be scheduled simultaneously, owing to interference constraints which can differ based on the assumptions on
the network. The rate region of the network with random
linear network coding is determined by three different
constraints on capacity, flow and scheduling as in [6].
Among these constraints, the determinant for optimization complexity is the scheduling constraint. Therefore,
in this work, we concentrate on the scheduling constraint
rather than the others. The scheduling problem can be
formulated as finding maximum weighted independent
set (MWIS) in the conflict graph where independent
set is defined as follows. Given an undirected graph
G = (V, E), a subset of vertices S ⊆ V is an independent set if {i, j} ∈
/ E is satisfied for all i and j
in S. There are several examples for independent set
formulation including the scheduling for routed traffic
[7] and network code construction in a wireline setup
[8]. Finding MWIS dominates the complexity of the
rate maximization problem in the rate region. MWIS
problem is NP-hard for general graphs, therefore this
makes scheduling NP-hard in general networks. On other
hand, it is known that MWIS problem is solvable in
polynomial time in claw-free graphs [9], [10], [11]. A
graph G = (V, E) is claw-free if none of its vertices V
has three pairwise nonadjacent neighbours [12].
The remainder of the paper is organized as follows.
We detail on the conflict graph construction and present
different scenarios, which are on line and tree networks
for which the conflict graphs are claw-free, in Section II.
As a next step, we explain the rate region constraints and
discuss some results in a butterfly network in Section III.
Finally, we conclude the paper in Section IV.

II.

N ETWORK M ODEL AND C ONFLICT G RAPH

E

Throughout the scenarios, we use the Protocol model
[13] and K-hop interference model [4] with small variations to represent networks instead of the Physical model
[13], which takes SIN R levels into account.

r

A. Scenario I

r

B

r
A
C

r
D

r

r

F
G
We consider a wireless ad hoc network with n nodes.
We have a set of assumptions for the network:
A1.1) A node cannot receive from multiple nodes at Fig. 1: A wireless network example with the weights r
the same time and a node cannot receive if it is in the which show the Euclidean distance between nodes.
interference range of another transmitting node.
A1.2) Time division duplex transceivers are used in
network.
(E, B)
A1.3) The Protocol model [13] is used to decide interference relationships between transmissions. Suppose node
A is transmitting to node B where node C is simultaneously making a transmission to another node. Then,
the transmission between A and B will be successful if
(A, B)
and only if inequalities (1) and (2) are satisfied:

|A − B| ≤ rT
|B − C| ≥ (1 + ∆)|A − B|

(1)

(F, C)

(G, D)

Fig. 2: An induced subgraph of the conflict graph of the
(2) network in Fig. 1.

where rT is the maximum transmission range of
nodes and ∆ > 0 is the guard zone which can be
chosen arbitrarily small for simplicity without loss of
generality. Inequality (1) means that every node employs
a common range of transmission rT , and (2) says that
in a communication pair, among all transmitting nodes,
the receiver of this pair must be closest to its transmitter
with a guard zone ∆.
Without making additional assumptions, the conflict
graph of a network is not guaranteed to be claw-free.
Construction 1 (Construction of Conflict Graph):
Reference [6] shows the construction of conflict graph
G = (V, E) in a wireless network. Here, we use a similar
strategy. It consists of the steps below:
C1.1) We can denote transmission v as (i, J) where i
is the source and J as the set of receivers and N (i)
as the set of nodes that are in the transmission range
of node i. The condition for a transmission being valid
is given by J ⊂ N (i), which means that the set of
receiver nodes must be in the transmission range of the
transmitter node. A valid transmission v is modeled as
a vertex, v ∈ V.
C1.2) Say v1 , v2 ∈ V, then {v1 , v2 } ∈ E if v1 and v2
cannot be scheduled simultaneously.
Let v1 , v2 ∈ V be in the conflict graph.{v1, v2 } ∈ E if
any of the below conditions hold:
C1.2.1) i1 = i2 ;
C1.2.2) (i1 ∈ J2 )||(i2 ∈ J1 );
C1.2.3) J1 ∩ J2 6= ∅;
C1.2.4) |i2 − j| ≤ (1 + ∆)|i1 − j| for ∃j ∈ J1 ;
C1.2.5) |i1 − j| ≤ (1 + ∆)|i2 − j| for ∃j ∈ J2 .

Example 1: Consider the topology given in Fig.
1. Assume a transmission range rT and an Euclidean
distance r where rT ≥ r . In this case, when A is a transmitting, for instance to B, then there will be interference
to (E, B), (F, C), (G, D) due to the Protocol model [13]
and hence transmission node (A,B) shares edges with
these three possible transmissions in the conflict graph.
On the other hand, suppose ∠BAC, ∠CAD, ∠DAB =
120◦ , then there will not be any interference between any
pairs of (E, B), (F, C), (G, D) because these transmissions satisfy constraint (2) as well as (1). Consequently,
this will lead to a claw in the conflict graph which can
be seen in Fig. 2.
Example 2: A possible arrangement of wireless
nodes to have a claw-free conflict graph is shown in
Fig. 3. Source and sink can be thought as the nodes A
and E, respectively. Let the maximum possible transmission distance be rT and ∆ be very small. Then,
we can model the conflict graph of this network as
seen in Fig. 4. The independent set polytope is the
convex hull of the incidence vectors of the five independent sets {(A, B), (D, E)}, (A, C), {(B, C), (D, E)},
(C, D) and (A, {B, C}).
We can generalize Example 2 by realizing that
the conflict graphs of the line networks are claw-free
provided that there is enough distance between nodes
to make 3 node away transmission impossible. We
should physically satisfy rT < |µi − µi+3 | for all
i ∈ {1, 2, ..., n − 3} where µi is the ith node in the

A

2rT /3

B

rT /3

C

rT

D

rT

E

Fig. 3: A possible physical arrangement of the wireless
network which leads to a claw-free conflict graph for
Scenario I.

(A, B)

B

C

D

E

F

Fig. 6: Illustration for proof of Theorem 1.

v1

v2

...

vn−2

vn−1

Fig. 7: Conflict graph of a line network where only
possible transmission for a node i is vi = (i, i + 1).

(A, C)

(C, D)

A

(D, E)

(A, {B, C})

(B, C)

Fig. 4: Conflict graph of the network seen in Fig. 3.

network. This inequality can be easily satisfied by many
different positioning scenarios, so, for simplicity, we
can use a hypergraph H = (N , A) to represent our
model, where N denotes the nodes and A denotes the
hyperedges to symbolize valid transmissions between
wireless nodes. Hypergraph of a line network, which
has claw-free conflict graph, changes depending on the
number of nodes to which a node i can transmit, which
can be 1 or 2 for every i ∈ {1, 2, ..., n − 2} and 1
for i ∈ {n − 1}. We have 2n−2 different possible
hypergraphs of a line network, with n nodes, all of
which lead to claw-free conflict graphs. For instance,
hypergraph of the network in Fig. 3 can be seen in Fig.
5. Here, first node is able to transmit up to next two
neighbours whereas the other nodes are only able to
transmit to next node. Transmissions (A, B) and (C, D)
are not simultaneously possible, because we use the
Protocol model [13] to decide interference relations.
Receiver B is closer to C, a transmitter of another
transmission, than to A and this violates the constraint
(2). Directed antennas, which we do not assume in our
scenario, could be used to avoid the interference.

To have a claw in the conflict graph, a transmission
v1 should have conflicts with three other transmissions
v2 , v3 , v4 whereas those three should not have any
conflicts between them. Let us use Fig. 6 for ease of
understanding. Since transmissions are from µ1 to µn ,
from source to sink, assume that a node only transmits
to nodes that are located closer to sink in terms of hop
distance. To this end, assume v1 as the central node
of a possible claw, v1 = (C, D). Then, we can have
one interfering transmission from the source side of C,
say v2 = (A, B), and one from the sink side of D,
v3 = (E, F ) not to have interference between v2 and
v3 . B and E are chosen to be as far as possible. In such
situation, transmitting nodes C and E cause interference
on receiving nodes B and D, respectively. Now, we
have to place the transmitter and the receiver of the
last transmission. This one has to interfere with (C, D)
without interfering with (A, B) and (E, F ) to induce a
claw in the conflict graph of the network. If we place
the transmitter on the source side of C, this leads to
an interference with (A, B) which will break the claw,
so this option is not possible. Also, we cannot place
the receiver in the sink side of D since this leads to
an interference with (E, F ) which will again break the
claw. Therefore, since the receiver must be on the sink
side relative to the transmitter, the only remaining option
is to place both the transmitter and the receiver between
C and D. However, this option makes C able to transmit
to 3 different nodes where we assume each node is able
to transmit to at most 2 nodes.

Let us consider a line network to see the effect of
increasing number of nodes on end-to-end throughput,
first when all transmissions are orthogonal and second
when MWIS scheduling policy is used. To be very
simple, suppose we have a line network with n nodes
and each node can only transmit to next node where node
Proof: Let us prove this theorem by contradiction. µ1 is the source and node µn is the sink. Suppose n is
odd. Also, assume that the transmission (i, i + 1) does
not lead to an interference with (i + 2, i + 3). We name
the transmission (i, i+1) as vi . Under these assumptions,
B
our conflict graph is shown in Fig. 7. So we have two
different maximum independent sets, where weights are
A
C
D
E
assumed equal, which are S1 = {v1 , v3 , ..., vn−2 } and
S2 = {v2 , v4 , ..., vn−1 }. Consider the situation where
transmissions do not have any errors or loss. Since we
Fig. 5: Hypergraph of the network seen in Fig. 3.
only need 2 time slots to combine S1 and S2 to complete

Theorem 1: Under the assumptions A1.1-3 and
Construction 1, the conflict graph of a line network
where a node is able to transmit to at most 2 nodes
and all nodes convey information in the direction from
µ1 to µn is guaranteed to be claw-free.

end-to-end transmissions, we conclude that end-to-end
F
throughput is 1/2 bits/sec if we assume one time slot
D
has a duration of 1 second and the link capacity between
B
G
nodes is 1 bit/sec. The throughput does not depend
A
E
on n. However, if we assume all transmissions to be
orthogonal, we can say that throughput will decrease
C
linearly with the number of nodes in the network as it
equals 1/(n − 1) bits/sec per frequency use. As seen,
we have 0.5(n − 1) gain on throughput by using MWIS Fig. 8: An example of a tree network which has clawapproach. Using network coding does not provide any free conflict graph for Scenario II.
advantage in the end-to-end throughput of this system.
B. Scenario II
We can have other network topologies that induce
a claw-free conflict graph. One of them is a tree representation of the network, but since it is harder to get
claw-freeness with the same assumptions for the line
topology model, we propose new set of assumptions:
A2.1) A node cannot receive from multiple nodes at the
same time.
A2.2) Time division duplex transceivers are used in
network.
A2.3) Nodes are arranged as a tree topology.
A2.4) We directly work on hypergraph model without
any consideration on physical locations of nodes and
assume an interference model based on hops instead of
the Protocol model [13].
A2.5) Transmissions are in the direction from root node
to leaves of tree.
A2.6) Directed antennas are used, so interference can
only occur in the forward direction along the tree.
A2.7) A transmitting node does not lead to any interference to the receivers which are 3-hops or more away
from it.
A2.8) Only one node in every level can have children.

(A, B)

(B, D)

(D, F )

(A, C)

(B, E)

(D, G)

(A, {B, C})

(B, {D, E})

(D, {F, G})

Fig. 9: Conflict graph of the network seen in Fig. 8.

ik ’s parent. Since only one of these transmissions can
be scheduled in one time slot, they induce a complete
subgraph in the conflict graph. Therefore, we can only
choose one transmission, say v2 , from level k − 1 to k
which has interference with v1 because the cardinality
of maximum independent set of the complete graph is
1. Assuming that we have the node ik+1 , which belongs
to level k + 1 and has children, in the receiver set of the
transmission v1 (otherwise, it is easier to say that we will
not have a claw.), we have another complete subgraph
which contains the transmissions from the node ik+1 to
its children in level k + 2. One of these transmissions
can be selected for a possible claw, say v3 . Since, it is
not possible to find another independent transmission v4 ,
we have a claw-free conflict graph for the network.

Construction 2 (Construction of Conflict Graph):
In the construction of conflict graph, we implement the
steps below:
C2.1) Model valid transmissions as the vertices V of
conflict graph G = (V, E) as in C1.1.
C2.2) Say v1 , v2 ∈ V, then {v1 , v2 } ∈ E if v1 and v2
cannot be scheduled simultaneously.
Let v1 , v2 ∈ V be in the conflict graph.{v1, v2 } ∈ E if
any of the below conditions hold:
C2.2.1) i1 = i2 ;
An example of a tree network which has a claw-free
C2.2.2) (i1 ∈ J2 )||(i2 ∈ J1 );
conflict
graph and its conflict graph can be seen in Fig.
C2.2.3) J1 ∩ J2 6= ∅;
8
and
Fig.
9, respectively.
C2.2.4) (i1 is a child of i2 ) || (i2 is a child of i1 ).

Theorem 2: Under the assumptions A2.1-8 and C. Scenario III
Construction 2, conflict graph of a wireless network is
In this scenario, transmission and interference
guaranteed to be claw-free.
schemes are less restricted, since we only allow for
Proof: Let us assume that the root node belongs to full-duplex transceivers and do not allow for 2-hop
level 1 and a node, which has a distance k to root in interference, compared to Scenario II, but the network
terms of hyperedge number, belongs to level k +1. Now, topology is relaxed by letting every node have children.
consider the transmission v1 , from a node ik in level k Assumptions are below:
to its children that reside in level k +1. We have 2Nk −1 A3.1) A node cannot receive from multiple nodes at the
different interfering transmissions to v1 which are from same time.
level k − 1 to k where Nk is the number of children of A3.2) Full duplex transceivers are used in network.

A3.3) Nodes are arranged as a tree topology.
F
A3.4) We directly work on hypergraph model without
D
any consideration on physical locations of nodes and
G
assume an interference model based on hops instead of
B
the Protocol model [13].
A3.5) Transmissions are in the direction from root node
A
H
to leaves of tree.
C
E
A3.6) Directed antennas are used, so interference can
I
only occur in the forward direction along the tree.
A3.7) A transmitting node does not lead to any interference to the receivers which are 2-hops or more away Fig. 10: An example of a tree network which has a clawfrom it.
free conflict graph for Scenario III but not for Scenario
Construction 3 (Construction of Conflict Graph): II.
In the construction of conflict graph, we implement the
steps below:
C3.1) Model valid transmissions as the vertices V of
conflict graph G = (V, E) as in C1.1.
C3.2) Say v1 , v2 ∈ V, then {v1 , v2 } ∈ E if v1 and v2
cannot be scheduled simultaneously.
Let v1 , v2 ∈ V be in the conflict graph.{v1, v2 } ∈ E if
any of the below conditions hold:
C3.2.1) i1 = i2 ;
C3.2.2) J1 ∩ J2 6= ∅;
Theorem 3: Under the assumptions A3.1-7 and
Construction 3, conflict graph of a wireless network is
guaranteed to be claw-free.
Proof: Let us again assume that the root node
belongs to level 1 and a node, which has a distance k
to root in terms of hyperedge number, belongs to level
k + 1. In these settings, we eliminate the possibility
of having interference between any transmissions from
different levels. Let us denote a transmission from a node
in level k to a node in level k + 1 as k → k + 1. Any
transmission k → k+1 interferes neither with k−1 → k
nor with k + 1 → k + 2 because we use full-duplex
transceivers which makes a node eligible to transmit
and receive at the same time. Therefore, we only have
interference between the transmissions which initiate
from the same node. A node with j children has 2j − 1
possible transmissions where each pair has interference
between them which then leads to a complete graph with
2j − 1 nodes in the conflict graph. Assume we have m
non-leaf tree nodes, then we have m disjoint complete
subgraphs in the overall conflict graph which implies
that the conflict graph is claw-free.
An example of a tree network which has a claw-free
conflict graph and its conflict graph can be seen in Fig.
10 and Fig. 11, respectively.

(A, B)

(B, D)

(D, F )

(E, H)

(A, C)

(B, E)

(D, G)

(E, I)

(A, {B, C})

(B, {D, E})

(D, {F, G})

(E, {H, I})

Fig. 11: Conflict graph of the network seen in Fig. 10.

T ∈ N where all sinks T ∈ N demand the same
information and network coding is used. We can extend
it to multiple connections using intra-session coding.
When we use i to denote a wireless node, N (i) denotes
the set of nodes to which node i can transmit, namely
there is a hyperedge from i to set N (i). Recall that
MWIS problem dominates the complexity of the rate
maximization problem in the rate region. In this section,
we review the three constraints of the rate region to
highlight the importance of the scheduling problem that
we address by revisiting [6] and [14] and give the
formulation of MWIS problem for the conflict graph.
Firstly, we have capacity constraints given in (3).
X

(t)

xij ≤

j∈K

X

zij

(3)

j⊂N (i)

∀i ∈ N , K ⊂ N (i), t ∈ T .
(t)

In constraint (3), xij shows the flow rate of data
packets from node i to node j in the way of sink t. ziJ
III. R ATE R EGION
is the average packet injection rate to the output set J of
hyperedge
(i, J) and ziJ is guaranteed to exist and be
A. Rate Region Constraints
finite if the injection process is assumed to be stationary
To find the rate region, we assume that we have a and ergodic.
hypergraph H = (N , A) model of the network as in
Second, we have flow constraints given in (4) and
Fig. 8 where N symbolizes the nodes and A symbolizes
the hyperedges. We consider the multicast connection (5).
with rate R, we have a source s ∈ N and sinks

network has claw-free conflict graph. There are 12 valid

transmissions, 3 for each node being source except E
if i = s
R,
X
X (t)
and F . Therefore, possible transmissions from a node
(t)
xji = −R, if i = t
xij −
(4) lead to a complete subgraph of 3 nodes. To have a claw,

{j|i∈N (j)}
j∈N (i)
0,
otherwise
a transmission (i1 , J1 ) should have three conflicts, each
with a different source ia 6= ib for a, b ∈ {1, 2, 3, 4}
where these three should not have any conflicts between
∀i ∈ N , t ∈ T .
them. However, this is not possible in the given butterfly
network which lead to a claw-free conflict graph. So,
(t)
(5) the scheduling can be completed in polynomial time.
xij ≥ 0
Complement of the conflict graph can be seen in Fig.
∀i ∈ N , j ∈ N (i), t ∈ T .
13 for a more clear illustration.
Constraint (4) should be satisfied to guarantee a flow
Assume all transmissions are done without any errors
of rate R from the source to sinks and it is trivial that or loss from source to sinks and every link has a unit
flow rates cannot be negative as seen in (5).
capacity, say 1 bit/sec. We have 2 bits to send in the
multicast
connection. We consider four different conLastly, we have the scheduling constraint given in
ditions where the constraints (3)-(6) from the previous
(6).
subsection only apply to MWIS approach with network
coding:
z ∈ PIN D (G).
(6) 1) All transmissions are orthogonal without network
coding.
In (6), vector z = (ziJ ) is called network coding 2) All transmissions are orthogonal with network coding.
subgraph where (i, J) ∈ A. PIN D (G) denotes the 3) MWIS approach without network coding.
independent set polytope of G = (V, E), which is the 4) MWIS approach with network coding.
conflict graph of the considered network. In overall, the
In the fully orthogonal model [14], all transmission
network coding subgraph should lie in the independent
signals are orthogonal, making the network interferenceset polytope of the conflict graph.
free but this leads to a suboptimal bandwith usage.
The maximum weighted independent set problem We maximize bandwith efficiency by frequency reuse
of a weighted undirected graph G = (V, w, E) with n whenever possible. We could also consider the two-hop
vertices where w : V(G) → R can be formulated as constraints model [6] in which if a node i transmits,
none of the nodes in two-hop neighbourhood of i can
below:
P
transmit, but it adds up to the same thing with orthogonal
Maximize i∈V wi vi
model in this butterfly network. In 1-3, our conflict graph
construction, Construction 1, does not represent the
Subject to vi + vj ≤ 1 {i, j} ∈ E
conditions correctly owing to some additional constraints
where vi ∈ {0, 1} for 1 ≤ i ≤ n.
that show up. For instance, when we adopt orthogonal
We maximize R subject to (3)-(6). Scheduling con- model, conflict graph becomes a complete graph where
straint (6) can be formulated as MWIS problem, and we can choose only one transmission for a time slot
it is known to be NP-hard for general graphs to solve due to our bandwith limited regime. Our conflict graph
which makes our optimization problem NP-hard. How- formulation can only be used for MWIS approach with
ever, there are algorithms proposed for solving MWIS network coding. Throughput analysis can be seen below:
problem in claw-free graphs in polynomial time. For 1) We can achieve an end-to-end throughput of 1/3
instance, Minty’s [9], [10] algorithm can be used for bits/sec per frequency use.
solvability in O(n6 ) or Faenza et al.’s [11] algorithm 2) We can achieve an end-to-end throughput of 2/5
can be used for further improvement to O(n3 ). Since we bits/sec per frequency use which is better than the first
are able to find MWIS of the claw-free conflict graph in approach.
polynomial time, it is possible to solve the joint subgraph 3) We are now scheduling {(A, B), (C, {D, F })},
optimization and scheduling problem, i.e. maximizing R {(A, C), (B, {D, E})}, (D, E) and (D, F ) in four
time slots, thus have an end-to-end throughput of 1/2
subject to (3)-(6), in polynomial time [15].
bits/sec which is better than second approach.
4) We first set the conflict graph as seen in Fig. 13,
B. Illustration
then find the maximum weighted independent sets, and
Networks having claw-free conflict graphs are not finally use convex combination of them for scheduling.
limited with the discussed ones in Section II. Let us We have {(A, B), (C, {D, F })}, {(A, C), (B, {D, E})}
consider a butterfly network as seen in Fig. 12 with and (D, {E, F }) which we can combine in three time
the assumptions A1.1-3 which lead to Construction 1 slots. End-to-end throughput is 2/3 bits/sec which is
where r ≤ rT , |AD| > rT and ∆ is negligible. A the highest among four conditions.
is the source node where E and F are the sinks of
a multicast connection. First, we show that butterfly

r

C

r
A

r

r
r

D

r

B

[2]

F

r

[3]

r
[4]

E

Fig. 12: A butterfly network with the weights r which
show the Euclidean distance between nodes.

(A, C)

(C, D)

(C, F )

(C, {D, F })

(D, F )

(A, {B, C})

[5]

[6]
(D, {E, F })

[7]
(A, B)

(B, D)

(B, E)

(B, {D, E})

(D, E)

[8]

Fig. 13: Complement of the conflict graph of the network
seen in Fig. 12.
[9]

IV.

C ONCLUSION

We have investigated wireless ad hoc networks which
have claw-free conflict graphs. To this end, we used
conflict graph to model possible valid transmissions
and their interference relations in the network, then
we exploited the claw-freeness of the conflict graph of
certain networks and MWIS algorithm for graphs to
do the scheduling in polynomial time. We believe that
this paper can be used as a guide to set up wireless
networks which allow jointly solving the network coding
subgraph and the scheduling problem in polynomial
time. However, most of the real life networks do not have
claw-free conflict graphs and our approach can only be
applied to limited number of networks.
For future work, we work on a strategy which
breaks all of the claws in a conflict graph by iteratively
introducing edges. We believe this new strategy will
allow us to do polynomial time scheduling for more
general networks with a very small throughput loss.
Besides this new strategy, the Physical model [13] can
be considered to form the conflict graph of networks
which may complicate scenarios but give a more detailed
view at the same time. Lastly, a superset of clawfree graphs in which MWIS problem can be solved in
polynomial time can be searched to extend throughput
optimal polynomial time scheduling to more general
networks.
R EFERENCES
[1]

E. Arikan, “Some complexity results about packet radio networks (corresp.),” IEEE Transactions on Information Theory,
vol. 30, no. 4, pp. 681–685, 1984.

[10]

[11]

[12]
[13]

[14]

[15]

B. Hajek and G. Sasaki, “Link scheduling in polynomial time,”
IEEE transactions on Information Theory, vol. 34, no. 5, pp.
910–917, 1988.
A. Ephremides and T. V. Truong, “Scheduling broadcasts in
multihop radio networks,” IEEE Transactions on communications, vol. 38, no. 4, pp. 456–460, 1990.
G. Sharma, R. R. Mazumdar, and N. B. Shroff, “On the complexity of scheduling in wireless networks,” in Proceedings of
the 12th annual international conference on Mobile computing
and networking. ACM, 2006, pp. 227–238.
G. Sharma, N. B. Shroff, and R. R. Mazumdar, “Maximum
weighted matching with interference constraints,” in Pervasive
Computing and Communications Workshops, 2006. PerCom
Workshops 2006. Fourth Annual IEEE International Conference
on. IEEE, 2006, pp. 5–pp.
D. Traskov, M. Heindlmaier, M. Médard, and R. Koetter,
“Scheduling for network-coded multicast,” IEEE/ACM Transactions on Networking (TON), vol. 20, no. 5, pp. 1479–1488,
2012.
L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum
throughput in multihop radio networks,” IEEE transactions on
automatic control, vol. 37, no. 12, pp. 1936–1948, 1992.
J. K. Sundararajan, M. Médard, R. Koetter, and E. Erez, “A
systematic approach to network coding problems using conflict
graphs,” in Proceedings of the UCSD Workshop on Information
Theory and its Applications, 2006.
G. J. Minty, “On maximal independent sets of vertices in clawfree graphs,” Journal of Combinatorial Theory, Series B, vol. 28,
no. 3, pp. 284–304, 1980.
D. Nakamura and A. Tamura, “A revision of minty’s algorithm
for finding a maximum weight stable set of a claw-free graph,”
Journal of the Operations Research Society of Japan, vol. 44,
no. 2, pp. 194–204, 2001.
Y. Faenza, G. Oriolo, and G. Stauffer, “Solving the weighted
stable set problem in claw-free graphs via decomposition,”
Journal of the ACM (JACM), vol. 61, no. 4, p. 20, 2014.
M. Chudnovsky and P. D. Seymour, “The structure of claw-free
graphs.” Surveys in combinatorics, vol. 327, pp. 153–171, 2005.
P. Gupta and P. R. Kumar, “The capacity of wireless networks,”
IEEE Transactions on information theory, vol. 46, no. 2, pp.
388–404, 2000.
D. S. Lun, N. Ratnakar, M. Médard, R. Koetter, D. R. Karger,
T. Ho, E. Ahmed, and F. Zhao, “Minimum-cost multicast over
coded packet networks,” IEEE Transactions on information
theory, vol. 52, no. 6, pp. 2608–2623, 2006.
D. Traskov, M. Heindlmaier, M. Médard, R. Koetter, and D. S.
Lun, “Scheduling for network coded multicast: A conflict graph
formulation,” in GLOBECOM Workshops, 2008 IEEE. IEEE,
2008, pp. 1–5.

