# Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover

arXiv: https://arxiv.org/abs/2402.08346 · HTML: https://mlsanity.com/paper/2402.08346/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2024.

## Built on by (most cited first, 1 of 1)

- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)

## Abstract (arXiv)

We investigate fine-grained algorithmic aspects of identification problems in graphs and set systems, with a focus on Locating-Dominating Set and Test Cover. We prove the (tight) conditional lower bounds for these problems when parameterized by treewidth and solution as. Formally, textscLocating-Dominating Set (respectively, textscTest Cover) parameterized by the treewidth of the input graph (respectively, of the natural auxiliary graph) does not admit an algorithm running in time 2^2o(tw) · poly(n) (respectively, 2^2o(tw) · poly(|U| + |F|)). This result augments the small list of NP-Complete problems that admit double exponential lower bounds when parameterized by treewidth. Then, we first prove that textscLocating-Dominating Set does not admit an algorithm running in time 2o(k2) · poly(n), nor a polynomial time kernelization algorithm that reduces the solution size and outputs a kernel with 2o(k) vertices, unless the ETH fails. To the best of our knowledge, textscLocating-Dominating Set is the first problem that admits such an algorithmic lower-bound (with a quadratic function in the exponent) when parameterized by the solution size. Finally, we prove that textscTest Cover does not admit an algorithm running in time 2^2o(k) · poly(|U| + |F|). This is also a rare example of the problem that admits a double exponential lower bound when parameterized by the solution size. We also present algorithms whose running times match the above lower bounds.