Skip to content

LIMDA Seminar (2019-2020)



ALBCOM Seminar on Algorithms and Theory of Computation
COMBGRAPH Seminar on Combinatorics, Graph Theory and Applications
GAPCOMB Geometric, Algebraic and Probabilistic combinatorics

Next talk

On 12th September, 2019, 12h at Room C3-005, Campus Nord UPC
Dimitrios Thilikos (CNRS, LIRMM & Dept. Math., NKUA)
will give a talk on

 The parameterized complexity of F-M-Deletion on partial k-trees: a tight classification.

 

AbstractFor a fixed connected graph  H, the  {H}-M-Deletion  problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H  in G. It is known that this problem can be solved in time f(tw) n^{O(1)}, where tw is the treewidth of G. We determine the asymptotically optimal function f(tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw)=2^{Θ(tw)} if H is a contraction of the chair or the banner, and f(tw)=2^{Θ(tw log tw)} otherwise.

The proof combines several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem,  Bidimensionality,  the irrelevant vertex technique, treewidth modulators, and protrusion replacement. 

____________________________

This seminar is partially supported by ERC Consolidator Research Grant  ERC-2014-CoG 648276 AUTAR ReadingSeminar-W1718_html_m36e0576.jpgReadingSeminar-W1718_html_m40a518ce.jpg

____________________________

Previous sessions this year

Date:
Speaker
Title

Abstract
____________________________