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.

Special Instructions: Please note that this talk is in EB1!

Host: Blair D. Sullivan, CSC

Back to Seminar Listings
Back to Colloquia Home Page