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

Speaker: Daniel Lokshtanov, UCSB

Thursday 21st September, 3:00 in Fine Hall 224.

Title: Bandwidth is FPT-Approximable


A layout of a graph G is an injective function f : V(G) --> Z, and the
bandwidth of a layout f is bw(G,f) = max |f(u) - f(v)| where the maximum is
taken over all edges uv in G. The bandwidth bw(G) of G is the minimum
bandwidth of a layout of G. Computing the bandwidth of a graph is a
notoriously hard problem: assuming P != NP there is no polynomial time
algorithm, even on very restricted classes of trees [Monien, SIAM Journal
on Algebraic Discrete Methods, 1986], and no constant factor approximation,
even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time
Hypothesis there is no algorithm with running time f(k)n^{o(k)} even on
very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014].

We show that bandwidth is FPT-approximable. In particular we give an
algorithm that takes as input a graph G and integer k, runs in time
f(k)n^{O(1)}, and either outputs a subtree T of G such that bw(T) > k, or a
layout of G of bandwidth at most h(k). Here f and h are functions that
depend solely on k. Our theorem can be seen as an analogue for bandwidth of
the classic grid minor theorem for treewidth, forbidden subtree theorem for
pathwidth, and forbidden sub-path theorem for tree-depth.

Joint work with M. Chudnovsky and E. Nevo

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

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