{"id":"3b314ffb-15d9-44cc-9cef-8185dcbc1e42","arxiv_id":"2504.21675","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Dominated Cluster Deletion and elimination distance to dominated clusters are uniformly fixed-parameter tractable in f(k,d)·n^{O(d)} and, on graphs of semi-ladder index ℓ, in f(k,d,ℓ)·n^{O(1)}.","lead":"The paper gives fast parameterized algorithms for two graph problems where the goal is to delete vertices so that every remaining component has a small dominating set. It resolves an open question from a 2024 conference paper by making a previously non-uniform algorithm uniform and extending it to a very general class of graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"FPT-by-semi-ladder-index claims rest on an unreviewed meta-theorem, and Lemma 48's bag-graph preservation proof has a shifted-index gap.","rationale":"The reader's weakest_assumption identifies exactly the dependence on Theorem 4 of the unreviewed preprint [20] as the load-bearing risk, and I agree. This is the single point whose failure would collapse the central FPT-by-semi-ladder-index claims, including the positive resolution of Bentert et al.'s open question. I additionally note that Lemma 48's proof, which is needed to apply the meta-theorem to bag graphs, contains a shifted-index construction that does not preserve the diagonal non-adjacency condition; however, this appears fixable with a slightly weaker bound and so is secondary. The uniform f(k,d)n^{O(d)} algorithms are independent of these steps and are supported by the paper's own decomposition and DP arguments. The proper remedy is to require the authors to supply a proof of Theorem 4 or a pointer to a peer-reviewed version, plus a corrected Lemma 48 proof, which is exactly the CONDITIONAL verdict the reader already reached. Hence my recommendation is no change to the reader's verdict.","tokens_in":27398,"tokens_out":33925,"duration_ms":344485,"concrete_test":"Provide a self-contained proof of Theorem 4 of [20] for the specific formula delta_{k,d} on semi-ladder-free graphs, including the composition lemmas cited in Lemma 5, and re-verify Lemma 48 by taking a middle subsequence with matching indices (a_{q+5},...,a_{t-q-4} and b_{q+5},...,b_{t-q-4}). If the matching-index construction is the best possible, the stated q+ell+4 bound is false but the FPT consequence may survive with a larger function; if Theorem 4 cannot be re-derived, the semi-ladder-index claims in Theorems 1 and 2 are unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorems 1 and 2 (second running times) rely on Corollary 6, which is derived from Theorem 4 of the unreviewed preprint [20]. The paper's Lemma 5 does not prove the required composition facts; it cites Lemmas 4 and 5 of [20], a preprint coauthored by one of the present authors. If Theorem 4 fails, or does not apply to the colored bag graphs used in the DP, the positive answer to Bentert et al.'s open question is unsupported. Additionally, Lemma 48, which is needed to transfer bounded semi-ladder index from G to bag graphs, has a concrete gap: it claims that a_{q+5},...,a_t and b_1,...,b_{t-q-4} form a semi-ladder of G, but this pairs a_{q+4+i} with b_i, and the required non-edge {a_{q+4+i}, b_i} is not implied by the semi-ladder condition, which only forbids {a_j,b_j}. The uniform f(k,d)n^{O(d)} results do not depend on these steps and are not affected by this concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two graph modification problems: Dominated Cluster Deletion, where one deletes at most k vertices so that every remaining connected component has a dominating set of size at most d, and its recursive analogue Elimination Distance to Dominated Clusters. The main results are a uniform algorithm running in time f(k,d)·n^{O(d)} for both problems and an FPT algorithm with running time f(k,d,ℓ)·n^{O(1)}, where ℓ is the semi-ladder index of the input graph. The latter result is claimed to answer positively the open question of Bentert et al. on fixed-parameter tractability with respect to k+d+c, since bounded degeneracy implies bounded semi-ladder index. The paper also supplies a classification of hardness and kernelization for the elimination-distance variant: para-NP-hardness for k+Δ and for d, W[2]-hardness for k+d, and the absence of a polynomial kernel for parameter k even when d=0 and c=2.","tokens_in":27626,"tokens_out":20980,"duration_ms":215485,"significance":"If the main theorems are correct, the paper is a genuine advance: it replaces a non-uniform algorithm of Bentert et al. by a uniform f(k,d)·n^{O(d)} algorithm and introduces a new structural parameter (semi-ladder index) under which both problems become FPT, thereby resolving the open question about degeneracy. The hardness and kernelization classification for the elimination-distance variant is also valuable. The paper is well structured and the appendix contains substantial technical material. However, the FPT-by-semi-ladder-index claim currently rests on two load-bearing steps that are not fully supported: an external meta-theorem cited from an unreviewed preprint with overlapping authorship, and a transfer lemma (Lemma 48) whose proof contains a shifted-index gap. These issues do not affect the f(k,d)·n^{O(d)} uniform algorithms, but they must be resolved before the main FPT claim can be accepted.","major_comments":[{"comment":"The proof of Lemma 48 asserts that a_{q+5},...,a_t and b_1,...,b_{t-q-4} form a semi-ladder of G. Pairing these sequences termwise gives pairs (a_{q+4+i}, b_i) for i=1,...,t-q-4. For such a pair, the original semi-ladder condition implies that {a_{q+4+i}, b_i} is an edge, because q+4+i > i; the semi-ladder definition instead requires a non-edge on the diagonal. Hence the constructed pair of sequences is not a semi-ladder, and the claimed bound t ≤ q+ℓ+4 does not follow. This lemma is the only step establishing that the semi-ladder index has Property 2, so the f(k,d,ℓ)·n^{O(1)} running times in Theorems 1 and 2 are currently unsupported. The gap appears repairable: one can take a same-index middle subsequence and absorb all gadget vertices into an additive O(q+d) term, which still suffices for Property 2, but the proof must be rewritten.","section":"Section 3, Theorem 4 and Corollary 6"},{"comment":"The semi-ladder-index results depend entirely on Theorem 4 of [20] and on Lemmas 4–5 of that same arXiv preprint, which is coauthored by one of the present authors and is not proved in this manuscript. The proof of Lemma 5 is only a citation to those lemmas, and Corollary 6 inherits the full weight of the external result. If [20] is not yet available in a peer-reviewed venue, the authors should provide a self-contained proof of the specific evaluation and closure facts needed for the formula δ_{k,d}; alternatively, they should cite a published version with a DOI. As written, a referee cannot verify the main FPT claim without relying on an external unreviewed source.","section":"Appendix B.2, Claim 50 and Lemma 53"},{"comment":"The correctness argument for the dynamic programming step (Proposition 49) is highly compressed. Claim 50 is proved in two paragraphs that do not state a formal invariant connecting the selected marks of the children, the counter c, the partition P, and the constructed bag graph H; for example, it is not shown precisely how the pi-gadgets encode the requirement that each component's Blue dominating set has size at most p and how the count |D|+c is maintained across the branching. Lemma 53 also needs a precise argument that every branching step increases |S|+s or |D|+c, since the branch that selects a mark with ky=0 and all pi=0 is supposed to make no progress. These gaps make the proof of the central DP difficult to verify and should be expanded.","section":"Appendix B.2"}],"minor_comments":[{"comment":"In the proof of Lemma 37, the text bounds the number of Red exterior vertices in G−C0 by qd, but this does not follow from the assumption |E∩B|≤qd and appears inconsistent with the later bound '3qd+q' used in the same appendix. The constants should be reconciled.","section":"Appendix A"},{"comment":"In the definition of N[Y], the displayed formula '⋃_{v∈Y} N[y]' mixes the variables y and v; it should be '⋃_{v∈Y} N[v]'.","section":"Section 2"},{"comment":"The statement that for |G|≥2q+1 every deletion of at most k vertices leaves a unique connected component with more than q vertices is not justified by size alone; a graph could in principle break into several components all of size at most q. The subsequent lemmas that invoke C0 (Lemma 8, Lemma 13) should either prove this claim from (q,k)-unbreakability or explicitly handle the case where no large component exists.","section":"Section 4"},{"comment":"There is a typo in 'sudivision vertex' and the proof would benefit from a figure or a more detailed exchange argument, since the claim that a subdivision vertex can always be swapped with an endpoint without increasing depth is stated rather than shown.","section":"Section 6"}],"recommendation":"major_revision","confidential_remarks":"The most serious verification issue is the reliance on [20]: if that preprint is not yet peer-reviewed, the paper should not present Theorem 4 as a black box. The flaw in Lemma 48 is concrete but seems fixable, so I would not reject on that basis alone. I would also ask the editor to verify that the correctness proof of the DP in Appendix B is completed to the standard required by the journal, since it is currently more of a proof sketch."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"One thing to know: the uniform f(k,d)·n^{O(d)} algorithm for both problems is the real contribution and it looks solid. The stronger FPT claim for parameter k+d+ℓ is the headline, but it depends on an unreviewed preprint and there is a proof gap in Lemma 48 that needs fixing.\n\nThe paper answers the open question of Bentert et al. in a clean way. The key move is to replace the non-uniform recursive understanding with Cygan et al.'s unbreakable tree decompositions, then run a DP that reduces to annotated partial domination on bag graphs. That gives the uniform n^{O(d)} bound for Dominated Cluster Deletion and for the new Elimination Distance variant. The hardness part is simple but completes the classification nicely, and the treedepth-on-2-degenerate kernel lower bound is a nice observation.\n\nWhere are the soft spots? First, the f(k,d,ℓ) results use Corollary 6, which is Theorem 19 of Fabiański et al. [20], an arXiv preprint coauthored by one of the present authors. That is not fatal in the field, but the paper should either prove it in an appendix or point to a peer-reviewed version, because the two main theorems lean on it. Second, Lemma 48, which transfers bounded semi-ladder index from G to the bag graphs, has a concrete bug in the proof as written. The argument takes a tail of the a's and a prefix of the b's, but then pairs the i-th a with the i-th b of the original sequence, so the diagonal non-edge becomes {a_{q+4+i}, b_i}, which may actually be an edge by the original semi-ladder condition (since q+4+i > i). The fix is to pair same-offset vertices in the uncontaminated middle of both sequences, which gives t ≤ ℓ+O(q+d) instead of the claimed q+ℓ+4. The qualitative conclusion still works, but the constants need correcting and the proof needs rewriting. This does not affect the n^{O(d)} uniform algorithms, which go through the |bgraph|^d route.\n\nThird, the DP in Appendix B is dense and several steps are delegated to straightforward adaptation; a referee with time will want to verify the marks and the black-white tree argument. None of this looks load-bearing—the central argument holds up.\n\nBottom line: for the uniform n^{O(d)} results and the classification, this is a solid paper that deserves a serious referee. The FPT-by-semi-ladder result is plausible but needs the preprint dependency resolved and Lemma 48 repaired. I'd send it out.","headline":"Uniform f(k,d)n^{O(d)} algorithm is solid and answers the open question; the stronger semi-ladder-index FPT result has a repairable proof gap in Lemma 48 and depends on an unreviewed preprint.","tokens_in":28136,"tokens_out":5886,"would_cite":true,"duration_ms":54314,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","05C69","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves uniform fixed-parameter algorithms for Dominated Cluster Deletion and Elimination Distance to Dominated Clusters, with the second running in $f(k,d,\\ell)\\cdot n^{O(1)}$ where $\\ell$ is the semi-ladder index.","keywords":["dominated cluster deletion","elimination distance","semi-ladder index","fixed-parameter tractability","parameterized complexity","tree decompositions","unbreakable graphs","domination"],"falsifier":"Exhibit a graph class with bounded semi-ladder index on which Annotated Partial Domination, specifically the formula $\\delta_{k,d}$ used in the proof, cannot be solved in $f(d,k,\\ell)\\cdot n^{O(1)}$ time, or produce a distance formula $\\delta$ whose associated bipartite graph has bounded semi-ladder index but whose decision problem is not fixed-parameter tractable; either would falsify Theorem 4 and with it Theorems 1 and 2.","tokens_in":27217,"feed_emoji":"🧩","tokens_out":10002,"duration_ms":92491,"temperature":0.7,"pith_summary":"This paper claims that two related graph-deletion problems are easier than previously known. Dominated Cluster Deletion and Elimination Distance to Dominated Clusters each admit a uniform algorithm with running time $f(k,d)\\cdot n^{O(d)}$ on all graphs, and each admits an FPT algorithm with running time $f(k,d,\\ell)\\cdot n^{O(1)}$ when the input graph has semi-ladder index $\\ell$. Because every class of bounded degeneracy also has bounded semi-ladder index, this settles the open question of whether the problems are FPT for the parameter $k+d+c$. The paper also completes nearly all of the complexity and kernelization classification for the recursive version, leaving only the treedepth case on bounded-degree graphs open.","feed_headline":"Both dominated-cluster deletion problems are fixed-parameter tractable","feed_subtitle":"A width parameter called the semi-ladder index makes both one-shot and recursive deletion tractable.","key_machinery":"The argument runs through three linked devices. First, an unbreakable tree-decomposition theorem produces bags that cannot be split in a balanced way by separators of order at most $k$, so after deleting $k$ vertices each instance has one large connected component and only small ones. Second, the dynamic program works on bag graphs: the small components are compressed into $d$-gadgets, and the decision problems on each bag reduce to an instance of Annotated Partial Domination. Third, the semi-ladder index governs the runtime: the semi-ladder is the largest $n$ for which two sequences of distinct vertices satisfy $a_i b_j\\in E(G)$ for $i>j$ and $a_i b_i\\notin E(G)$, and on classes with bounded semi-ladder index the cited meta-theorem evaluates the needed domination-type formula in linear time. This combination is what turns the tree decomposition into an $f(k,d,\\ell)\\cdot n^{O(1)}$ algorithm, and the same skeleton-and-bag-graph machinery produces the uniform $f(k,d)\\cdot n^{O(d)}$ algorithm on general graphs.","core_discovery":"The central claim is that both deletion problems become uniformly tractable. For any computable function $f$, Dominated Cluster Deletion can be solved in time $f(k,d)\\cdot n^{O(d)}$ and in time $f(k,d,\\ell)\\cdot n^{O(1)}$, and the same two running-time bounds hold for Elimination Distance to Dominated Clusters, where $\\ell$ is the semi-ladder index of the input graph. The first bound upgrades a previously non-uniform algorithm to a uniform one. The second covers every semi-ladder-free graph class, which includes all degenerate and biclique-free classes, and therefore implies fixed-parameter tractability with respect to $k+d+c$, answering the open question from the earlier classification. Alongside the algorithms, the paper shows Elimination Distance to Dominated Clusters is para-NP-hard for parameter $k+\\Delta$ and for parameter $d$, $W[2]$-hard for $k+d$, and admits no polynomial kernel for parameter $k$ even when $d=0$ and $c=2$, unless $\\mathrm{NP}\\subseteq \\mathrm{coNP}/\\mathrm{poly}$.","pith_inferences":["If the cited semi-ladder meta-theorem is correct, the same machinery should give uniform FPT algorithms for other deletion problems whose target class is defined by small dominating sets, such as Red-Blue domination variants, on all semi-ladder-free classes.","The collapse of elimination distance to deletion distance on unbreakable graphs suggests a general principle: once a graph is unbreakable, recursive deletion adds no extra hardness for hereditary-style target classes; this could simplify other elimination-distance algorithms.","The bound in Lemma 48 that every bag graph inherits semi-ladder index at most $q+\\ell+4$ is directly checkable on synthetic semi-ladder-free instances and would provide an empirical sanity check independent of the preprint's meta-theorem.","The real remaining barrier is treedepth on bounded-degree graphs; if that case is NP-hard, the $d+\\Delta$ parameter becomes para-NP-hard and the classification is complete."],"forward_implications":["The earlier non-uniform $f(k,d)\\cdot n^{O(d)}$ algorithm for Dominated Cluster Deletion is replaced by one uniform algorithm, with the same dependence on $n$.","Open question answered: both problems are FPT for $k+d+c$, since the semi-ladder index is no larger than the degeneracy $c$ and is often much smaller.","The FPT result transfers to every graph class on which Annotated Partial Domination is FPT and the parameter transfers to bag graphs, not only to semi-ladder-free classes.","Recursive deletion to dominated clusters is tractable on the same broad classes as one-shot deletion, so measuring distance by elimination depth does not add hardness there.","The classification of Elimination Distance to Dominated Clusters is almost complete: only the $d=0$ treedepth case on bounded maximum degree remains open, and no polynomial kernel exists for parameter $k$ with $d=0$ and $c=2$ unless $\\mathrm{NP}\\subseteq \\mathrm{coNP}/\\mathrm{poly}$."],"supporting_citations":[{"why":"Supplies the problem definitions, the earlier non-uniform $f(k,d)\\cdot n^{O(d)}$ algorithm, and the open question about parameter $k+d+c$ that this paper answers.","marker":"[4]"},{"why":"Provides the unbreakable tree-decomposition theorem that reduces general graphs to bags with small adhesions and unbreakable interiors.","marker":"[13]"},{"why":"Introduces the semi-ladder index and the meta-theorem that domination-type formulas with bounded semi-ladder index can be evaluated in linear time; the main FPT results depend on it.","marker":"[20]"},{"why":"The non-uniform recursive-understanding framework that the earlier algorithm used and that the present dynamic program replaces with a uniform approach.","marker":"[29]"},{"why":"Introduces elimination distance and the elimination-order characterization on which the recursive version of the problem is based.","marker":"[10]"},{"why":"Establishes NP-hardness of treedepth, which yields para-NP-hardness for parameter $d$ and the kernel lower bound for $d=0$.","marker":"[32]"}],"fun_headline_variants":["Semi-ladder index unlocks FPT for cluster deletion","Both dominated cluster deletion problems go FPT","Uniform FPT algorithms for cluster deletion problems","New width parameter tames two deletion problems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on a theorem the paper cites but does not prove: on graphs where the semi-ladder index is bounded, the class of domination-type formulas used in the proof can be evaluated in linear time; if that cited theorem fails or does not apply to the bag graphs constructed here, both main algorithms collapse.","fun_headline_variants_meta":{"raw":{"variants":["Semi-ladder index unlocks FPT for cluster deletion","Both dominated cluster deletion problems go FPT","Uniform FPT algorithms for cluster deletion problems","New width parameter tames two deletion problems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000851,"raw_usage":{"total_tokens":3808,"prompt_tokens":1164,"completion_tokens":2644,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":780,"completion_tokens_details":{"reasoning_tokens":2586}},"tokens_in":780,"tokens_out":2644,"duration_ms":19748,"temperature":1.0,"reasoning_tokens":2586,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:57:13.249723+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a graph class with bounded semi-ladder index on which Annotated Partial Domination, specifically the formula $\\delta_{k,d}$ used in the proof, cannot be solved in $f(d,k,\\ell)\\cdot n^{O(1)}$ time, or produce a distance formula $\\delta$ whose associated bipartite graph has bounded semi-ladder index but whose decision problem is not fixed-parameter tractable; either would falsify Theorem 4 and with it Theorems 1 and 2.","supporting_citations":[{"cited_title":"u r Informatik, Schloss Dagstuhl - Leibniz-Zentrum f \\","cited_arxiv_id":null,"evidence_quote":"Supplies the problem definitions, the earlier non-uniform $f(k,d)\\cdot n^{O(d)}$ algorithm, and the open question about parameter $k+d+c$ that this paper answers."},{"cited_title":"Minimum bisection is fixed-parameter tractable","cited_arxiv_id":null,"evidence_quote":"Provides the unbreakable tree-decomposition theorem that reduces general graphs to bags with small adhesions and unbreakable interiors."},{"cited_title":"The complexity of optimal elimination trees","cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of treedepth, which yields para-NP-hardness for parameter $d$ and the kernel lower bound for $d=0$."}],"review_version":1}