Optical networks send many small traffic streams over a few high-capacity wavelengths. Each wavelength that starts or ends at a node needs an expensive electronic multiplexer there. Choosing which streams share which wavelength, so that this hardware count is small, is called traffic grooming, and it is NP-complete even on a simple line of nodes. The only algorithms with provable cost guarantees work on lines, rings, stars and trees. Real backbones such as Abilene and GÉANT are irregular meshes. For them, practitioners fall back on metaheuristics with no guarantees, or would reach for learned graph policies, which are known to transfer poorly across topologies with different structure.
This note proposes one move that addresses both problems. The best line-and-ring algorithm cuts the network in the middle and groups the traffic paths that cross the cut into "edge instances": sets of paths that all share one link. We generalize the cut from a single middle link to a small balanced separator of an arbitrary graph. We conjecture that the approximation ratio then scales with the separator width times the recursion depth, rather than with anything specific to lines or rings. The same move helps learning. An edge instance has the same combinatorial form whether it came from a chain or from GÉANT, so a solver trained on edge instances meets no topology shift at deployment. Running it alongside the classical solver and keeping the cheaper answer preserves the worst-case guarantee.
Background and the gap
The Traffic Grooming Problem in Optical Networks with Respect to ADMs and OADMs supplies the method we build on. That paper proves grooming NP-complete on chains with grooming factor $g=2$ via a reduction from TRIPART, where $g$ is how many low-rate streams fit on one wavelength. Its MERGE meta-algorithm turns any $r$-approximation for edge instances into an $r\lceil\log n\rceil$-approximation on chains and an $r(\lceil\log n\rceil+1)$-approximation on rings. It also gives GROOM, a $2\sqrt{g}$-approximation for edge instances. The paper stops at one-dimensional topologies. Approximating the traffic grooming problem in tree and star networks handles stars and trees and finds that stars are polynomial for grooming factor $C\le 2$ and NP-complete above.
Together these results raise an unexplained tension. The factor-2 case is easy on the diameter-2 star but hard on the pathwidth-1 chain, and nothing in the literature says which graph parameter controls difficulty or approximability. Metaheuristic Approaches to Traffic Grooming in WDM Optical Networks motivates the proposal from the practical side. It reports that ring-specific constructions fail on general meshes and that genetic, tabu and annealing methods work but carry no bounds.
Learned allocators constrain the design. Resource Allocation via Graph Neural Networks in FSO Fronthaul Networks trains a graph neural network (a model that computes node decisions by repeatedly aggregating information from neighbors) with primal-dual learning. It shows scaling only from 5 to 10 radio heads on one bipartite layout, and it models no wavelength packing. The graphon transfer theory of Transferability Properties of Graph Neural Networks and Graph Neural Networks: Architectures, Stability, and Transferability bounds transfer error only between graphs drawn from the same dense limit. Within that regime the result is mild: MovieLens rating error rises from 0.829 to 0.873 when a model trained on 118 nodes runs on 1,682. Sparse optical meshes and chains are not drawn from a common dense limit. Evidence from Chauhan et al. and Trovò et al. shows that methods tuned to one degree regime break in another. We therefore do not try to make a whole-graph policy transfer. We change what the learned component sees.
Core Claim
Fix the routes of all demands, as MERGE does. Let a balanced separator of a network be a small set of links whose removal splits the graph into pieces of at most a constant fraction of the nodes. Suppose the graph admits a recursive hierarchy of such separators, each of at most $s$ links, with depth $D$. At each level, assign every path crossing the separator to the first separator link it uses. This partitions the crossing paths into at most $s$ edge instances. Every path is handled exactly once, at the highest level where it is cut.
We conjecture, and will try to prove, a generalization of the MERGE bound: the resulting grooming costs at most
$$\text{ALG} \le r \cdot s \cdot D \cdot \text{OPT},$$
where $r$ is the edge-instance approximation ratio and OPT is the optimal combined multiplexer cost. The form comes from MERGE's charging argument. On a chain, each level's edge instance costs at most $r$ times OPT's restriction to it, and restrictions at one level do not overlap. The new ingredient is that a separator of width $s$ produces up to $s$ instances per level, each chargeable to OPT, which multiplies the bound by $s$.
Chains have $s=1$ and $D=\lceil\log n\rceil$, recovering MERGE. Graphs of treewidth $k$ have separators of size $O(k)$, which would give $O(k\sqrt{g}\log n)$ with GROOM. The main risk is that edge-instance restrictions of OPT can share multiplexers at common endpoints across the $s$ instances. The proof must show this overlap costs at most a constant factor. If it cannot, a weaker $s^2$ dependence is the fallback result.
The learning claim is secondary but concrete. An edge instance is a set of intervals on its path structure plus a grooming factor, and its form does not depend on the host graph. A solver trained only on chain-derived edge instances should therefore perform equally well on edge instances drawn out of GÉANT. We run it in parallel with GROOM and keep the cheaper answer per instance. The end-to-end guarantee is therefore never worse than with GROOM alone, whatever the learned model does.
Research Program
The theoretical part has three pieces. First, attempt the charging proof above for separator-based MERGE, including the ring-style correction for paths that wrap around. Second, state the resulting bound for bounded-treewidth graphs and for planar backbones, whose separators have size $O(\sqrt{n})$. Third, test whether the parameter $s$ explains the star-versus-chain tension. Stars have diameter 2 but only one high-degree node, so every separator is trivial, and edge instances there are unusually structured. We expect this to show that factor-2 tractability on stars comes from edge-instance structure, not separator width, which is a falsifiable hypothesis about Gap 3.
The algorithmic part builds the decomposition pipeline. It computes separators with standard graph partitioning heuristics and uses the certified width $s$ as reported. It then runs GROOM for multiplexer cost and GROOM-OADM for optical add-drop cost on each edge instance.
The learned part trains a permutation-invariant model on edge instances with the weighted cost $a\cdot\text{ADM}+(1-a)\cdot\text{OADM}$ as reward, using the primal-dual constraint handling of Gao et al. to enforce the capacity limit $g$. It is trained only on instances from random chains.
Baselines
The naive reference point assigns every demand its own wavelength. This is the trivial upper bound on multiplexer cost, and every method must be reported as a fraction of it.
The strongest classical competitor on quality is the metaheuristic family surveyed by Xu et al.: genetic algorithm, tabu search and simulated annealing with traffic-matrix operators. They are the best-known practical methods on general meshes. We give them the same wall-clock budget as our full pipeline, and also a tenfold budget to expose the quality ceiling. We tune them on the same held-out chain and small-mesh instances used to tune our model.
The strongest method with guarantees is MERGE itself applied to a spanning tree or a chosen Hamiltonian-like path of the mesh, with routes re-embedded. This is what a practitioner would do today to obtain some guarantee on a mesh.
The exact reference is a mixed-integer program solved to optimality on instances up to a few dozen nodes, with its LP relaxation serving as a lower bound on larger ones.
There is no reported result found on Lacuna for multiplexer counts on Abilene, GÉANT or SNDlib grooming instances. The only nearby figure is SR-TSP reaching "within 8.23% of the mathematical optimum" in On Routing Optimization in Networks with Embedded Computational Services, which is a different, continuous-capacity problem, so we generate our own reference numbers.
Two ablations isolate the key ingredients. The first is an end-to-end graph neural network trained on whole chain-and-ring grooming instances and deployed directly on meshes. It tests whether decomposition, rather than learning capacity, is what buys transfer. The second is separator-MERGE with GROOM only and no learned solver. It tests whether learning adds anything at all.
Beating the baselines means the following. Against metaheuristics, the pipeline must come within a few percent of their cost at equal time while retaining its bound. Against spanning-tree MERGE, it must show lower cost on meshes and a tighter certified ratio. The learned plug-in counts as useful only if it lowers mean edge-instance cost relative to GROOM on mesh-derived instances it never saw.
Why not just…?
Why not just run genetic algorithms or tabu search on each mesh? They are a real threat on solution quality, and Xu et al. report that they beat greedy methods. They offer no bound and must be rerun whenever traffic changes. The equal-budget and tenfold-budget comparisons will show how much quality, if any, the certified pipeline gives up. If metaheuristics win by a wide margin, the contribution narrows to the approximation theorem, and we would report that plainly.
Why not just solve an LP relaxation and round? Multiplexer cost is a step function: a wavelength costs the same whether it carries one stream or $g$. Rounding fractional wavelengths can therefore multiply cost, and Ni et al. show that the related circular rebalancing problem in payment channel networks is not approximable within a constant ratio (Utility-aware Payment Channel Network Rebalance). We still compute the LP as a lower bound and include randomized rounding as a baseline, so its integrality gap on real backbones is measured rather than assumed.
Why not just train a graph neural network on whole networks and rely on transfer? Graphon transfer guarantees require a shared dense limit, which chains and sparse WANs lack. Methods tuned to one degree regime are documented to fail on others. The end-to-end ablation tests this directly on the chain-to-mesh shift.
Why not just skip learning and use GROOM inside the decomposition? This may be enough, and the design accepts that. The theorem does not depend on learning, and the learned solver is a guarded plug-in. If it fails to beat GROOM on mesh-derived instances, we drop it.
Proposed Experiments
The instances are the Abilene and GÉANT topologies (as used by Mei et al.) and SNDlib networks, with gravity-model demand matrices at several grooming factors $g\in\{2,4,8,16\}$ and cost weights $a\in\{0.25,0.5,0.75\}$. Routes are fixed as shortest paths. Controlled synthetic families include $k\times n$ grids and ring-of-rings graphs, which let separator width vary independently of size.
Metrics are weighted hardware cost normalized by the MIP optimum on small instances and by the LP lower bound on large ones, together with runtime and the certified ratio $r\cdot s\cdot D$.
Three checks decide the project. First, on the synthetic families, the empirical cost ratio should grow with separator width $s$ and only logarithmically with $n$. If it tracks $n$ instead, the width-based account is wrong. Second, the learned edge solver, trained only on chain instances, should show no measurable gap between chain-derived and GÉANT-derived test instances. The end-to-end network should show a clear gap on the same shift. Third, on Abilene, GÉANT and SNDlib, separator-MERGE should beat spanning-tree MERGE on both measured cost and certified ratio, and should stay close to equal-budget metaheuristics.
References
- The Traffic Grooming Problem in Optical Networks with Respect to ADMs and OADMs: Complexity and Approximation
- Approximating the traffic grooming problem in tree and star networks
- Metaheuristic Approaches to Traffic Grooming in Wdm Optical Networks
- Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networks
- Transferability Properties of Graph Neural Networks
- Graph Neural Networks: Architectures, Stability and Transferability
- Approximating optimization problems using EAs on scale-free networks
- Unimodal Thompson Sampling for Graph-Structured Arms
- On Routing Optimization in Networks With Embedded Computational Services
- Utility-aware Payment Channel Network Rebalance