Structural Parameterization of Locating-Dominating Set and Test Cover

Abstract

We investigate structural parameterizations for two identification problems in graphs and set systems: Locating-Dominating Set and Test Cover. In the first problem, an input is a graph G and an integer k, and one asks whether there is a subset S of k vertices such that any two distinct vertices not in S are dominated by distinct subsets of S. In the second problem, an input is a set of items U, a collection of subsets

of U called tests, and an integer k, and one asks whether there is a solution set S of at most k tests such that each pair of items belongs to a distinct subset of tests of S.

In a related work [ISAAC 2024], we proved that both problems admit a conditional double-exponential lower bound and a matching algorithm when parameterized by the treewidth of the input graph. We continue this line of investigation and consider parameters larger than treewidth, like vertex cover number and feedback edge set number. We design a nontrivial dynamic programming scheme for Test Cover in “slightly super-exponential” time in the number |U| of items, and also Locating-Dominating Set in time , where is the vertex cover number and n the order of the graph. Thus, the known lower bounds with respect to treewidth cannot be extended to the vertex cover number. We also show that when parameterized by the feedback edge set number, Locating Dominating Set admits a linear kernel, answering an open question from [Cappelle et al., LAGOS 2021]. Finally, we show that neither Locating-Dominating Set nor Test Cover is likely to admit a compression algorithm returning an input with a subquadratic number of bits.