Coding in undirected graphs is either very helpful or not helpful at all

Mark Braverman, Sumegha Garg, Ariel Schvartzman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured in [11] that the answer is 'no'. In this paper we show that even a small advantage over MCF can be amplified to yield a near-maximum possible gap. We prove that any undirected network with k source-sink pairs that exhibits a (1 + ϵ) gap between its MCF rate and its network coding rate can be used to construct a family of graphs G0 whose gap is log(|G'|)c for some constant c < 1. The resulting gap is close to the best currently known upper bound, log(|G'|), which follows from the connection between MCF and sparsest cuts. Our construction relies on a gap-Amplifying graph tensor product that, given two graphs G1,G2 with small gaps, creates another graph G with a gap that is equal to the product of the previous two, at the cost of increasing the size of the graph. We iterate this process to obtain a gap of log(|G'|)c from any initial gap.

Original languageEnglish (US)
Title of host publication8th Innovations in Theoretical Computer Science Conference, ITCS 2017
EditorsChristos H. Papadimitriou
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770293
DOIs
StatePublished - Nov 1 2017
Event8th Innovations in Theoretical Computer Science Conference, ITCS 2017 - Berkeley, United States
Duration: Jan 9 2017Jan 11 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume67
ISSN (Print)1868-8969

Other

Other8th Innovations in Theoretical Computer Science Conference, ITCS 2017
CountryUnited States
CityBerkeley
Period1/9/171/11/17

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Gap Amplification
  • Multicommodity flows
  • Network coding

Fingerprint Dive into the research topics of 'Coding in undirected graphs is either very helpful or not helpful at all'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Garg, S., & Schvartzman, A. (2017). Coding in undirected graphs is either very helpful or not helpful at all. In C. H. Papadimitriou (Ed.), 8th Innovations in Theoretical Computer Science Conference, ITCS 2017 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 67). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2017.18