pith. sign in

arxiv: 1907.01133 · v1 · pith:WD7ZF7BGnew · submitted 2019-07-02 · 💻 cs.IT · math.IT

A Local Perspective on the Edge Removal Problem

Fei Wei , Michael Langberg , Michelle Effros This is my paper

Pith reviewed 2026-05-25 11:16 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords edge removalnetwork codingrate vectorsencoding functionslocal conditionsachievable rates
0
0 comments X

The pith

Sufficient conditions on the encoding function of one removed edge allow proving achievability of a related rate vector after removal.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The edge removal problem studies how much network coding rates drop when one edge is taken out. The paper shifts from global restrictions such as linearity on every encoding function to a local view that constrains only the function on the removed edge. It supplies sufficient conditions on that single function under which a nearby rate vector remains achievable once the edge is gone. This widens the set of codes for which the known bound on rate loss continues to hold. A reader cares because the result isolates when rate preservation depends on local properties rather than network-wide coding constraints.

Core claim

Our central results give sufficient conditions on the function carried by edge e* in the code used to achieve a particular rate vector under which we can demonstrate the achievability of a related rate vector once e* is removed.

What carries the argument

The sufficient local conditions on the encoding function carried by the single removed edge e*.

If this is right

  • The known bound on rate loss after edge removal holds whenever the removed edge satisfies the local conditions.
  • The edge-removal statement applies to strictly larger families of encoding functions than linear or Abelian-group codes.
  • Rate achievability arguments can be completed locally on one edge without re-deriving global code properties.
  • The result applies directly to any network in which an edge carrying a qualifying function is removed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The local lens might simplify proofs for rate preservation in time-varying or adversarial networks where global linearity cannot be assumed.
  • One could test whether the same conditions suffice for multicast or multi-source settings beyond the unicast cases implicitly covered.
  • The approach suggests examining other network problems, such as edge addition or capacity scaling, through analogous local function constraints.

Load-bearing premise

The local conditions on the function of e* are sufficient to carry the rate-achievability argument through the rest of the network without additional global restrictions on other edges.

What would settle it

A concrete network, rate vector, and function on e* that meets the stated local conditions yet fails to achieve any related rate vector after e* is removed would falsify the central claim.

Figures

Figures reproduced from arXiv: 1907.01133 by Fei Wei, Michael Langberg, Michelle Effros.

Figure 1
Figure 1. Figure 1: An example depicting the proof of Lemma 4. The dark blocks 1 [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The network N3 and coding scheme from [14]. Figure taken from [14]. For network C we set the linear encoding functions to be: e16,20 = c + d + e e26,34 = c + d e27,35 = c + e e28,36 = d + e It now follows that the demands are met: n40 : c =t(e19,40 − e31,40) = t(a + b + t(c) − (a + b)) n41 : b =e19,41 − e32,41 = a + b + t(c) − (a + t(c)) n42 : a =e19,42 − e33,42 = a + b + t(c) − (b + t(c)) n43 : c =(e33,43… view at source ↗
Figure 3
Figure 3. Figure 3: The network N from [15] with corresponding notation used in our analysis. The Figure is taken from [15]. variables U1, U2, U3, U4, such that h(1) = h(2) = h(3) = h(4) = log 13 h(1, 2) = log 6 + log 13 h(3, 4) = log 13 + log 12 h(1, 3) = h(1, 4) = h(2, 3) = h(2, 4) = log 13 + log 4 h(i, j, k) = log 13 + log 12 = h(1, 2, 3, 4), ∀distinct i, j, k. It is easy to show that h violates the Ingleton inequality. [1… view at source ↗
Figure 4
Figure 4. Figure 4: The building block B(m) from [16] with the corresponding notation used in our analysis. The figure is taken from [16]. non-linearly solvable network N4(m) is constructed by taking a disjoint union of component networks N1(m), N2(m, w), N3(m1, m2) with carefully chosen parameters. The later net￾works, in turn, are constructed from a certain building block B(m), see [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
read the original abstract

The edge removal problem studies the loss in network coding rates that results when a network communication edge is removed from a given network. It is known, for example, that in networks restricted to linear coding schemes and networks restricted to Abelian group codes, removing an edge e* with capacity Re* reduces the achievable rate on each source by no more than Re*. In this work, we seek to uncover larger families of encoding functions for which the edge removal statement holds. We take a local perspective: instead of requiring that all network encoding functions satisfy certain restrictions (e.g., linearity), we limit only the function carried on the removed edge e*. Our central results give sufficient conditions on the function carried by edge e* in the code used to achieve a particular rate vector under which we can demonstrate the achievability of a related rate vector once e* is removed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript examines the edge removal problem in network coding. It seeks to identify larger families of encoding functions (beyond linear and Abelian group codes) for which removing an edge e* of capacity R_{e*} reduces each source rate by at most R_{e*}. The central contribution is a local perspective: the authors derive sufficient conditions on the encoding function carried specifically by the removed edge e* (in a code achieving a given rate vector) under which a related rate vector remains achievable after edge removal, without imposing global restrictions on other edges.

Significance. If the derived conditions are non-vacuous and the sufficiency arguments hold, the local approach meaningfully extends the known edge-removal guarantees to broader classes of functions while preserving the rate-loss bound. The constructive, function-specific nature of the conditions is a clear strength relative to global linearity or group-code restrictions.

minor comments (2)
  1. The abstract asserts the existence of sufficient conditions but does not preview the form of those conditions or the key technical steps; a one-sentence characterization in the abstract would improve accessibility.
  2. Notation for the related rate vector after edge removal is introduced without an explicit equation reference in the provided abstract; ensure the first appearance is tied to a numbered display equation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper states a constructive result: it supplies sufficient local conditions on the encoding function of a single edge e* such that a related rate vector remains achievable after removal. This is a direct proof of sufficiency under the stated premises rather than a claim that reduces by construction to its own inputs, a fitted parameter, or a self-citation chain. The work explicitly builds on externally known results for linear codes and Abelian group codes; no load-bearing uniqueness theorem or ansatz is imported from the authors' prior work. The central claim is therefore independent of the result it proves.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard network-coding setup (directed graph, edge capacities, rate vectors) and on the known edge-removal bounds for linear and Abelian-group codes; no free parameters, invented entities, or ad-hoc axioms are visible in the abstract.

axioms (1)
  • domain assumption Standard directed-graph network model with capacity-constrained edges and achievable rate vectors
    Invoked when the edge-removal problem is defined and when the local conditions are stated to preserve achievability.

pith-pipeline@v0.9.0 · 5668 in / 1158 out tokens · 24632 ms · 2026-05-25T11:16:38.067975+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    On equivalence between network topologies,

    T. Ho, M. Effros, and S. Jalali, “On equivalence between network topologies,” in IEEE Allerton Conference on Communication, Control, and Computing, 2010, pp. 391–398

    work page 2010

  2. [2]

    On the impact of a single edge on the network coding capacity,

    S. Jalali, M. Effros, and T. Ho, “On the impact of a single edge on the network coding capacity,” in IEEE Information Theory and Applications Workshop, 2011, pp. 1–5

    work page 2011

  3. [3]

    Network coding: Is zero error always possible?

    M. Langberg and M. Effros, “Network coding: Is zero error always possible?” in IEEE Allerton Conference on Communication, Control, and Computing, 2011, pp. 1478–1485

    work page 2011

  4. [4]

    On a capacity equivalence between network and index coding and the edge removal problem,

    M. F. Wong, M. Langberg, and M. Effros, “On a capacity equivalence between network and index coding and the edge removal problem,” in IEEE International Symposium on Information Theory (ISIT) , 2013, pp. 972–976

    work page 2013

  5. [5]

    Outer bounds and a functional study of the edge removal problem,

    E. J. Lee, M. Langberg, and M. Effros, “Outer bounds and a functional study of the edge removal problem,” in IEEE Information Theory Workshop, 2013, pp. 1–5

    work page 2013

  6. [6]

    On an equivalence of the reduction of k-unicast to 2-unicast capacity and the edge removal property,

    M. F. Wong, M. Effros, and M. Langberg, “On an equivalence of the reduction of k-unicast to 2-unicast capacity and the edge removal property,” in IEEE International Symposium on Information Theory (ISIT), 2015, pp. 371–375

    work page 2015

  7. [7]

    On tightness of an entropic region outer bound for network cod- ing and the edge removal property,

    ——, “On tightness of an entropic region outer bound for network cod- ing and the edge removal property,” in IEEE International Symposium on Information Theory (ISIT) , 2016, pp. 1769–1773

    work page 2016

  8. [8]

    The effect of removing a network commu- nication edge: group network codes,

    F. Wei and M. Langberg, “The effect of removing a network commu- nication edge: group network codes,” in IEEE Allerton Conference on Communication, Control, and Computing , 2017

    work page 2017

  9. [9]

    On achievable rate regions for source coding over networks,

    W. Gu, “On achievable rate regions for source coding over networks,” Ph.D. dissertation, California Institute of Technology, 2009

    work page 2009

  10. [10]

    On the relationship between edge removal and strong converses,

    O. Kosut and J. Kliewer, “On the relationship between edge removal and strong converses,” in IEEE International Symposium on Information Theory (ISIT), 2016, pp. 1779–1783

    work page 2016

  11. [11]

    Two-unicast is hard,

    S. Kamath, N. David, and C.-C. Wang, “Two-unicast is hard,” in IEEE International Symposium on Information Theory (ISIT), 2014, pp. 2147– 2151

    work page 2014

  12. [12]

    Network coding capacity regions via entropy functions,

    T. H. Chan and A. Grant, “Network coding capacity regions via entropy functions,” IEEE Transactions on Information Theory , vol. 60, no. 9, pp. 5347–5374, 2014

    work page 2014

  13. [13]

    A characterization of the capacity region for network coding with dependent sources,

    W. Kim, M. Langberg, and M. Effros, “A characterization of the capacity region for network coding with dependent sources,” in IEEE International Symposium on Information Theory (ISIT), 2016, pp. 1764– 1768

    work page 2016

  14. [14]

    Insufficiency of linear coding in network information flow,

    R. Dougherty, C. Freiling, and K. Zeger, “Insufficiency of linear coding in network information flow,”IEEE Transactions on Information Theory, vol. 51, no. 8, pp. 2745–2759, 2005

    work page 2005

  15. [15]

    Dualities between entropy functions and network codes,

    T. Chan and A. Grant, “Dualities between entropy functions and network codes,” IEEE Transactions on Information Theory , vol. 54, no. 10, pp. 4470–4487, 2008

    work page 2008

  16. [16]

    A class of non-linearly solvable networks,

    J. Connelly and K. Zeger, “A class of non-linearly solvable networks,” IEEE Transactions on Information Theory , vol. 63, no. 1, pp. 201–229, 2017

    work page 2017

  17. [17]

    Lexicographic products and the power of non-linear network coding,

    A. Blasiak, R. Kleinberg, and E. Lubetzky, “Lexicographic products and the power of non-linear network coding,” in IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS) , 2011, pp. 609–618

    work page 2011

  18. [18]

    R. W. Yeung, Information theory and network coding. Springer Science & Business Media, 2008

    work page 2008

  19. [19]

    good” and elements in Gi\S(k′) i “bad

    J. Gallian, Contemporary abstract algebra . Cengage Learning, 2016. APPENDIX I. P ROOF OF COROLLARY 2 We apply the model and definitions from [8]. Proof of Corollary 2. We show that for any edgee∗∈E there exists a random variable Y which satisfies all three conditions in Theorem 1, which implies that the edge removal statement holds onI. By Theorem 4 proven...

    work page 2016

  20. [20]

    that we can modify the code of [16] and make the global encoding function φge CWL

    work page

  21. [21]

    Subnetwork: N1(m): In the coding scheme of [16] all edges in N1(m) have a linear global encoding function

    work page

  22. [22]

    From the expressions we notice that the edge message e(l) 0 is a linear function of source messages

    Subnetwork: N2(m,w ): By Lemma IV .4 of [16], a solution for N2(m,w ) is given as a single blocklength code over the ring Zmw for each l = 1, 2,...,w by e(l) 0 = m+1∑ j=1 x(l) j , e(l) i =πl(z)+ m+1∑ j=1,j̸=i x(l) j (i = 1, 2,...,m + 1), e(l) =πl(z)+ m+1∑ j=1 x(l) j . From the expressions we notice that the edge message e(l) 0 is a linear function of sour...

    work page

  23. [23]

    By the encoding functions given above, we know for l = 1, 2 thate(l) 0 is a linear function of source messages

    Subnetwork: N3(m1,m 2): By Lemma V .4 of [16], a solution for N3(m1,m 2) (m1 =m and m2 =smα) is given as a single blocklength code over the ring Zmα+1 for each l = 1, 2 by e(l) 0 = ml∑ j=1 x(l) j , e(l) i =πl(z)+ ml∑ j=1,j̸=i x(l) j (i = 1, 2,...,m + 1), e(l) =πl(z)+ ml∑ j=1 x(l) j . By the encoding functions given above, we know for l = 1, 2 thate(l) 0 i...

    work page