{"id":"b7f6f439-a557-4d36-bab4-2014618f6dfa","arxiv_id":"2411.17948","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New parameterized algorithms and a feedback-edge-set kernel for Locating-Dominating Set and Test Cover are claimed, together with quadratic-bit incompressibility results.","lead":"This paper designs faster algorithms, a linear kernel, and incompressibility proofs for two NP-complete identification problems, Locating-Dominating Set and Test Cover, parameterized by structural graph measures. It shows that known treewidth-based double-exponential lower bounds do not extend to the vertex cover parameter, while flagging a missing proof appendix for one kernel result.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's feedback-edge-set kernel depends on nonexplicit doubly-rooted tree gadgets in a missing Appendix E; the paper's only support is an unreported empirical study, so the kernel is unproven as written.","rationale":"The strongest advertised contributions are Theorems 1–3. The most load-bearing is Theorem 2 because it answers an open question and the linear kernel is a headline result. Its proof pivots on Reduction Rule 24, which requires constant-size doubly-rooted tree gadgets for each class Tg. The paper explicitly defers the construction to Appendix E, which is absent, and the only evidence for nonempty classes is an unreported 'empirical study.' This is precisely a claim-without-derivation on a load-bearing step; there is no way to verify the kernelization from the text. The reader's weakest_assumption identified exactly this, and I agree. Theorem 1's DP appears plausible (though notationally loose), and Theorem 3's reduction is standard in outline, but neither compensates for the missing core of the kernel. The verdict should remain unchanged: as a preprint it is incomplete; with Appendix E supplied it could become acceptable, but that is not the version under review.","tokens_in":26724,"tokens_out":15299,"duration_ms":138964,"concrete_test":"Reconstruct the missing Appendix E computationally: for each of the 3^25 functions g, enumerate all doubly-rooted trees in increasing order of size, compute the 25 opt-values via the DP of Proposition 20, and record the smallest representative of each nonempty class; then check that every class occurring in Proposition 12's decomposition is in this list. If the enumeration cannot be completed (e.g., no finite upper bound on the minimal representative size is established), Reduction Rule 24 is not an executable algorithm and Theorem 2 remains unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4, Definitions 22–23 and Reduction Rule 24, are the load-bearing core of Theorem 2 (the O(fes) kernel). The rule replaces every tree (T,v1,v2) corresponding to an edge of the multigraph ~G with a 'doubly-rooted tree gadget' (Tg,vX,vY), defined as the smallest tree in the class Tg. The proof of Lemma 25 asserts that any two trees in the same class are interchangeable. However, the construction and existence of these gadgets is explicitly deferred: the text before Definition 23 says 'Missing parts of the proof are found in Appendix E,' and the arXiv version has no Appendix E. Moreover, the footnote after Definition 22 states only that 'an empirical study shows that the number of nonempty classes is very large,' without giving the study, the nonempty classes, or the gadgets. Since a kernelization must be an explicit polynomial-time procedure, the absence of a finite catalogue of gadgets (or of a proof that all occurring classes have bounded-size representatives) means Reduction Rule 24 is not a fully specified algorithm. The rest of the paper's Theorem 1 and Theorem 3 may be salvageable, but the advertised linear kernel and the resolution of the LAGOS 2021 open question are not established in this version.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":26953,"tokens_out":25700,"duration_ms":247457,"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":[{"comment":"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":"Section 4, Definitions 22-23, Reduction Rule 24, Lemma 25"},{"comment":"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":"Section 3, Lemma 8 and surrounding text"},{"comment":"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.","section":"Section 3, paragraph after Lemma 6"}],"minor_comments":[{"comment":"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":"Section 2, Observation 4"},{"comment":"There is a grammatical error: 'We find it convenient to with the auxiliary graph representation' should read 'to work with the auxiliary graph representation'.","section":"Section 3, paragraph 'Parameterization by the number of items for Test Cover'"},{"comment":"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":"Throughout"},{"comment":"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.","section":"Section 3, Definition 7"}],"recommendation":"major_revision","confidential_remarks":"The absence of Appendix E and the reliance on an unreported 'empirical study' in the proof of Theorem 2 are serious omissions; the paper should not have been submitted in this form. I recommend major revision rather than rejection because the gaps appear fixable -- the kernel can likely be made explicit by a finite search argument, and the Section 3 DP can be completed by supplying the missing definitions and a formal correctness proof. If the authors cannot supply the missing appendix or the substitutability proof for doubly-rooted tree gadgets, Theorem 2 should be removed or clearly marked as conditional."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nSecond, 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":27502,"tokens_out":3903,"would_cite":true,"duration_ms":33015,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Identification Problems","Locating-Dominating Set","Test Cover","Parameterized Algorithms","Structural Parameterizations","Kernelization","Vertex Cover Number","Feedback Edge Set Number"],"falsifier":"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.","tokens_in":2418,"feed_emoji":"🎯","tokens_out":11865,"duration_ms":174832,"temperature":0.7,"pith_summary":"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}$.","feed_headline":"Vertex cover and feedback edge set tame two identification problems","feed_subtitle":"FPT algorithms run in near-optimal time and yield linear kernels; quadratic compression is ruled out.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the treewidth double-exponential lower bounds that the new results show do not transfer to vertex cover number.","marker":"[10]"},{"why":"Raised the open question of a feedback-edge-set kernel for Locating-Dominating Set.","marker":"[8, 9]"},{"why":"Proves that any locating-dominating set must contain $|S|-1$ vertices of a twin class $S$, used by Reduction Rule 5 and the forced-choice step.","marker":"[36]"},{"why":"Provides the linear-time tree dynamic programming for the five solution types used in the feedback edge set kernel.","marker":"[35]"},{"why":"Gives the decomposition of bounded-feedback-edge-set graphs into a small multigraph with subdivided edges and pendant trees.","marker":"[30, Observation 8]"},{"why":"Bondy's theorem bounds Test Cover solutions by $|U|-1$, which limits $k$ and supports the algorithm.","marker":"[6]"},{"why":"Supplies the Set Cover dynamic programming scheme whose complexity the Test Cover algorithm matches and improves.","marker":"[20, Theorem 3.10]"},{"why":"Establishes the quadratic incompressibility of Red-Blue Dominating Set, the source problem for the reductions.","marker":"[1, Proposition 2]"},{"why":"Provides the fast minimum vertex cover algorithm used to locate the vertex cover before applying the dynamic program.","marker":"[29]"}],"fun_headline_variants":["Vertex cover beats treewidth lower bounds for identification problems","Feedback edge set yields linear kernel for locating-dominating set","No polynomial compression for locating-dominating set or test cover","FPT algorithms for vertex cover parameterization of identification problems","Identification problems: FPT by vertex cover, linear kernel by feedback edge set"],"cache_read_input_tokens":29568,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Vertex cover beats treewidth lower bounds for identification problems","Feedback edge set yields linear kernel for locating-dominating set","No polynomial compression for locating-dominating set or test cover","FPT algorithms for vertex cover parameterization of identification problems","Identification problems: FPT by vertex cover, linear kernel by feedback edge set"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000804,"raw_usage":{"total_tokens":3673,"prompt_tokens":1229,"completion_tokens":2444,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":845,"completion_tokens_details":{"reasoning_tokens":2358}},"tokens_in":845,"tokens_out":2444,"duration_ms":15428,"temperature":1.0,"reasoning_tokens":2358,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:41:03.646405+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}