Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth

Abstract

In Chordal/Interval Vertex Deletion we ask how many vertices one needs to remove from a graph to make it chordal (respectively: interval). We study these problems under the parameterization by treewidth $tw$ of the input graph $G$. On the one hand, we present an algorithm for Chordal Vertex Deletion with running time $2^{O(tw)}\cdot |V(G)|$, improving upon the running time $2^{O(t{w}^2)}\cdot |V(G){|}^{O(1)}$ by Jansen, de Kroon, and Wlodarczyk (STOC'21). When a tree decomposition of width $tw$ is given, then the base of the exponent equals $2^{\omega -1}\cdot 3+1$. Our algorithm is based on a novel link between chordal graphs and graphic matroids, which allows us to employ the framework of representative families. On the other hand, we prove that the known $2^{O(tw\log tw)}\cdot |V(G)|$-time algorithm for Interval Vertex Deletion cannot be improved assuming Exponential Time Hypothesis.

To appear at ICALP'23