SIAM Journal on Discrete Mathematics· 2026Q1
Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
- 1citations
- Q1SCImago
- 2026year
Short summary
Locating-Dominating Set and Test Cover problems do not admit algorithms faster than O(2^tw) or O(2^k) respectively, and polynomial-time kernelization with O(tw) or O(k) vertices, unless the Exponential Time Hypothesis (ETH) fails.
AI-generated from the title and abstract; the full text is not read.
Key points
- Locating-Dominating Set and Test Cover problems are proven to have a lower bound of O(2^tw) and O(2^k) running time, respectively, assuming the ETH.
- Polynomial-time kernelization for these problems is also shown to be impossible within O(tw) and O(k) vertices, respectively, under the ETH.
- The paper provides algorithms with matching running times and kernel sizes, confirming the tightness of the established lower bounds.
AI-generated from the title and abstract; the full text is not read.
Abstract
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.
The authors' abstract, as published at the source. SIAM Journal on Discrete Mathematics, 2026 · DOI ↗
Continue with a free account
Ask the paper: 3 free questions a day about this paper; save it, get its citation, new summaries every day for your field. Takeaways are Premium.
Continue free on the webSign in with Google or Apple; no card needed. You come back to this paper.
On your phone:
Field: Computational Theory and Mathematics
Computational Theory and MathematicsComputer Science