On the Multiple-Unicast Conjecture: Session Dominance

Abstract

In the field of network coding, the longstanding and fundamental multiple-unicast conjecture states that for independent unicast sessions in an undirected network, network coding offers no throughput advantage over routing. Despite its significance, this conjecture remains unresolved for over two decades, and has recently witnessed deep connections to core problems in computational complexity. Existing approaches, based on multicommodity flows, information inequalities, and geometric embeddings, have succeeded in verifying the conjecture for restricted network classes only.We introduce a new session dominance framework, whose core principle establishes that if the conjecture holds for a particular set of sessions, it must also hold for another, dominated set. This new perspective leads to: (1) unified proofs for known results; (2) a sufficient condition in the cost domain for the conjecture to hold on arbitrary undirected networks with three unicast sessions; (3) a new, equivalent formulation of the conjecture; and (4) a proof to the conjecture on a significant new network class defined solely by topological conditions—with no restrictions on network size or link capacities. The goal is to establish a new pathway toward resolving this important and longstanding open problem.