| Title | : | Tight algorithmic double-exponential bounds for treewidth for some metric-based and identification-based graph problems |
| Speaker | : | Florent Foucaud (University of Clermont Auvergne, France) |
| Details | : | Wed, Jan 15, 2025 11:00 AM, @ Turing Hall (SSB 334) |
| Abstract | : | We investigate fine-grained algorithmic aspects of certain graph problems (Metric Dimension, Geodetic Set and Locating-Dominating Set), and also in set systems (Test Cover). The two first problems are covering problems based on distances/shortest paths, while the two last problems are neighbourhood-based identification problems. We show that when parameterized by the treewidth of the input graph, none of these problems admit an algorithm running in FPT time $2^{2^{o( w)}} poly(n)$, unless the Exponential-Time Hypothesis (ETH) fails. For the two local identification problems, this is tight. For the two metric-based problems, this is tight when the diameter is bounded. These are the first NP-complete problems that admit (tight) double-exponential lower bounds when parameterized by treewidth. Some other aspects of these problems will also be presented, depending on time.
The talk is based on two joint works with: -Esther Galby, Liana Khazalya, Shaohua Li, Fionn McInerney, Roohani Sharma, Prafullkumar Tale (ICALP 2024, https://arxiv.org/abs/2307.08149); -Dipayan Chakraborty, Diptapriyo Majumdar, Prafullkumar Tale (ISAAC 2024, http://arxiv.org/abs/2402.08346). |