Bar-Ilan Combinatorics Seminar
The next meeting will be, IYH, on Sunday, 6 Tevet (Jan 1) at 14:00 pm in
Room 201 (Math Dept Seminar Room), Math and CS Building
Speaker: Igor Razgon (University of Leicester)
Title: Treewidth reduction theorem and algorithmic problems on graphs
Abstract: We introduce so called treewidth reduction theorem. Given a graph
$G$, two specified vertices $s$ and $t$, and an integer $k$, let $C$ be the
union of all minimal $s-t$ (vertex) separators of size at most $k$.
Further on, let $G^*$ be the graph obtained from $G$ by contracting all the
connected components of $G \setminus C$ into single vertices. The theorem
states that the treewidth of $G^*$ is bounded by a function of $k$.
and that the graph $G^*$ can be computed in a linear time for any fixed $k$.
The above theorem allows us to solve in a linear time for every fixed $k$
the following generic graph separation problem. Let $G$ be a graph with two
specified vertices $s$ and $t$ and let $Z$ be a hereditary class of graphs.
The problem asks if $G$ has a $s-t$ vertex separator of size at most $k$
such that the subgraph graph induced by $S$ belongs to the class $Z$.
In other words, we show that this generic problem is fixed-paramete
tractable. This allows us to resolve a number of seemingly unrelated open
questions scattered in the literature concerning fixed-parameter
tractability of various graph separation problems under specific
The role of the treewidth reduction theorem is that it reduces an arbitrary
instance of the given problem to an instance of the problem where the
treewidth is bounded. Then a standard methodology using Courcelle theorem
can be applied.
The purpose of this talk is to convey the main technical ideas of the above
work in an intuitive level.
The talk is self-contained. In particular, no prior knowledge of
parameterized complexity, treewidth, and Courcelle theorem is needed.
Everything will be intuitively defined in the first 10-15 minutes of the
Join work with D. Marx and B. O'Sullivan. Available at
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel <firstname.lastname@example.org>
Announcement from: Yuval Roichman <email@example.com>