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 [Formula: see text] on [Formula: see text] vertices and an integer [Formula: see text], and the objective is to decide whether there is a subset [Formula: see text] of [Formula: see text] vertices such that any two distinct vertices not in [Formula: see text] are dominated by distinct subsets of [Formula: see text]. In the second problem, an input is a set [Formula: see text] of items, a collection [Formula: see text] of subsets of [Formula: see text] called tests, and an integer [Formula: see text], and the objective is to select a set [Formula: see text] of at most [Formula: see text] tests such that any two distinct items are contained in a distinct subset of tests of [Formula: see text]. 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 [Formula: see text] (respectively, [Formula: see text]), 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 [Formula: see text] or a polynomial-time kernelization algorithm that reduces the solution size and outputs a kernel with [Formula: see text] vertices, and Test Cover does not admit an algorithm running in time [Formula: see text] or a kernel with [Formula: see text] vertices. Again, we show that these lower bounds are tight by designing (kernelization) algorithms with matching running times.