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