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.
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