============================== 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 constraints. 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 talk. Join work with D. Marx and B. O'Sullivan. Available at <http://arxiv.org/abs/1110.4765> Chanukka Sameach! --------------------------------------------------------- Technion Math Net-2 (TECHMATH2) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Yuval Roichman <yuvalr@macs.biu.ac.il>