KAIST Discrete Math Seminar

It has long been known that Feedback Vertex Set can be solved in time 2^{O(w log w)}n^O(1) on graphs of treewidth w, but it was only recently that this running time was improved to 2^O(w)n^O(1), that is, to single-exponential parameterized by treewidth. We consider a natural generalization of this problem, which asks given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices of G such that each block of G-S has at most d vertices. The central question of this talk is: “Can we obtain an algorithm that runs in single-exponential time parameterized by treewidth, for every fixed d?” The answer is negative. But then, one may be curious which properties of Feedback Vertex Set that make it allow to have a single-exponential algorithm. To answer this question, we add an additional condition in the general problem, and provide a dichotomy result.
Formally, for a class ? of graphs, the Bounded ?-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices of G such that each block of G-S has at most d vertices and is in ?. Assuming that ? is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d:

• if ? consists only of chordal graphs, then the problem can be solved in time 2^{O(wd^2)}n^O(1),
• if ? contains a graph with an induced cycle of length ℓ≥4, then the problem is not solvable in time 2^{o(w log w)} n^O(1) even for fixed d=ℓ, unless the ETH fails.

We further show that it is W[1]-hard parameterized by only treewidth, when ? consists of all graphs. This is joint work with Édouard Bonnet, Nick Brettell, and Daniel Marx.