Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 17 min ago
PreprintarXiv licencearXiv

Routing Optimality for Demand Graphs of Matching Number at Most Two

  • Xiaohong Cai
  • Yulin Chen
Open at sourcePDFDOICite

Abstract

We prove that network coding and fractional routing have the same capacity region in undirected networks whose demand graph has matching number at most two, that is, when no three demand edges have pairwise disjoint endpoints. The metric-packing reduction of Liu et al. reduces this problem to a distance-weighted communication inequality on the fixed graph Γ3,3. We first prove two entropy inequalities for sessions between designated terminal pairs on Γ3,3. We then extend this result to sessions with arbitrary endpoints to obtain the distance-weighted communication bound required by the reduction. The proof combines conditional entropy inequalities with two graph contractions and an information inequality for deterministic interaction. Combining this inequality with the existing reduction establishes routing optimality for this class of demand graphs.

Related

  1. Edge ideals of gapfree graphs with matching number $3$
    Nursel Erey, Tài Huy Hà, Takayuki Hibi +2
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. The maximum number of edges in minimal matching covered graphs
    Xiaoling He
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Linear resolutions of powers of edge ideals of gap-free graphs with matching number four
    Luis Alfredo Dupont García
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Sim-Width, Induced Matching Treewidth, and Tree-Independence Number in Induced Kt,t-Free Graphs
    Mengyuan Niu, Xiumei Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Regularity of the Price of Anarchy in Routing Games over the Multivariate Demand Space
    Jiawen Wang, Hu Shao, Ting Wu
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{cai2026routing,
  title = {{Routing Optimality for Demand Graphs of Matching Number at Most Two}},
  author = {Xiaohong Cai and Yulin Chen},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.17911},
  eprint = {2610.17911},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17911},
}
RIS
TY  - UNPB
TI  - Routing Optimality for Demand Graphs of Matching Number at Most Two
AU  - Xiaohong Cai
AU  - Yulin Chen
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.17911
UR  - https://arxiv.org/abs/2610.17911
AB  - We prove that network coding and fractional routing have the same capacity region in undirected networks whose demand graph has matching number at most two, that is, when no three demand edges have pairwise disjoint endpoints. The metric-packing reduction of Liu et al. reduces this problem to a distance-weighted communication inequality on the fixed graph Γ_3,3. We first prove two entropy inequalities for sessions between designated terminal pairs on Γ_3,3. We then extend this result to sessions with arbitrary endpoints to obtain the distance-weighted communication bound required by the reduction. The proof combines conditional entropy inequalities with two graph contractions and an information inequality for deterministic interaction. Combining this inequality with the existing reduction establishes routing optimality for this class of demand graphs.
ER  -