Abstract: In the talk I will discuss two related notions with regards to graph compression.

- Given a graph (directed or undirected, weighted or unweighted) G with n vertices, and a set P of p pairs of vertices, a distance sparsifier is an edge-minimal subgraph of G that maintains the same lengths of shortest paths between the pairs in P. A natural question is to obtain as small as possible size of a distance sparsifier, expressed as a function of n and p.

- Given an edge-weighted graph G with a set Q of k terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts between any partition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph G being either an arbitrary graph or coming from a specific graph class.

In many special cases, the known upper and lower bounds for the above concepts are surprising far from each other. In the talk, I will survey these areas, with emphasize on open problems. Furthermore, I will present our recent result obtained in a joint work with Nikolai Karpov and Anna Zych-Pawlewicz, namely an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with k terminals that require 2^{k?2} edges in any mimicking network.

Short Bio: Marcin Pilipczuk received his PhD from University of Warsaw in 2012. After a stay at Bergen, Warwick, and at the Simons Institute for Theory of Computing in Berkeley, he returned to Warsaw. His main research interests include parameterized complexity and structural graph theory.