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

Abstract

We investigate fine-grained algorithmic aspects for classical identification problems in graphs, namely, Locating-Dominating Set, and in set systems, namely, Test Cover. In the first problem, an input is a graph 𝐺 on 𝑛 vertices and an integer 𝑘, and the objective is to decide whether there is a subset 𝑆 of 𝑘 vertices such that any two distinct vertices not in 𝑆 are dominated by distinct subsets of 𝑆. In the second problem, an input is a set 𝑈 of items, a collection F of subsets of 𝑈 called tests, and an integer 𝑘, and the objective is to select a set 𝑆 of at most 𝑘 tests such that any two distinct items are contained in a distinct subset of tests of 𝑆. For our first result, we Locating-Dominating Set (respectively, Test Cover) parameterized by the treewidth of the input graph (respectively, the incidence graph) does not admit an algorithm running in time 22𝑜⁡(𝗍𝗐) ⋅poly⁡(𝑛) (respectively, 22𝑜⁡(𝗍𝗐) ⋅poly⁡(|𝑈| +|F|))), unless the exponential-time hypothesis (ETH) fails. Next, we prove that unless the ETH fails, Locating-Dominating Set does not admit an algorithm running in time 2𝑜⁡(𝑘2) ⋅poly⁡(𝑛) or a polynomial-time kernelization algorithm that reduces the solution size and outputs a kernel with 2𝑜⁡(𝑘) vertices, and Test Cover does not admit an algorithm running in time 22𝑜⁡(𝑘) ⋅poly⁡(|𝑈| +|F|) or a kernel with 22𝑜⁡(𝑘) vertices. Again, we show that these lower bounds are tight by designing (kernelization) algorithms with matching running times.