Thursday, November 5 2020
11:30 - 12:30

IMSc Webinar

Structural Parameterizations with Modulator Oblivion

Ashwin Jacob


Webinar: join at 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.

Download as iCalendar