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

Speaker: Tuukka Korhonen (University of Bergen)

Thursday 2nd March, 3:00 in Fine Hall 224.

Title: An improved parameterized algorithm for treewidth

We give a 2^O(k^2) n^O(1) time algorithm for determining if the
treewidth of a given n-vertex graph is at most k and outputting the
corresponding tree decomposition. This is the first improvement on the
dependency on k in fixed-parameter algorithms for treewidth since the
2^O(k^3) n^O(1) time algorithm given in 1991 by Bodlaender-Kloks and
Lagergren-Arnborg. We also give a k^O(k/eps) n^O(1) time
(1+eps)-approximation algorithm for treewidth. Our algorithms are based on
introducing a new variant of treewidth called subset treewidth, showing
that parameterized algorithms for subset treewidth imply parameterized
algorithms for treewidth, and then giving parameterized algorithms for
subset treewidth. This is joint work with Daniel Lokshtanov.

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


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