Linear-in-$\Delta$ Lower Bounds in the LOCAL Model

Mika Göös, Juho Hirvonen, Jukka Suomela

By prior work, there is a distributed algorithm that finds a maximal fractional matching (maximal edge packing) in $O(\Delta )$ rounds, where $\Delta$ is the maximum degree of the graph. We s…