***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Marcin Pilipczuk (U Warsaw)

Thursday 14th November, 3:00 in Fine Hall 224.

Title: Randomized contractions meet lean decompositions
 
The randomized contractions technique, introduced by Chitnis et al. in 2012, 
is a robust framework for designing parameterized algorithms for graph 
separation problems. On a high level, an algorithm in this framework recurses 
on balanced separators while possible, and in the leaves of the recursion 
exploits the high connectivity of the graph at hand to highlight a solution 
using color coding.
 
In 2014, we showed a static decomposition theorem corresponding to the 
recursion scheme underlying randomized contractions: given a graph G and 
connectivity parameter k, one can compute a tree decomposition of G with 
adhesions of size bounded in k and with bags exhibiting the same high 
connectivity properties with respect to cuts of size at most k as in the 
leaves of the recursion in the randomized contractions framework. This theorem 
was the key ingredient of the fixed-parameter algorithm for the Minimum 
Bisection problem.
 
Now, we provide a new construction algorithm for tree decompositions admitting 
the properties described above using the notion of lean decompositions of 
Thomas. Our algorithm is not only arguably simpler than the one from 2014, but 
also gives better parameter bounds; in particular, we provide probably the 
best possible connectivity properties and adhesion size bounds. This allows us 
to provide 2^{O(k log k)} n^{O(1)}-time parameterized algorithms for 
Minimum Bisection, Steiner Cut, and Steiner Multicut.
 
Joint work with Marek Cygan, Paweł Komosa, Daniel Lokshtanov, Michał Pilipczuk,
Saket Saurabh, and Magnus Wahlström.

		----------------------------------

Next week:  Carla Groenland

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)