Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity

Area of Science:

• Graph Theory
• Algorithms
• Computer Science

Background:

• Tree-packings, collections of spanning trees, are crucial for minimum cut and graph parameter studies.
• Existing dynamic algorithms for min-cut and arboricity rely on tree-packing structures.
• Previous dynamic min-cut algorithms achieved update times like O~(λ^14.5√n).

Purpose of the Study:

• To investigate the structural properties of tree-packings and their connection to min-cut and arboricity.
• To develop faster dynamic algorithms for exact min-cut and fractional arboricity maintenance.
• To establish new lower bounds for greedy tree-packing.

Main Methods:

• Analyzing the relationship between tree-packings and graph cuts.
• Developing a deterministic algorithm for fully dynamic exact min-cut.
• Designing a deterministic algorithm for maintaining (1+ε)-approximations of fractional arboricity.

Main Results:

• A deterministic algorithm for fully dynamic exact min-cut with O~(λ^5.5√n) worst-case update time.
• An improved amortized update time of O~(m^(1-1/12)) for dynamic exact min-cut.
• The first fully dynamic algorithm for (1+ε)-approximate fractional arboricity with O(α log^6 m / ε^4) amortized update time.

Conclusions:

• The study provides significant improvements in dynamic graph algorithms through novel structural insights into tree-packings.
• The new algorithms offer faster update times for fundamental graph problems on multi-graphs.
• This work advances the understanding of tree-packing structures and their algorithmic applications.