1 of 67

Vizing’s Theorem in Near-Linear Time

Sepehr Assadi �University of Waterloo

Sayan Bhattacharya�University of Warwick

Soheil Behnezhad�Northeastern University

Martín Costa�University of Warwick

Tianyi Zhang�ETH Zurich

Shay Solomon�Tel Aviv University

midjourney

2 of 67

What is the Edge Coloring Problem?

3 of 67

What is the Edge Coloring Problem?

4 of 67

Algorithms for Edge Coloring

5 of 67

Our Result

6 of 67

Algorithms for Edge Coloring

7 of 67

Idea 0:�Color Extension and Alternating Paths

8 of 67

Idea 0: Color Extension and Alternating Paths

9 of 67

Idea 0: Color Extension and Alternating Paths

10 of 67

Idea 0: Color Extension and Alternating Paths

11 of 67

A Simple Algorithm for Bipartite Graphs

12 of 67

A Simple Algorithm for Bipartite Graphs

13 of 67

A Simple Algorithm for Bipartite Graphs

14 of 67

A Useful Insight

Flipping these paths 🡺 color all edges

15 of 67

Idea 0’:�Euler Partitions

16 of 67

Idea 0’: Euler Partitions

2

3

2

3

1

2

4

2

3

1

2

3

4

6

7

8

5

17 of 67

Our Algorithm Instantiated�on Bipartite Graphs

First near-linear time bipartite algorithm based on alternating paths.

The algorithm uses colors.

Introduces key subroutines/insights of the final algorithm for general graphs.

18 of 67

Euler Partitions for Edge Coloring

…

Extends easily to general graphs

19 of 67

Bird’s-Eye View of Our Approach

Single-edge color extension

🡺 Batch color extension

20 of 67

A Simplifying Assumption

21 of 67

Component I: Color Type-Reduction

22 of 67

Component I: Color Type-Reduction

Remain vertex-disjoint!

23 of 67

Component II: Uniform Type Color-Extension

24 of 67

Putting Everything Together

25 of 67

Component I: �Color-Type Reduction

26 of 67

Component I: Color Type-Reduction

27 of 67

The Framework

28 of 67

An Iteration

29 of 67

An Iteration

30 of 67

An Iteration

31 of 67

An Iteration

32 of 67

An Iteration

33 of 67

An Iteration

34 of 67

An Iteration

35 of 67

An Iteration

vertex-disjoint!

36 of 67

An Iteration

37 of 67

Component II: �Uniform Type Color-Extension

38 of 67

Component II: Uniform Type Color-Extension

39 of 67

The Algorithm

40 of 67

The Algorithm

41 of 67

The Algorithm

42 of 67

Putting Everything Together

43 of 67

Extension to General Graphs

44 of 67

Recall the Challenge

45 of 67

Vizing Fans and Chains

46 of 67

Vizing Fans and Chains

47 of 67

Vizing Fans and Chains

48 of 67

Vizing Fans and Chains

Case 2 fan

49 of 67

Vizing Fans and Chains

50 of 67

Vizing Fans and Chains

51 of 67

u-Fans

[Gabow et al. ‘85]

52 of 67

Bird’s-Eye View of Our Approach�for General Graphs

53 of 67

Bird’s-Eye View of Our Approach�for General Graphs

54 of 67

Bird’s-Eye View of Our Approach�for General Graphs

u-Fans

55 of 67

Bird’s-Eye View of Our Approach�for General Graphs

u-Fans

a constant fraction

56 of 67

Bird’s-Eye View of Our Approach�for General Graphs

Remains:

u-Fans

a constant fraction

57 of 67

Coloring or Creating u-Fans

58 of 67

Coloring or Creating u-Fans

59 of 67

Coloring or Creating u-Fans

60 of 67

Coloring or Creating u-Fans

61 of 67

Coloring or Creating u-Fans

62 of 67

Coloring or Creating u-Fans

63 of 67

Creating u-Fans via Intersecting Vizing Chains

64 of 67

Creating u-Fans via Intersecting Vizing Chains

65 of 67

Creating u-Fans via Intersecting Vizing Chains

66 of 67

Bird’s-Eye View of Our Approach�for General Graphs

u-Fans

constant fraction

67 of 67

Conclusion