Structural Parameterization of Locating-Dominating Set and Test Cover

Dipayan Chakraborty; Diptapriyo Majumdar; Florent Foucaud; Prafullkumar Tale

REVIEW 3 major objections 4 minor 18 references

Structural Parameterization of Locating-Dominating Set and Test Cover

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Locating-Dominating Set and Test Cover admit FPT algorithms under vertex cover and item count, a linear kernel for feedback edge set number, and no subquadratic compression unless NP is in coNP/poly.

desk verdict The FPT and incompressibility results look solid, but the advertised linear kernel for feedback edge set number is unproven in this version: it depends on a missing Appendix E and an unreported empirical study. read the letter →

arxiv 2411.17948 v1 pith:Q3Q2CEZF submitted 2024-11-26 cs.DS

Dipayan Chakraborty , Florent Foucaud , Diptapriyo Majumdar , Prafullkumar Tale This is my paper · ORCID

classification cs.DS MSC 05C6968Q2568R10

keywords IdentificationProblemsLocating-DominatingSetTestCoverParameterizedAlgorithmsStructuralParameterizationsKernelizationVertexNumberFeedbackEdge

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies two NP-complete identification problems: Locating-Dominating Set, in which a chosen set of vertices must distinguish every vertex by its neighbourhood in that set, and Test Cover, in which a set of tests must give every item a unique signature. Earlier work had shown both to be doubly-exponentially hard in the treewidth of the input graph. The paper shows that these hardness results do not extend to larger structural parameters: Locating-Dominating Set is fixed-parameter tractable in the vertex cover number, and Test Cover is fixed-parameter tractable in the number of items, with running times $2^{O(\mathrm{vc}\log\mathrm{vc})}n^{O(1)}$ and $2^{O(|U|\log|U|)}(|U|+|\mathcal{F}|)^{O(1)}$. It also gives a linear kernel for Locating-Dominating Set parameterized by feedback edge set number, and proves that neither problem admits a polynomial compression of subquadratic size unless $\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$.

What carries the argument

The load-bearing object is the Annotated Red-Blue Partition Refinement problem: given a bipartite graph with red vertices as candidate solution elements and blue vertices as elements to be identified, an initial partition $\mathcal{Q}$, a forced set $C_0\subseteq R$, and a target set $T_L\subseteq B$ that must be dominated, find $C\subseteq R$ containing $C_0$ such that $C$ dominates $T_L$ and the refinement $\mathcal{Q}\Cap\mathcal{P}(C)$ is the identity partition, where $\mathcal{P}(C)$ groups vertices by their neighbourhood in $C$. The dynamic program processes vertices of $R\setminus C_0$ in a fixed order, keeping a state $(i,P,S)$ where $P$ is a possible refinement and $S$ is the set of blue vertices already dominated; the recurrence $\mathrm{opt}[i,P,S]=\min(\mathrm{opt}[i-1,P,S],\,1+\min_{P'\Cap\mathcal{P}(r_i)=P,\,S'\cup N(r_i)=S}\mathrm{opt}[i-1,P',S'])$ runs over at most $2^{O(|B|\log|B|)}|R|^{O(1)}$ states. The feedback edge set kernel uses a classification of optimal tree solutions into five types (A–E), extended to doubly-rooted trees with 25 types, and replaces each hanging tree or subdivided edge by a constant-size gadget from the same class. The incompressibility reductions use bit-representation gadgets that attach pendant pairs so that only the original choice of $R$-vertices can separate the twin pairs.

What would settle it

By exhaustive search over all doubly-rooted trees up to a given size, determine whether each of the at most $3^{25}$ behavioural classes defined by the 25-type optimality offsets is nonempty; if a class is nonempty only for trees with more than a fixed constant number of vertices, then the constant-size gadget replacement underlying the linear kernel cannot hold.

Watch

Extended reading notes

Core claim

The paper establishes Theorem 1: Locating-Dominating Set can be solved in time $2^{O(\mathrm{vc}\log\mathrm{vc})}n^{O(1)}$, where $\mathrm{vc}$ is the vertex cover number, and Test Cover in time $2^{O(|U|\log|U|)}(|U|+|\mathcal{F}|)^{O(1)}$. The algorithm reduces each problem to a bipartite partition-refinement problem, solves that problem by dynamic programming over valid tuples, and then guesses the intersection of the solution with a vertex cover. Theorem 2 gives a kernel of $O(\mathrm{fes})$ vertices and edges for Locating-Dominating Set, answering an open question and using a decomposition of the graph into a small multigraph with subdivided edges and pendant trees. Theorem 3 shows that neither problem has a polynomial compression of size $O(n^{2-\epsilon})$ unless $\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$, also reproving a $2^{o(n)}$ lower bound for Locating-Dominating Set and ruling out polynomial kernels for several combined parameters.

Load-bearing premise

The linear-kernel proof assumes that for every possible behavioural type of a doubly-rooted tree, a constant-size example tree of that type exists and can be constructed, but the construction is deferred to an appendix that is not present in this arXiv version; if some types require arbitrarily large trees, the kernel argument would fail.

Editorial extensions

If this is right

The double-exponential lower bound for treewidth does not transfer to vertex cover number: with $\mathrm{vc}$ as the parameter the problem becomes solvable in $2^{O(\mathrm{vc}\log\mathrm{vc})}n^{O(1)}$ time.
Test Cover improves from brute force $2^{O(|U|^2)}$ to $2^{O(|U|\log|U|)}(|U|+|\mathcal{F}|)^{O(1)}$ time, matching the shape of the standard Set Cover dynamic program.
Locating-Dominating Set has a kernel with $O(\mathrm{fes})$ vertices and edges when $\mathrm{fes}$ is the feedback edge set number, and combining it with brute force gives an FPT algorithm for that parameter.
Neither problem admits a polynomial compression of size $O(n^{2-\epsilon})$ unless $\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$, which also rules out polynomial kernels for the combined parameter pairs $(\mathrm{vc},k)$, $(|U|,k)$, and the single parameter $|\mathcal{F}|$.
The partition-refinement scheme extends to distance to clique, twin-cover number, and neighbourhood diversity, giving $2^{O(\mathrm{dc}\log\mathrm{dc})}$ and $2^{O(\mathrm{tc}\log\mathrm{tc})}$ algorithms and a $2d$-vertex kernel for neighbourhood diversity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The valid-tuple dynamic program is likely adaptable to other identification problems on graphs with small vertex cover, such as identifying codes or metric dimension, whenever the solution must refine a partition to singletons; one would replace the bipartite dominance condition with the appropriate separation condition.
The feedback edge set kernel should be treated as existential until the missing appendix supplies explicit gadgets for all nonempty doubly-rooted tree classes; producing a concrete list would make the kernel usable in practice.
The incompressibility reduction gives a generic recipe: if a problem can encode the Red-Blue Dominating Set instance using twin pairs and bit-representation gadgets, it will inherit the $O(n^{2-\epsilon})$ lower bound, so the authors' technique could be applied to similar distinguishing problems.
The paper's algorithm does not settle whether the logarithmic factors in the exponents are removable; proving a matching single-exponential lower bound under ETH would require a different argument than the existing treewidth transfer.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know about arXiv:2411.17948. First, the main algorithmic contributions — the 2^{O(vc log vc)} algorithm for Locating-Dominating Set parameterized by vertex cover, the analogous 2^{O(|U| log |U|)} Test Cover algorithm, and the O(n^{2-epsilon}) incompressibility results — are real and worth reading. The partition-refinement DP in Section 3 is a nice way to unify LDS and Test Cover, and it extends to twin-cover and distance to clique; the incompressibility proof via Red-Blue Dominating Set is clean and gives simpler proofs of some known non-kernel results. The paper is also honest about what it does not prove.

Second, the headline result — the O(fes) kernel for Locating-Dominating Set parameterized by feedback edge set number (Theorem 2) — is not established in this arXiv version. The proof relies on Reduction Rule 24, which replaces doubly-rooted tree components with constant-size gadgets from a class T_g (Definition 23). The existence and construction of these gadgets is deferred to an Appendix E that is not in the arXiv posting, and the only support offered for the claim that many classes are nonempty is a footnote about an empirical study that is not described. Since a kernelization has to be an explicit polynomial-time procedure, Rule 24 is not fully specified. This is a load-bearing gap, not a cosmetic one: without the appendix (or a proof that every occurring class has a bounded-size representative, or an explicit catalogue of gadgets), the linear kernel and the resolution of the LAGOS 2021 open question do not follow from the written text.

The rest of the paper is in better shape. The Section 3 DP has notational rough spots — the set T in the DP is never defined, and the WLOG twin swap in Lemma 6 is a little hand-wavy — but these look repairable, not fatal. The incompressibility reductions in Section 5 are standard in structure and appear correct, aside from minor typos.

Who is this for? People working on structural parameterizations, identification problems, or kernelization will want to know Theorems 1 and 3. The paper deserves a serious referee, and I would engage with it, but only after the authors supply the missing appendix and the empirical data. My recommendation: ask for the missing material. If Appendix E gives explicit gadgets or a finiteness proof, Theorem 2 likely goes through; if not, the paper should be revised to present it as a conditional result.

Referee Report

3 major / 4 minor

Summary. The paper studies two identification problems, Locating-Dominating Set and Test Cover, under structural parameterizations. It claims an FPT algorithm for Locating-Dominating Set parameterized by vertex cover number running in 2^{O(vc log vc)} n^{O(1)} and for Test Cover parameterized by the number of items running in 2^{O(|U| log |U|)} (|U|+|F|)^{O(1)}; a linear kernel for Locating-Dominating Set parameterized by feedback edge set number, answering an open question of Cappelle et al.; and a lower bound ruling out polynomial compressions of size O(n^{2-epsilon}) for either problem unless NP ⊆ coNP/poly. The paper also draws consequences for parameters such as twin-cover number, distance to clique, and neighbourhood diversity.

Significance. If the results are correct, Theorem 1 is a substantial algorithmic contribution: it shows that the double-exponential treewidth lower bound of Chakraborty et al. does not transfer to the larger vertex cover parameter, and the Test Cover algorithm improves on the naive 2^{O(|U|^2)} enumeration. Theorem 3 gives a clean incompressibility result via explicit reductions from Red-Blue Dominating Set. Theorem 2, if fully proved, would resolve the LAGOS 2021 open question. The paper also contains a reusable dynamic-programming framework for partition refinement. However, as submitted, Theorem 2 is not established because its central gadget construction is deferred to a missing Appendix E and supported only by an unreported empirical study, and the Section 3 DP has substantial formal gaps. The reductions in Section 5 are explicit and appear sound in outline, and the paper makes good use of known results such as Slater's bound, Bondy's theorem, and the incompressibility of Red-Blue Dominating Set.

major comments (3)

[Section 4, Definitions 22-23, Reduction Rule 24, Lemma 25] The proof of Theorem 2 is incomplete. Definition 23 defines the gadget (Tg,vX,vY) as the smallest tree in class Tg 'if such a tree exists', and Reduction Rule 24 replaces every tree corresponding to an edge of the multigraph with such a gadget. The text immediately before Definition 23 states that 'Missing parts of the proof are found in Appendix E', but the arXiv version has no Appendix E. The footnote after Definition 22 adds only that 'an empirical study shows that the number of nonempty classes is very large', without giving the study, the list of nonempty classes, or the gadgets. Since a kernelization must be a fully specified algorithm, the existence and construction of these constant-size gadgets is load-bearing for the claimed O(fes) kernel. Moreover, Lemma 25 asserts that any two trees in the same class Tg are interchangeable 'since they have the same behaviour', but the class is defined purely by the 25 optimal values opt_X,Y(T,v1,v2)-opt_A,A(T,v1,v2); the proof does not establish that this vector of values is a complete invariant for the interaction of the tree with an arbitrary outside graph through the two identified vertices. Consequently, Theorem 2 and the resolution of the LAGOS 2021 open question are not established as written.
[Section 3, Lemma 8 and surrounding text] The dynamic program for Annotated Red-Blue Partition Refinement is not fully specified. The set T used in the valid-tuple definition and in the recurrence (1) is never defined; the set T◦L is introduced without a formal definition; and the final query opt[ℓ,I(R∪B),T] uses an undefined object I(R∪B). More importantly, the preprocessing phase (from 'Pre-processing the Partition' through the 'sanity checks') modifies TL, adds vertices to C0, and enumerates subsets T◦L, but the correctness proof after Equation (1) never accounts for these modifications: it only proves the recurrence for tuples (i,P,S). The proof also does not justify that the partition P′ in the second transition of (1) is a valid tuple; it is merely declared to exist. Finally, the bound on the number of valid tuples is stated informally ('From the above three properties...') rather than proved. Since Lemma 8 is the technical core of Theorem 1, these gaps make the main algorithmic claim of the paper hard to verify.
[Section 3, paragraph after Lemma 6] The initialization of the partial solution YL is not justified correctly. The text says that for every pair of twins u,v the algorithm adds one of them to YL and that 'it is safe to assume that all the vertices in YL are present in any locating-dominating set'. Slater's bound only says that a locating-dominating set contains at least |S|-1 vertices of a twin class S; it does not say that a prescribed representative belongs to every solution. What is needed is an argument, using the symmetry of twins, that there exists a single optimal solution containing all chosen representatives simultaneously. The text does not provide this argument. In addition, when the algorithm later guesses XL = L∩U, it must enforce YL∩U ⊆ XL; the text does not state this consistency condition, so as written the algorithm may force a vertex into YL and then exclude it from XL.

minor comments (4)

[Section 2, Observation 4] In the proof of Observation 4, the sentence 'w was not adjacent with any vertex in S′\{v}=S\{u}' only contradicts the fact that S is a dominating set if w∉S; this should be stated explicitly. The phrase 'apart from u in the neighbourhood of v' is also unclear.
[Section 3, paragraph 'Parameterization by the number of items for Test Cover'] There is a grammatical error: 'We find it convenient to with the auxiliary graph representation' should read 'to work with the auxiliary graph representation'.
[Throughout] There are several typos: 'Thereom 3' in Section 5, 'repeatedely' in the proof of Lemma 10, and 'Locating Dominating Set' missing a hyphen in the abstract. A careful proofreading pass is needed.
[Section 3, Definition 7] In the definition of P(C), the symbol V is used both for the ambient vertex set and for the subset on which the partition is defined; using a different symbol for the subset would avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithmic cores in Theorems 1 and 3 are self-contained and the external lower bound is independent; Theorem 2's kernel proof is incomplete because Appendix E and the constant-size gadget bound are missing, but that is a correctness gap, not circularity.

full rationale

The main derivation chains do not reduce to their own inputs. Theorem 1 is a direct algorithmic construction: the paper defines the auxiliary Annotated Red-Blue Partition Refinement problem, proves Lemma 8 with an inductive correctness proof for its dynamic program, and then reduces Locating-Dominating Set and Test Cover to this problem. The uses of Slater's twin bound (Observation 4, Lemma 6) and Bondy's theorem are external results that do not assume the target claims. Theorem 3 is a standard reduction from Red-Blue Dominating Set, whose incompressibility is cited from [1, Proposition 2] and from the textbook [18, Lemma 15.19]; although reference [1] is co-authored by Prafullkumar Tale, the cited proposition is an independent published lower bound for a different problem, not a fitted value or an assertion of the current paper, so it does not constitute load-bearing self-citation under the stated rules. The only serious defect is in Theorem 2 (Section 4): the doubly-rooted tree gadgets of Definition 23 are existential, the text states 'Missing parts of the proof are found in Appendix E' before Definition 23, Appendix E is absent from this arXiv version, and Lemma 25 asserts without proof that 'the gadget Tg is of constant size.' The footnote's 'empirical study' about nonempty classes is informal and is not used to prove the kernel bound. These are genuine completeness gaps that make the advertised linear kernel unproven as written, but they are missing proofs rather than circular reasoning: the class definitions and the gadget replacement do not presuppose the kernel-size conclusion, and the intended interchangeability argument is the standard same-class replacement, which would be valid if the missing existence and size lemmas were supplied.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper's central claims rest on standard external theorems plus one ad hoc assumption: the existence and availability of constant-size doubly-rooted tree gadgets for every nonempty class, which is not established in the main text and is deferred to a missing appendix. No numeric free parameters are fitted to data.

assumptions (5)

domain assumption Red-Blue Dominating Set admits no polynomial compression of O(n^{2-epsilon}) bits unless NP is contained in coNP/poly.
Imported from [1, Proposition 2] and used in Section 5 to transfer incompressibility to Locating-Dominating Set and Test Cover.
domain assumption Every graph with feedback edge set number fes decomposes into a multigraph core of O(fes) vertices and edges, subdivided edges, and pendant trees.
Proposition 12 is cited from [30, Observation 8] and is the structural basis for the feedback edge set kernel in Section 4.
ad hoc to paper For every nonempty class T_g of doubly-rooted trees, a constant-size smallest tree T_g exists and its value k_g = opt_{A,A}(T_g,v_X,v_Y) is available.
Definition 23 asserts this existence nonconstructively, but the construction is deferred to the missing Appendix E and an unreported empirical study in the footnote.
standard math For any set S of twin vertices, every locating-dominating set contains at least |S|-1 vertices of S.
This is Slater's theorem, cited as [36], and is used in Reduction Rule 5 and in the initialization of the partial solution Y_L in Section 3.
standard math Test Cover always has a solution of size at most |B|-1, where B is the item set.
This is Bondy's theorem, cited as [6], and is used to justify the brute-force baseline and parameter bounds in the Test Cover section.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Structural Parameterization of Locating-Dominating Set and Test Cover." pith.science (2026). https://pith.science/paper/Q3Q2CEZF

@misc{pith2026241117948,
  author       = {Pith},
  title        = {Pith review of: Structural Parameterization of Locating-Dominating Set and Test Cover},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q3Q2CEZF}},
  note         = {Machine review of arXiv:2411.17948}
}

abstract

We investigate structural parameterizations of two identification problems: LOCATING-DOMINATING SET and TEST COVER. In the first problem, an input is a graph $G$ on $n$ vertices and an integer $k$, and one asks if 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 set of subsets $\mathcal{F}$ of $U$ called $tests$ and an integer $k$, and one asks if there is a set $S$ of at most $k$ tests such that any two items belong to distinct subsets of tests of $S$. These two problems are "identification" analogues of DOMINATING SET and SET COVER, respectively. Chakraborty et al. [ISAAC 2024] proved that both the problems admit conditional double-exponential lower bounds and matching algorithms when parameterized by 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 to solve TEST COVER in "slightly super-exponential" time $2^{O(|U|\log |U|)}(|U|+|\mathcal{F}|)^{O(1)}$ in the number $|U|$ of items and LOCATING-DOMINATING SET in time $2^{O(\textsf{vc} \log \textsf{vc})} \cdot n^{O(1)}$, where $\textsf{vc}$ is the vertex cover number and $n$ is the order of the graph. This shows that the lower bound results with respect to treewidth from Chakraborty et al. [ISAAC 2024] cannot be extended to vertex cover number. We also show that, parameterized by feedback edge set number, LOCATING-DOMINATING SET admits a linear kernel thereby answering an open question in [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, unless $\textsf{NP} \subseteq \textsf{coNP}/poly$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 11 canonical work pages

[4]

Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover

10 Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, and Prafullkumar Tale. Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover. CoRR, abs/2402.08346,

arXiv
[6]

12 Bogdan S

URL:https://arxiv.org/abs/2406.19278, arXiv: 2406.19278. 12 Bogdan S. Chlebus and Sinh Hoa Nguyen. On finding optimal discretizations for two attributes. In Proceedings of the First International Conference on Rough Sets and Current Trends in Computing, volume 1424, pages 537–544, Berlin, Heidelberg,

arXiv
[11]

Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover

23 Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors,51st International Colloquium on Automata, Languages, a...

work page 2024
[12]

24 Florent Foucaud, George B Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov

URL:https: //doi.org/10.4230/LIPIcs.ICALP.2024.66, doi:10.4230/LIPICS.ICALP.2024.66. 24 Florent Foucaud, George B Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. algorithms and complexity.Algorithmica, 78(3):914–944,

work page doi:10.4230/lipics.icalp.2024.66 2024
[17]

30 Leon Kellerhals and Tomohiro Koana

URL:https: //doi.org/10.4230/LIPIcs.STACS.2024.40, doi:10.4230/LIPICS.STACS.2024.40. 30 Leon Kellerhals and Tomohiro Koana. Parameterized complexity of geodetic set.J. Graph Algorithms Appl., 26(4):401–419,

doi:10.4230/lipics.stacs.2024.40 2024
[18]

32 Bernard M

URL: https://doi.org/10.1007/s00453-011-9554-x, doi:10.1007/ S00453-011-9554-X. 32 Bernard M. E. Moret and Henry D. Shapiro. On minimizing a set of tests.SIAM Journal on Scientific and Statistical Computing, 6(4):983–1003,

doi:10.1007/s00453-011-9554-x
[1987]

36 Peter J. Slater. Dominating and reference sets in a graph.Journal of Mathematical and Physical Sciences, 22(4):445–455, 1988

work page 1988
[1998]

29 David G

Springer-Verlag. 29 David G. Harris and N. S. Narayanaswamy. A faster algorithm for vertex cover parameterized by solution size. In Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov, editors,41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France, volum...

work page 2024

Show all 18 references

[2011]

doi:10.1007/978-3-642-28050-4\_21. 26 M. R. Garey and D. S. Johnson.Computers and Intractability - A guide to NP-completeness. W.H. Freeman and Company,

doi
[2012]

20 Fedor V

URL: https://dblp.org/rec/books/daglib/0030488.bib. 20 Fedor V. Fomin and Dieter Kratsch.Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010.doi:10.1007/978-3-642-16533-7. 21 Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and ...

2010
[2013]

A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata

28 Michel Habib, Christophe Paul, and Laurent Viennot. A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata. InProceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998), pages 25–38, Ber...

1998
[2015]

19 Reinhard Diestel

doi:10.1007/978-3-319-21275-3. 19 Reinhard Diestel. Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics. Springer,

doi
[2016]

Gutin, Mark Jones, Saket Saurabh, and Anders Yeo

17 Robert Crowston, Gregory Z. Gutin, Mark Jones, Saket Saurabh, and Anders Yeo. Paramet- erized study of the test cover problem. In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors,Mathematical Foundations of Computer Science 2012 - 37th International Symposium...

2012
[2017]

Twin-cover: Beyondvertexcoverinparameterizedalgorithmics

25 RobertGanian. Twin-cover: Beyondvertexcoverinparameterizedalgorithmics. InDánielMarx and Peter Rossmanith, editors,Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8,

2011
[2019]

15 Bruno Courcelle

doi:10.1145/3310228. 15 Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12–75,

doi
[2020]

9 Márcia R

URL: https://arxiv.org/abs/2011.14849, arXiv:2011.14849. 9 Márcia R. Cappelle, Guilherme C. M. Gomes, and Vinícius Fernandes dos Santos. Para- meterized algorithms for locating-dominating sets. In Carlos E. Ferreira, Orlando Lee, and Flávio Keidi Miyazawa, editors,Proceedings ...

2011 arXiv
[2021]

2021.01.033, doi:10.1016/J.TCS.2021.01.033

URL:https://doi.org/10.1016/j.tcs. 2021.01.033, doi:10.1016/J.TCS.2021.01.033. 2 Gabriela R. Argiroffo, Silvia M. Bianchi, Yanina Lucarini, and Annegret Katrin Wagler. Linear- time algorithms for three domination-based separation problems in block graphs.Discret. Appl. Math., ...

2021 doi
[2024]

11 Dipayan Chakraborty, Anni Hakanen, and Tuomo Lehtilä

URL:https://doi.org/10.48550/arXiv.2402.08346, arXiv:2402.08346, doi:10.48550/ARXIV.2402.08346. 11 Dipayan Chakraborty, Anni Hakanen, and Tuomo Lehtilä. The n/2-bound for locating- dominating sets in subcubic graphs,

doi arXiv

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [4]

Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover

10 Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, and Prafullkumar Tale. Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover. CoRR, abs/2402.08346,

arXiv

[2] [6]

12 Bogdan S

URL:https://arxiv.org/abs/2406.19278, arXiv: 2406.19278. 12 Bogdan S. Chlebus and Sinh Hoa Nguyen. On finding optimal discretizations for two attributes. In Proceedings of the First International Conference on Rough Sets and Current Trends in Computing, volume 1424, pages 537–544, Berlin, Heidelberg,

arXiv

[3] [11]

Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover

23 Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors,51st International Colloquium on Automata, Languages, a...

work page 2024

[4] [12]

24 Florent Foucaud, George B Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov

URL:https: //doi.org/10.4230/LIPIcs.ICALP.2024.66, doi:10.4230/LIPICS.ICALP.2024.66. 24 Florent Foucaud, George B Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. algorithms and complexity.Algorithmica, 78(3):914–944,

work page doi:10.4230/lipics.icalp.2024.66 2024

[5] [17]

30 Leon Kellerhals and Tomohiro Koana

URL:https: //doi.org/10.4230/LIPIcs.STACS.2024.40, doi:10.4230/LIPICS.STACS.2024.40. 30 Leon Kellerhals and Tomohiro Koana. Parameterized complexity of geodetic set.J. Graph Algorithms Appl., 26(4):401–419,

doi:10.4230/lipics.stacs.2024.40 2024

[6] [18]

32 Bernard M

URL: https://doi.org/10.1007/s00453-011-9554-x, doi:10.1007/ S00453-011-9554-X. 32 Bernard M. E. Moret and Henry D. Shapiro. On minimizing a set of tests.SIAM Journal on Scientific and Statistical Computing, 6(4):983–1003,

doi:10.1007/s00453-011-9554-x

[7] [1987]

36 Peter J. Slater. Dominating and reference sets in a graph.Journal of Mathematical and Physical Sciences, 22(4):445–455, 1988

work page 1988

[8] [1998]

29 David G

Springer-Verlag. 29 David G. Harris and N. S. Narayanaswamy. A faster algorithm for vertex cover parameterized by solution size. In Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov, editors,41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France, volum...

work page 2024