Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale
January 2024
PDF bib Project Project DOI

Abstract

Full Citation:

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale. Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover. 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (Karl Bringmann and Martin Grohe and Gabriele Puppis and Ola Svensson), volume 297 of LIPIcs, pages 66:1-66:19, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.

Type
Conference Paper
PGD ParAI
Liana Khazaliya
Liana Khazaliya

Liana Khazaliya is a Project Assistant at the Algorithms and Complexity Group.