{"id":"arxiv/2601.11419","url":"https://arxiv.org/abs/2601.11419","tags":["cs.DM","math.OC"],"score":0,"title":"On the Virtual Network Embedding polytope","domain":"cs.DM","source":"arxiv","authors":["Amal Benhamiche","Pierre Fouilhoux","Lucas Létocart","Nancy Perrot","Alexis Schneider"],"reviews":0,"subject":"cs.DM","summary":"We initiate the polyhedral study of the Virtual Network Embedding (VNE) problem, which arises in modern telecommunication networks. We propose new valid inequalities for the so-called flow formulation. We then prove, through a dedicated flow decomposition algorithm, that these inequalities characterize the VNE polytope in the case of an embedding of a virtual edge on a substrate path. Preliminary experiments show that the new inequalities propose promising speedups for MIP solvers.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-16","reactions":{}}