An arXiv preprint presents a set of algorithms for a graph-connectivity problem in which different, nested tiers of edges can carry different requirements. When the number of tiers is a fixed constant, its main randomized k-tier Flexible Graph Connectivity algorithm returns a feasible solution with probability at least one third. The stated approximation factor depends on the number of tiers and on the logarithm of the graph's size. An approximation factor is a worst-case measure of how far an algorithm's solution may be from the best possible one.
The problem starts with nested edge tiers
The model is built on an undirected graph with non-negative edge costs. Its tiers are nested, starting with the first tier and ending with a final tier that contains every edge. Each tier has a non-negative integral requirement, and the requirements do not decrease from the first tier to the last. A cut, meaning a division of the graph's vertices into two sides, is safe when at least one tier contains enough edges to meet its own requirement. That definition supplies the flexibility in the paper's connectivity formulations.
One model, several optimization targets
One branch of the work asks for a min-cardinality solution, meaning one that uses as few selected edges as possible. Its approximation factor combines the best known approximation ratio for min-cardinality p-ECSS with an additional term determined by the first and last tier requirements: twice their difference divided by the first requirement. The guarantee therefore changes with the requirements rather than being a single fixed number. The construction uses an approximate first-tier edge-connectivity solution together with inclusion-wise minimal excluding covers, which the paper says can be found in polynomial time.
Another branch tackles k-tier Flexible Multi-Graph Connectivity. The proposed algorithm runs in polynomial time and is a 2-approximation. It first finds a minimum-weight spanning tree, a set of edges that connects all vertices without cycles, then assigns each selected tree edge in its tier the multiplicity required by that tier while assigning multiplicity zero to other edges. In effect, the method builds from one selected tree and gives its edges the tier-specific counts used in the analysis.
Alongside the approximation results, the paper gives a polynomial-time way to verify whether a graph meets the k-tier FGC conditions when the number of tiers is fixed. It also shows that, for every fixed constant k, the linear-programming relaxation of its k-tier integer program can be solved in polynomial time. This relaxation permits fractional edge choices while the target solution remains integral. The stated approach uses an efficient separation oracle, a procedure for finding a violated constraint, together with the Ellipsoid method.
The main guarantee depends on random sampling
The main FGC result uses randomized rounding, a process that converts fractional edge choices into an actual selected-edge solution. Algorithm 2 retains edges whose fractional values clear a threshold and samples each remaining edge with a probability set by its value and a factor tied to the tier count and graph size. The analysis gives a high-probability feasibility bound and separately states that, with constant probability, the rounded solution is feasible while meeting a cost bound relative to the displayed LP solution. These are probabilistic guarantees, so they describe the algorithm's analyzed chance of success rather than every individual run.
The fixed-tier boundary matters
The LP relaxation is not shown to be tight. On a constructed cycle instance, the paper gives a lower bound on its integrality gap of at least . An integrality gap measures the separation between the value allowed by a fractional relaxation and the value required by an integer solution. Here, k is the number of tiers and V is the vertex set. Because this is a lower-bound construction on a specific cycle, it does not establish the exact gap for every graph.
The FMGC guarantee carries its own qualification. The integer formulation used in that analysis is explicitly a relaxation and does not itself formulate k-tier FMGC, although every feasible k-tier FMGC solution is feasible for the relaxation. The factor-two result is therefore presented alongside a formulation caveat, rather than as evidence that the relaxation exactly captures the original multi-graph problem.
Across the FGC results, the fixed-tier condition is central. The polynomial-time feasibility and LP claims are stated for a fixed constant number of tiers, and the main approximation result is likewise limited to that setting. The paper leaves open whether dependence on the number of tiers and the graph size can be reduced or replaced with dependence on the tier requirements. The supplied document is arXiv version 1 dated 28 August 2026 and reports partial support from NSF grant CCF-2402667.
Paper data and sources
Original title: Multi-tier Flexible Graph Connectivity
Authors: Karthekeyan Chandrasekaran, Raymond Jiang, Krishna Kalathur
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-28
DOI: Not available
Original paper · Full text