The link to join the zoom talk is https://uib.zoom.us/j/
Meeting ID: 423 116 9675
Password: Name of the W-complete problem, six letters, all capital. Set of pairwise adjacent vertices.
We consider two recently introduced classes of parameterizations which are relaxations of either treedepth of treewidth. They are related to graph decompositions in which subgraphs that belong to a target class H (e.g., bipartite or planar) are considered simple. First, we present a framework for computing approximately optimal decompositions for miscellaneous classes H. Namely, if the cost of an optimal decomposition is k, we show how to find a decomposition of cost k^O(1) in time f(k)*n^O(1). Secondly, we exploit the constructed decompositions for solving vertex-deletion problems under the new parameterizations.
Based on joint work with Hubie Chen, Astrid Pieterse, and Michal Wlodarczyk
As a consequence, a range of problems have quasipolynomial kernels, in particular including Edge Multiway Cut, Group Feedback Edge Set and Subset Feedback Edge Set (in its general formulation, with undeletable edges). The existence of a polynomial kernel for Multiway Cut is one of the biggest open questions in kernelization, and this result is the first improvement in general graphs since the introduction of the representative sets approach to kernelization in 2012 (Kratsch and W.).
The talk assumes no previous knowledge of matroids or other previous work on the problem.