Topological Interference Management

When You Know the Topology but Not the Channels

In the interference channel and MIMO BC analysis of Chapters 16-17, we assumed that the transmitters know the channel matrices — either perfectly (for DPC and IA) or at least approximately. But in many practical scenarios, the transmitters know only the network topology: which transmitters interfere with which receivers, and which links are absent.

Topological interference management (TIM) asks: what rates can be achieved when the transmitters know only the interference graph — which links exist — but not the channel coefficients? This is a much coarser level of CSIT than what IA or DPC requires, and it leads to a fundamentally different set of achievable results.

The surprising finding is that even topological knowledge alone can achieve non-trivial DoF — and the achievable DoF is determined by an elegant connection to index coding, a combinatorial problem studied independently in computer science.

Definition:
Topological Interference Management

A TIM problem is defined by:

A set of $K$ transmitter-receiver pairs
An interference graph $\mathcal{G} = (V, E)$ where $V = [K]$ and $(i, j) \in E$ if Tx $i$ interferes with Rx $j$ (for $i \neq j$ )
Channel coefficients are generic (drawn from a continuous distribution) but unknown to the transmitters
The transmitters know only the topology $\mathcal{G}$

The topological DoF is the maximum sum DoF achievable with only topological CSIT: $d_{\Sigma}^{\text{top}} = \max \sum_{k=1}^K d_k$ subject to the constraint that the coding scheme depends only on $\mathcal{G}$ , not on the specific channel realizations.

Topological interference management

An interference management framework where transmitters know only which interference links exist (the network topology) but not the channel coefficient values. The achievable DoF depends on the graph structure and is connected to the index coding problem.

Definition:
Connection to Index Coding

An index coding problem consists of a server with $K$ messages and $K$ clients. Client $k$ wants message $W_k$ and has a subset $\mathcal{A}_k \subseteq [K] \setminus \{k\}$ of messages as side information. The server broadcasts coded messages, and each client uses its side information to decode its desired message.

The connection to TIM: if Tx $i$ does not interfere with Rx $j$ (i.e., $(i,j) \notin E$ ), then Rx $j$ "effectively" has side information about $W_i$ (it can decode $W_i$ without being affected by Tx $i$ 's signal). The TIM problem can be mapped to an index coding problem where the side information graph is the complement of the interference graph.

The index coding optimal rate equals the topological DoF, providing a combinatorial characterization.

Theorem: Topological DoF via Index Coding

For a $K$ -user interference channel with interference topology $\mathcal{G}$ , the topological DoF (with topological CSIT only) satisfies: $d_{\Sigma}^{\text{top}} = \beta(\bar{\mathcal{G}})$

where $\bar{\mathcal{G}}$ is the complement graph of $\mathcal{G}$ (edges where interference is absent) and $\beta(\bar{\mathcal{G}})$ is the independence number of $\bar{\mathcal{G}}$ — the size of the largest set of non-interfering transmitter-receiver pairs.

More precisely, the fractional chromatic number and other graph-theoretic quantities provide tighter bounds in general.

The independence number of $\bar{\mathcal{G}}$ counts the maximum number of transmitter-receiver pairs that can communicate simultaneously without any mutual interference. These pairs can achieve DoF = 1 each simply by transmitting simultaneously (no interference between them). More sophisticated schemes using linear codes over the topology can achieve fractional DoF gains.

Proof

Achievability via orthogonal scheduling

Find a maximum independent set $\mathcal{I}$ in $\bar{\mathcal{G}}$ : a set of transmitter-receiver pairs with no mutual interference. Schedule these pairs simultaneously, achieving $|\mathcal{I}|$ DoF. This gives $d_{\Sigma}^{\text{top}} \geq \beta(\bar{\mathcal{G}})$ .

Converse via information-theoretic argument

The converse uses the fact that without channel knowledge, the transmitters cannot align interference. Each receiver must deal with the worst-case interference from all connected transmitters. The maximum rate is bounded by the capacity of the interference-free sub-network, giving $d_{\Sigma}^{\text{top}} \leq \beta(\bar{\mathcal{G}})$ .

Fractional relaxation

By time-sharing between different independent sets, the achievable DoF can exceed $\beta(\bar{\mathcal{G}})$ and approach the fractional chromatic number $\chi_f(\bar{\mathcal{G}})$ , providing a tighter characterization.

Example: TIM for a 4-User Interference Network

Consider a 4-user IC where Tx 1 interferes with Rx 2, Tx 2 interferes with Rx 3, Tx 3 interferes with Rx 4, and Tx 4 interferes with Rx 1 (a cycle topology). Find the topological DoF.

Solution

Interference graph

The interference graph $\mathcal{G}$ has edges: $(1,2), (2,3), (3,4), (4,1)$ — a 4-cycle. The complement $\bar{\mathcal{G}}$ has edges: $(1,3), (2,4)$ and the reverse (i.e., non-interfering pairs are $\{1,3\}$ and $\{2,4\}$ ).

Independence number

In $\bar{\mathcal{G}}$ : $\{1, 3\}$ is an independent set (no edge between them in $\mathcal{G}$ , meaning they don't interfere). Similarly $\{2, 4\}$ . The maximum independent set has size 2: $\beta(\bar{\mathcal{G}}) = 2$ .

Topological DoF

$d_{\Sigma}^{\text{top}} = 2$ . Achievability: schedule $\{1, 3\}$ in even slots and $\{2, 4\}$ in odd slots. Each pair uses half the time, getting DoF = 1/2 each. Sum DoF = $4 \times 1/2 = 2$ .

Comparison with full CSIT

With full CSIT (interference alignment): $d_{\Sigma} = K/2 = 2$ . The topological DoF matches the IA DoF for this particular topology — no channel knowledge is needed beyond the topology to achieve the optimal DoF. This is a special case; for general topologies, full CSIT can provide strictly higher DoF.

CSIT Levels and Achievable DoF

CSIT Level	Knowledge	Scheme	DoF ( $K$ -user IC)
No CSIT	Nothing about channels	TDMA/FDMA	1
Topological CSIT	Which links exist	TIM / index coding	$\beta(\bar{\mathcal{G}})$ (graph-dependent)
Statistical CSIT	Channel distributions	Ergodic alignment	Intermediate
Full CSIT	Exact channel matrices	Interference alignment	$K/2$

🔧Engineering Note

Topological Knowledge in Practice

Topological CSIT is much easier to obtain than full CSIT in practice:

Base stations can learn the interference topology from long-term measurements (which neighboring cells cause interference) without tracking fast fading.
The topology changes slowly (on the timescale of user mobility and cell configuration), unlike channel coefficients that change at the Doppler rate.
Network planning tools already compute interference graphs for frequency reuse planning.

TIM provides a principled framework for interference management using only this coarse information. In 5G HetNets (heterogeneous networks with macro and small cells), the interference topology is the natural design variable, and TIM-inspired scheduling can improve spectral efficiency without the overhead of full CSI acquisition.

Practical Constraints

•
Topology changes on timescale of minutes to hours (user mobility)
•
Full CSI changes on timescale of milliseconds (Doppler)
•
Topology can be learned from CQI reports and RSRP measurements
•
5G NR inter-cell coordination uses topology-level information

Common Mistake: TIM Does Not Replace Interference Alignment

Mistake:

Concluding that topological interference management makes interference alignment obsolete, since topology is easier to obtain.

Correction:

TIM and IA operate at different CSIT levels and achieve different DoF. For many topologies, the topological DoF is strictly lower than the IA DoF ( $K/2$ ). TIM is useful when full CSIT is unavailable, but it cannot match the IA performance when precise channel knowledge is available. The practical question is whether the cost of acquiring full CSIT is justified by the DoF improvement — and for many systems, it is not.

Quick Check

For a 3-user IC where every transmitter interferes with every other receiver (fully connected interference graph), what is the topological DoF?

1, because the complement graph has no edges, so the independence number is 1

3/2, because IA achieves this for 3 users

3, because each user can communicate at full rate

Correction:

1, because the complement graph has no edges, so the independence number is 1

In the complement $\\bar{\\mathcal{G}}$ , there are no edges (every pair interferes). The maximum independent set has size 1 (only one user can transmit at a time without interference). $d_{\\Sigma}^{\\text{top}} = 1$ , which is just TDMA.

Key Takeaway

Topological interference management achieves non-trivial DoF using only knowledge of which interference links exist, not their strengths. The achievable DoF is determined by graph-theoretic quantities (independence number, fractional chromatic number) and is connected to the index coding problem. TIM is particularly relevant for practical systems where full CSI is too expensive to acquire, and it provides a theoretical foundation for topology-aware interference management in heterogeneous networks.

The ISAC Fundamental Tradeoff Chapter Summary

Topological Interference Management

When You Know the Topology but Not the Channels

Definition: Topological Interference Management

Topological interference management

Definition: Connection to Index Coding

Theorem: Topological DoF via Index Coding

Achievability via orthogonal scheduling

Converse via information-theoretic argument

Fractional relaxation

Example: TIM for a 4-User Interference Network

Interference graph

Independence number

Topological DoF

Comparison with full CSIT

CSIT Levels and Achievable DoF

Topological Knowledge in Practice

Common Mistake: TIM Does Not Replace Interference Alignment

Quick Check

Key Takeaway

Definition:
Topological Interference Management

Definition:
Connection to Index Coding