AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

It is known for many algorithmic problems that if a tree decomposition of width t is given in the input, then the problem can be solved with exponential dependence on t. A line of research initiated by Lokshtanov, Marx, and Saurabh [SODA 2011] produced lower bounds showing that in many cases known DP algorithms already achieve the best possible exponential dependence on t, assuming the Strong Exponential-Time Hypothesis

(SETH). Our results reveal that, for many problems, the research on lower bounds on the dependence on tree width was never really about tree decompositions, but the real source of hardness comes from a much
simpler structure.

This will be a high-level talk. It is about motivation, results and intuition, not about proofs or technical details.

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only