A new proof that the multiple-unicast conjecture holds for networks with at most six coding nodes, without computer-aided search, is given, and it is shown that if the conjecture holds on $\Gamma_{3,3}$, then it holds whenever no three sessions have six distinct terminal locations.
Abstract
Network coding allows intermediate nodes to encode received messages before transmission. The multiple-unicast conjecture asserts that coding has no throughput advantage over fractional routing for independent unicast sessions in any undirected network. Despite more than two decades of sustained study, this central open problem remains unresolved. The conjecture is deeply connected to computational complexity: a proof would yield long-sought lower bounds for fundamental problems. To study the conjecture, this paper develops a unified metric framework from the perspective that the basic objects behind the comparison between coding and routing are not cuts alone, but graph metrics. Using this framework, we prove the conjecture for three new classes of undirected networks: (a) networks with at most five terminal locations; (b) planar networks whose terminal locations lie on the boundaries of at most three designated faces, with each session's endpoints on one such face; and (c) networks with arbitrarily many nodes and terminal locations under a structural restriction on session endpoints. We give a new proof that the conjecture holds for networks with at most six coding nodes, without computer-aided search, and show that if the conjecture holds on $\Gamma_{3,3}$, then it holds whenever no three sessions have six distinct terminal locations.
Entanglement-based networks provide a scalable framework for multiuser quantum communication by passively routing spectrally correlated photon pairs across interconnected nodes. Several wavelength-allocation schemes have been demonstrated experimentally, but these designs do not yet give a general way to determine how spectral use, receiver load, repeated connections, and fan-out constrain one another. We address this problem through the network's connectivity graph, where the wavelength assignment becomes a resource-optimization problem. For one-sided fan-out, assigning each link to a center and grouping links with the same center gives an exact optimization for arbitrary networks and fan-out limits. We solve this for complete networks and for complete networks in which every user has one excluded partner. Allowing both conjugate wavelengths to fan out changes the resource landscape: a balanced binary hierarchy attains the minimum spectral-layer count for a complete network while reducing the maximum receiver load to logarithmic in the number of users. An eight-user complete network then makes explicit the competing roles of spectral efficiency, receiver load, redundancy, and fan-out. We include the passive-splitter loss and the dependence of the key rate on the delivered pair flux to determine the minimum total pair-generation rate required to meet the prescribed targets. Finally, we formulate the corresponding BBM92 quantum key distribution (QKD) secret-key-rate analysis for a continuous-wave-pumped broadband source, with true and accidental coincidences evaluated between detector channels at the two endpoint users and relative layer pair-generation rates fixed by the source spectrum. This framework, therefore, provides a direct route from exact network resource laws to the design and comparison of passive entanglement architectures under experimentally specified hardware constraints.
Ekta Panwar, Gilberto Borges, Saeide Salari et al.· 0 citations
Wireless multi-hop networks rely on a subset of nodes to relay traffic, broadcast control messages, and maintain global connectivity without requiring every device to forward packets. A virtual backbone formalizes this idea by selecting a sparse set of representative nodes that can cover the network and serve as a routing substrate. In graph terms, given a general communication graph G = (V,E), the backbone is often modeled as a connected dominating set (CDS): a subset S ⊆ V such that every node in V \S has a neighbor in S, and the subgraph induced by S is connected. CDS-based backbones reduce routing overhead but are NP-hard to compute and must balance sparsity, coverage, and connectivity. Here we introduce a quantum approach to solving the CDS problem based on the cyclic quantum annealing algorithm, suitable for current digital quantum computers, which we call Digitized Cyclic Annealing. We explore the dependence of the obtained solutions on the algorithm hyperparameters and show how transfer learning allows us to find their values for large-scale problems. We demonstrate the complete algorithm on a network optimization problem using N = 73 qubits on an IBM Kingston quantum processor.
M. Grandadam, M. Koch-Janusz· International Conference on...· 0 citations
The results support HON as a simple low-degree construction for structured inter-group communication, whereas higher-radix, adaptive, or more richly connected fabrics remain better suited to less structured traffic and larger bandwidth demand.
Han Ni Soe, Yao Zhang, Zhipeng Xu· Parallel Processing Letters· 0 citations
In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally alters the problem, making it significantly more challenging than its classical counterpart. We focus on the fairness notion of $\mathrm{EF1}_{\mathrm{outer}}$, where envy can be eliminated by removing at most one vertex whose deletion does not disconnect the bundle -- a critical constraint for applications such as land division and network allocation. Our first result extends prior work by establishing the existence of $\mathrm{EF1}_{\mathrm{outer}}$ allocations for an infinite family of non-traceable graphs (that is, graphs that do not admit a Hamiltonian path), answering a central open question and generalizing Bil\`o et al.'s result for traceable graphs. We then make progress on a conjecture concerning the $\mathrm{EF1}_{\mathrm{outer}}$ spectrum of trees due to Chen and Zwicker. Finally, we complement our structural results with algorithmic insights, showing that deciding the existence of an $\mathrm{EF1}_{\mathrm{outer}}$ allocation is NP-complete even for binary additive valuations, thereby resolving an open complexity question. Taken together, our results deepen the connection between graph theory and fair division, and offer new tools for studying fairness in structured resource environments.
Nicolas Bousquet, Frank Connor, Agnes Totschnig et al.· 0 citations
As practical quantum networks approach large-scale deployment, the need for efficient user-to-user frequency allocation is increasing, yet current approaches only provide partial solutions to the routing and spectrum allocation problem for an arbitrary quantum network. We address this challenge for repeater-less flex-grid quantum networks based on hyperentangled photons using an efficient three-stage pipeline combining leading tools in classical networking with recent advances in numerical optimization. First, double instantiations of Yen's algorithm obtain low-loss route candidates between each pair of users and the entanglement sources. Second, the advanced process optimizer (APOPT) obtains frequency channel allocations that maximize distribution rates under fidelity constraints. Finally, the constraint programming solver using satisfiability methods (CP-SAT) assigns specific frequency bins to each link, ensuring that there is no contention between frequencies from different sources. We numerically demonstrate this approach on a representative ring network and a Manhattan incumbent local exchange carrier topology, realizing significant improvements over prior genetic algorithm approaches in speed, accuracy, and scalability. Overall, this pipeline provides an efficient heuristic workflow for optimizing broadband entanglement distribution, applicable to arbitrarily connected quantum networks integrated within the existing lightwave infrastructure.
Zachary Goisman, M. L. Stevens, Maxwell Goisman et al.· 0 citations
The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to terminals with unrelated demands, each terminal being served through a single path. The classical SSUF objective is to minimize the violation of some given arc capacities. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. Intriguingly, there are arguably no non-trivial graph classes for which it is known to hold. We show that a slight weakening of it holds for planar graphs, by exploiting a connection to a highly structured discrepancy problem. Moreover, our techniques extend to simultaneous upper and lower bounds on the flow values. This affirmatively answers a conjecture of Morell and Skutella for planar SSUF. Finally, we show that our approach can be extended to general (non-planar) graphs with a capacity violation that depends on the genus.
Vera Traub, Laura Vargas Koch, R. Zenklusen· Mathematical programming· 0 citations