Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
<|reference_start|>Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover: 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, \textsc{Locating-Dominating Set} (respectively, \textsc{Test Cover}) parameterized by the treewidth of the input graph (respectively, of the natural auxiliary graph) does not admit an algorithm running in time $2^{2^{o(tw)}} \cdot poly(n)$ (respectively, $2^{2^{o(tw)}} \cdot poly(|U| + |\mathcal{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 \textsc{Locating-Dominating Set} does not admit an algorithm running in time $2^{o(k^2)} \cdot poly(n)$, nor a polynomial time kernelization algorithm that reduces the solution size and outputs a kernel with $2^{o(k)}$ vertices, unless the \ETH\ fails. To the best of our knowledge, \textsc{Locating-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 \textsc{Test Cover} does not admit an algorithm running in time $2^{2^{o(k)}} \cdot poly(|U| + |\mathcal{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.<|reference_end|>
@article{chakraborty2024tight,
    title={Tight (Double) Exponential Bounds for Identification Problems:
  Locating-Dominating Set and Test Cover},
    author={Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, and
  Prafullkumar Tale},
    journal={arXiv preprint arXiv:2402.08346},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08346},
    primaryClass={cs.DS cs.CC cs.DM}
}