Separator theorem for B_t-free graphs

Karolina Okrasa

supervisor: Zbigniew Lonc

Let G be a graph on n vertices, and let S be a subset of vertices of G. Let p ∈ (0,1). We say that S is an p-balanced separator if each connected component of G-S (i.e., each "part" of the graph obtained by removing vertices that belong to S) has at most pn vertices.

We consider a class B_t of graphs that excludes some certain structures that consist of a path and a cycle. We prove that every graph from the class B_t contains a "small"-size set X, such that the set consisting of X and the vertices adjacent to X, is a 3/4-balanced separator. In particular, if the maximum degree of a vertex in G is bounded, we can obtain a 3/4-balanced separator of bounded size.

This result leads to several algorithmic corollaries -- we illustrate how this result can be applied when solving a classic graph problem called Independent Set. In the Independent Set problem, we are given a graph G and the task is to find the size of the largest subset of vertices of G that are pairwise non-adjacent. We show that if we assume that G belongs to the class B_t, then we can compute the size of the largest independent set in G in time subexponential in n.

This is a joint work with Paweł Rzążewski.