CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Discrete algorithms I
Org: Marcin Pilipczuk (University of Warsaw, Poland)

GREG BODWIN, Georgia Tech
Distance and Reachability Preservers  [PDF]

Given a graph $G$ and a set of node pairs $P$, A \emph{distance} or \emph{reachability} preserver is a sparse subgraph $H$ that preserves distance or reachability between all pairs in $P$. Research typically focuses on the extremal tradeoffs between the sizes of $G, P$, and the number of edges needed in $H$. In this talk we will discuss the state-of-the-art for these preservers, survey some algorithmic applications, and mention several outstanding open questions in the area.

Counting small patterns via homomorphisms  [PDF]

Classical results by Lovász show that, for every fixed graph $H$, the number of $H$-subgraph copies in graphs $G$ is a linear combination of homomorphism counts from fixed graphs $F_1, \ldots, F_t$ into $G$.

It turned out recently that the algorithmic problem of counting $H$-subgraphs and related patterns is precisely as hard as counting homomorphisms for the hardest graphs among $F_1, \ldots, F_t$. This enabled clean upper and (conditional) lower bounds for these problems.

In this talk, we give an introduction to the algorithmic connection between counting subgraph-like patterns and homomorphisms and then survey recent results.

KRZYSZTOF NOWICKI, University of Wrocław
MST in O(1) rounds of Congested Clique  [PDF]

Congested-Clique is a synchronous multi-party communication model, in which there are $n$ players that perform computation in synchronous rounds, each consisting of the phase of local computation and the phase of communication. While communicating, each pair of players can exchange $O(\log\hspace{0.25em}n)$-bit messages. Each player corresponds to a single vertex of the input graph and initially knows all edges incident to this vertex.

This talk is about two techniques that are essential for the $\mathcal{O}(1)$ round algorithm for the Minimum Spanning Forest problem. The first technique gives an $\mathcal{O}(\log^*\hspace{0.25em}n)$ round algorithm [Ghaffari,Parter;PODC'16], the second [Jurdziński,Nowicki;SODA'18] improves its complexity to $\mathcal{O}(1)$ rounds.

EVA ROTENBERG, Technical University of Denmark
Online Bipartite Matching with Amortized $O(\log^2 n)$ Replacements  [PDF]

In Online Bipartite Matching with Replacements, all the vertices on one side of the bipartition are given, and the up to $n$ vertices on the other side arrive one-by-one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path (SAP) from the newly inserted vertex uses at most amortized $O(\log^2 n)$ replacements per insertion, approaching the $\Omega(\log n)$ lower bound. The previous best strategy [Bosek, Leniowski, Sankowski, Zych, FOCS 2014] achieved amortized $O(\sqrt{n})$ replacements.

Four-coloring $P_6$-free graphs  [PDF]

I will present a polynomial-time algorithm for the 4-coloring problem restricted to the class of graphs with no induced six-vertex path, proving a conjecture of Huang. Combined with previously known results this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph.

Joint work with Maria Chudnovsky and Mingxian Zhong.