IMSc Webinar

Structural Parameterizations with Modulator Oblivion

Ashwin Jacob

IMSc

Webinar: join at https://meet.google.com/bbj-oeri-ccz It is known that Vertex Cover is polynomial time solvable in the class of chordal graphs. We consider this problem in a graph that has at most $k$ vertices whose deletion results in a chordal graph, when parameterized by $k$. While this investigation fits naturally into the recent trend of what are called 'structural parameterizations', here we assume that the deletion set is not given. Specifically, we show a $2^{O(k)}n^{O(1)}$ time algorithm for Vertex Cover parameterized by the size of chordal vertex deletion set when the chordal deletion set is not given as a part of the input.