Combinatorics and TCS Seminar

Wednesday, 3rd January 2024, 2.30 pm

=======================

Venue: Google Meet (https://meet.google.com/ctv-ynac-gjt)

Host: Sudhir R. Ghorpade

Speaker: Prafullkumar Tale

Affiliation: IISER Bhopal

Title: Parameterized Complexity and Some New Lower Bounds for Problems in NP

Abstract: In this talk, we briefly introduce Parameterized Complexity and some graph theoretical NP complete problems. We then look at the usual conditional lower bounds in this domain, most of which are single (or almost single) exponential.

Our results, for the first time, derive double-exponential lower bounds for natural, important, and well-studied NP-complete graph problems when parameterized by structural parameters. Specifically, we design a technique to obtain such lower bounds and show its versatility by applying it to three different problems: Metric Dimension, Strong Metric Dimension, and Geodetic Set. This techniques use for the lower bounds uses a novel yet simple technique based on the Sperner families of sets.