Capacity Factors of a Point-to-point Network

Yuan Li, Yue Zhao, Haibin Kan

Abstract

In this paper, we investigate properties of capacity factors (CF), which are used to analyze link failure problems in network coding. A capacity factor of a network is a minimal edge set whose deletion reduces the maximum flow. We characterize edges contained in some CF in acyclic point-to-point networks and propose an efficient $O(V^3)$ algorithm for their classification. We prove that all edges on any $s$-$t$ path in such networks are contained in some 2-CF. Furthermore, we establish that determining the existence of a capacity factor of at least a given size in a cyclic network is NP-complete. Finally, we introduce vertex capacity factors and show they generalize the edge-based definition.

Introduction

In traditional network reliability analysis, the primary concern is often connectivity: "Does a path still exist between two nodes?" However, in the context of network coding, the focus shifts from simple connectivity to capacity. Even if a path remains after a link failure, the total throughput (max-flow) may degrade, impacting the efficiency of the entire system.

This paper explores the concept of a Capacity Factor (CF)— a minimal set of edges whose removal reduces the network's max-flow. Unlike a minimum cut, which is the smallest set of edges to disconnect a graph, a CF is minimal in the sense that removing any proper subset of it would not reduce the capacity. This study provides a theoretical framework for identifying critical links and understanding the "Capacity Rank" of network components.

Characterizing Critical Edges: The D-set and H-set

A central contribution of this work is the classification of edges into two categories: the D-set (edges belonging to at least one CF) and the H-set (edges that do not affect capacity). In acyclic networks, an edge belongs to the D-set if and only if it is part of some maximum flow configuration.

A point-to-point acyclic network illustrating the structure used to analyze how edge failures (capacity factors) impact total throughput.

To identify these edges, the authors propose an efficient $O(V^3)$ algorithm. This algorithm leverages the "relabel-to-front" max-flow technique and cycle detection within residual graphs to partition the network's edges. This allows researchers to quickly determine which links are truly "critical" to maintaining full bandwidth.

The Ubiquity of 2-Order Capacity Factors

One of the paper's most striking findings is the "2-CF" property. The authors prove that in any acyclic point-to-point network with a max-flow greater than 1, every edge on any $s$-$t$ path is contained in some 2-order Capacity Factor. This implies that network capacity is remarkably fragile; one only needs to lose two specific edges to see a drop in performance, regardless of how many other paths might exist. This result highlights the importance of protecting specific pairs of links rather than just focusing on single-point failures.

Computational Hardness and Complexity

While identifying whether an edge is critical is computationally efficient, finding the largest possible minimal set of edges that reduces capacity—the Maximum Capacity Factor (MCF) problem—is proven to be NP-complete. The authors demonstrate this through a reduction from the NAESAT (Not-All-Equal Satisfiability) problem.

Additionally, the paper establishes that calculating the Capacity Rank of an edge (the size of the smallest CF containing it) is at least as difficult as solving the maximal flow problem itself. These results suggest a fundamental asymmetry: it is easy to find if a link is important, but difficult to find the worst-case scenario for capacity degradation in complex or cyclic topologies.

Conclusion and Future Work

This research bridges the gap between traditional graph theory and modern network coding reliability. By establishing the duality between edge and vertex capacity factors, the theory can be extended to node failures in physical hardware.

Future work remains in narrowing the complexity gap for Capacity Rank and extending these efficient algorithms to multicast scenarios (one source, multiple sinks). While acyclic networks offer clean theoretical properties, the introduction of cycles significantly complicates the landscape, leaving open questions for more general network topologies.

Summary updated

Abstract

In this paper, we investigate some properties on capacity factors, which were proposed to investigate the link failure problem from network coding. A capacity factor (CF) of a network is an edge set, deleting which will cause the maximum flow to decrease while deleting any proper subset will not. Generally, a $k$-CF is a minimal (not minimum) edge set which will cause the network maximum flow decrease by $k$. Under point to point acyclic scenario, we characterize all the edges which are contained in some CF, and propose an efficient algorithm to classify. And we show that all edges on some $s$-$t$ path in an acyclic point-to-point acyclic network are contained in some 2-CF. We also study some other properties of CF of point to point network, and a simple relationship with CF in multicast network. On the other hand, some computational hardness results relating to capacity factors are obtained. We prove that deciding whether there is a capacity factor of a cyclic network with size not less a given number is NP-complete, and the time complexity of calculating the capacity rank is lowered bounded by solving the maximal flow. Besides that, we propose the analogous definition of CF on vertices and show it captures edge capacity factors as a special case.
BibTeX
@misc{li2012capacity,
  author = {Yuan Li and Yue Zhao and Haibin Kan},
  title = {{Capacity Factors of a Point-to-point Network}},
  year = {2012},
  eprint = {1201.0435},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1201.0435},
}
Figure