Research Projects

The graph problems $\Pi$-Deletion and $\Pi$-Detection are NP-hard for most non-trivial graph families \Pi. These problems require a vertex subset S of the smallest size to remove from G, and a vertex subset S of the largest size to ensure the graph G induced on S belongs to the family \Pi. These problems have been extensively studied in frameworks designed to cope with NP-hardness, such as Approximation Algorithms and Exact Algorithms. However, many conjectures, such as the P$\neq$NP conjecture, have been used to prove inapproximability results for these problems. Newer conjectures like the Uniques Games Conjecture and Gap-Exponential Time Hypothesis have been used to refute approximation algorithms for these problems. The Exponential Time Hypothesis, formulated by Impagliazzo and Paturi, allows for refuting exact algorithms running in time for $\Pi$-Deletion and $\Pi$-Detection. This proposal aims to study the trade-off between time vs. the approximation factor, with a particular focus on sub-exponential time computability. The study will start with classical graph problems like Vertex Cover and Feedback Vertex Set, and consider problems on restricted graph classes to obtain better approximation factors. The proposal also plans to study problems for which constant factor polynomial time approximation algorithms are unknown and explore whether allowing sub-exponential time leads to constant factor approximations.