Connectivity Labeling in Faulty Colored Graphs

Area of Science:

• Theoretical Computer Science
• Graph Theory
• Distributed Computing

Background:

• Fault-tolerant connectivity labeling enables determining graph connectivity despite element failures using succinct labels.
• Existing schemes for edge/vertex faults achieve poly(f, log n)-bit labels.
• The color faults model, where colors represent faulty elements, presents unique challenges due to correlations.

Purpose of the Study:

• To develop efficient fault-tolerant connectivity labeling schemes for the color faults model.
• To determine the label length complexity for connectivity under one color fault (f=1).
• To extend the findings to multiple color faults (f>=2) and explore centralized settings.

Main Methods:

• Deterministic labeling scheme with O~(sqrt(n))-bit labels for single color faults.
• Introduction of the 'ball packing number' (bp(G)) as a new graph parameter.
• Development of a randomized scheme for f>=2 color faults and analysis for f=2.

Main Results:

• Achieved O~(sqrt(n))-bit labels and matching lower bound for single color faults, proving universal optimality.
• Introduced a routing scheme with O~(bp(G))-bit routing tables for avoiding a single forbidden color.
• Presented a centralized O~(n)-space oracle for single color fault connectivity queries in O~(1) time.

Conclusions:

• The O~(sqrt(n)) bound is optimal for single color faults, significantly improving upon Ω(n) bounds.
• The ball packing number characterizes optimal label length for connectivity under one color fault.
• The study provides efficient solutions for multiple color faults and centralized settings, with implications for dynamic algorithms.