Campus Event Calendar

### Lower bounds for maximal matchings and maximal independent sets

Jukka Suomela
Aalto University
AG1 Mittagsseminar (others' work)

Jukka Suomela (https://users.ics.aalto.fi/suomela/) is an Assistant Professor in the Department of Computer Science at Aalto University. His work focuses on the theoretical foundations of distributed computing, with particular emphasis on the concept of locality. He is a member of the EATCS council, he was recently a local co-chair of ALGO 2018, and he is the PC chair of DISC 2019.
AG 1, AG 3, AG 4, RG1, MMCI, AG 2, AG 5, SWS
AG Audience
English

#### Date, Time and Location

Thursday, 14 February 2019
13:00
30 Minutes
E1 4
024
Saarbrücken

#### Abstract

How fast can one find a maximal matching or a maximal independent set in a distributed system? Here each node of the input graph is a computer, and each node needs to output its own part of the solution. How many communication rounds are needed in a graph with n nodes and maximum degree Δ? These are classical questions with a long history of upper and lower bounds, the first of which date back to the 1980s.

For example, for maximal matchings the current upper bounds are:

(1) O(Δ + log* n), by Panconesi & Rizzi (2001)
(2) O(log Δ + log^3 log n), by Fischer (2017) and Barenboim et al. (2012, 2016).

The running time of algorithm (1) is optimal as a function of n; there is a matching lower bound by Linial (1987, 1992). The running time of algorithm (2) is near-optimal as a function of Δ; there is an almost-matching lower bound by Kuhn et al. (2004, 2016).

However, it has been a long-standing open question whether we can achieve the best of both worlds, and find maximal matchings and maximal independents sets e.g. in time O(log Δ + log* n).

We show that the answer is no. There is no distributed algorithm that finds a maximal matching or maximal independent set in time o(Δ + log log n/log log log n). Algorithm (1) is optimal for Δ << n, and algorithm (2) is near-optimal for larger values of Δ.

(This is joint work with Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, and Mikaël Rabie. Please see https://arxiv.org/abs/1901.02441 for more details.)

#### Contact

Christoph Lenzen
--email hidden
passcode not visible
logged in users only

Christoph Lenzen, 02/04/2019 17:25 -- Created document.