## Seminars & Colloquia

## Marcin Pilipczuk

### University of Warsaw

**"Recent progress in distance and cut sparsifiers"**

#### Friday February 16, 2018 11:30 AM

Location: 1005, EB1 NCSU Centennial Campus

(Visitor parking instructions)

**This talk is part of the**
**Theory Seminar Series**

**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.

**Host:** Blair D. Sullivan, CSC