{"id":"c4ccf742-87d9-4519-b99f-d98260d2147e","arxiv_id":"2411.13141","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Roman Domination and Independent Roman Domination are solvable in 4^k n^{O(1)} time when parameterized by distance to cluster, with SETH and kernel lower bounds showing this is nearly optimal.","lead":"This paper gives fixed-parameter tractable algorithms for Roman Domination and Independent Roman Domination on graphs that become a cluster of cliques after deleting k vertices. It also proves conditional lower bounds showing that the running time cannot be improved to 2^{εk} for any ε<1 unless the Strong Exponential Time Hypothesis fails.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"ISCP DP in Theorem 17 fails to enforce the 'exactly one' condition for flag-2 blocks, producing false positives for the IRD-CVD FPT algorithm.","rationale":"The reader identified the DP recurrences for SCP/ISCP as the weakest assumption but did not pinpoint the exact-one violation. Our analysis shows a concrete counterexample where the ISCP DP accepts an invalid solution, directly contradicting the central claim for Independent Roman Domination (Theorem 19). The SCP DP for Roman Domination appears sound because flag 2 requires only 'at least one', but the ISCP variant imposes 'exactly one', and the state compression (flag b only) cannot distinguish 'no set selected from this flag-2 block' from 'one set already selected'. This is not a minor typo or missing base case; it is a fundamental flaw in the recurrence. Since the paper's main contribution includes the FPT algorithm for IRD-CVD, the paper should be rejected unless the DP is redesigned (e.g., with a separate state for 'already satisfied exactly one') and re-proved. The lower-bound and kernel results for RD-CVD may still be correct, but the paper as a whole is not acceptable in its current form.","tokens_in":13491,"tokens_out":44008,"duration_ms":381602,"concrete_test":"Implement the ISCP DP from Theorem 17 and apply it to the instance U={a,b}, F={S1={a}, S2={b}}, one block β1 with flag 2, ℓ=4. Brute-force enumeration of all F'⊆F shows ∞ (no subset with |F'∩β1|=1 covers U), while the DP returns 4. Run this and also compare DP against brute force on all random small ISCP instances (|U|≤5, blocks≤3, flags in {1,2}) to confirm the discrepancy is systematic.","verdict_should_be":"REJECT","load_bearing_attack":"The DP for Independent-Set-CoverWithPartition (Theorem 17) claims to enforce \"exactly one set from each flag-2 block\" (condition (a)), but its recurrence does not track whether a set from the current flag-2 block has already been selected. In Case 1 (set is not the first of its block), the 'pick' option is 2 + OPT[W\\S_{j+1}, j, 0]. The subproblem with flag 0 may already contain a set from the same block (because flag 0 imposes no restriction and does not record history). Adding S_{j+1} then yields two sets from a flag-2 block, violating the exact-one condition. Concretely, take U={a,b}, F={S1={a}, S2={b}}, one block with flag 2. No valid solution exists: an exact-one selection covers only one of a or b. The DP returns OPT[{a,b},2,2] = 4, the cost of choosing both S1 and S2 (via the pick option at j=2 that calls OPT[{a},1,0]=2). This is a false positive. This instance arises naturally from the IRD-CVD reduction (a two-vertex clique whose two vertices attach to different vertices of the CVD set S with S1=S2=∅). Therefore Theorem 17 is incorrect, and the 4^k algorithm for Independent Roman Domination (Theorem 19) is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Roman Domination (RD) and Independent Roman Domination (IRD) parameterized by the distance k to a cluster graph. It claims FPT algorithms running in 4^k n^{O(1)} for both problems, a SETH-based lower bound excluding 2^{εk} n^{O(1)} for RD, and a polynomial-kernel lower bound for RD. The algorithms guess the restriction of the solution to the deletion set S and reduce the remaining problem to set-cover variants with block constraints, solved by dynamic programming over subsets of S. The lower bounds are obtained by a reduction from d-HITTING SET.","tokens_in":13758,"tokens_out":38973,"duration_ms":387897,"significance":"If the FPT algorithms were correct, the paper would be a useful contribution to structural parameterizations of Roman Domination, complementing the lower bounds. The lower-bound part (Theorems 20-25) is sound and clearly presented, and the IRD side of the positive results appears salvageable. The SCP/ISCP DP framework is promising, but the RD-CVD algorithm as written is not correct: the base case of the SCP DP rejects valid solutions, and Theorem 14's summation skips empty guesses. These are load-bearing issues that require a substantive revision of the positive section before the main FPT claims can be accepted.","major_comments":[{"comment":"The DP has a false negative for the first block. Take U={a,b,c,d}, one block β1={S1,S2} with S1={a,b}, S2={c,d}, and flag f1=2. The solution F'={S1,S2} covers U, satisfies F'∩β1≠∅, and has cost 4, so the SCP optimum is at most 4. However, the base case for W≠∅ requires W⊆S_i for some i≤j, hence OPT[{a,b,c,d},2,2]=∞; the recurrence is only invoked for S_{j+1} not in β1, so this value is never corrected. This SCP instance is realized as an RD-DisjointCluster instance produced by the S2=S1=∅ guess for the graph with S={a,b,c,d} and one cluster clique {x,y,z} where x is adjacent only to a,b and y only to c,d; that graph has γ_R=4. Thus the proof of Theorem 14 relies on a subroutine that is false for a valid guess. The base case must be replaced by a correct DP over the first block (for example, by using a dummy previous block and the same recurrence).","section":"Section 3.1, Theorem 12 (base cases)"},{"comment":"The double summation runs i1=1..k and i2=1..k-i1, so guesses with S1=∅ or S2=∅ are never considered. The optimal RD function in the counterexample above has S1=S2=∅, and such cases are natural for this problem. The index ranges should start at 0; as written, the 4^k time bound does not cover all relevant subproblems, even if the SCP DP were corrected.","section":"Section 3.1, Theorem 14 (summation range)"},{"comment":"I checked the stress-test counterexample and it does not produce a false positive for the IRD-CVD instances: for U={a,b} and a single flag-2 block {S1={a},S2={b}}, the base case (all sets are in β1) returns ∞ for W={a,b}, not 4. The DP does enforce the exact-one condition for the instances delivered by the IRD-CVD reduction. However, Theorem 17 as stated is false for general ISCP because flag-1 blocks may contain multiple sets, and the recurrence for a non-first set of a block jumps to the previous block after a pick, preventing more than one selection from a flag-1 block; the ISCP problem imposes no such limit. Since the reduction creates only singleton flag-1 blocks, the IRD-CVD result is not affected, but the theorem statement overclaims and should be restricted accordingly.","section":"Section 3.2, Theorem 17 (statement generality)"}],"minor_comments":[{"comment":"In the construction of the graph G, the edge set E2 is defined twice; the second definition should be E3.","section":"Section 4, Theorem 21"},{"comment":"The heading contains a typo: 'Defenitions' should be 'Definitions'.","section":"Section 2.3"},{"comment":"The phrase 'can not be solved' should be 'cannot be solved', and 'adaption' should be 'adaptation'.","section":"Abstract and Section 2.4"},{"comment":"Observation 10 proves only that some optimal solution has at least one selected vertex in each T2 clique; the DP's handling of multiple selections from a block is not explained, which contributed to the base-case error in Theorem 12. A short explanatory lemma about the structure of optimal solutions would improve the presentation.","section":"Section 3.1, Observation 10"}],"recommendation":"major_revision","confidential_remarks":"The reader's specific complaint about Theorem 17 is not supported by the manuscript text; the more serious issue is the first-block base case in Theorem 12, which also undermines Theorem 14. The lower-bound section appears solid. I would ask the authors to fix the base case and the summation range, and to restrict the ISCP statement, before the positive results can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nTwo things you should know about this paper. First, the RD-CVD side looks genuinely good: the 4^k FPT algorithm, the SETH lower bound, and the no-polynomial-kernel result are all plausible and the reduction from d-HITTING SET is clean. The set-cover-with-partition framework and the T0/T1/T2 clique classification are a sensible adaptation from Goyal et al., and the non-independent version (Theorem 12/14) holds up on inspection apart from a minor summation typo that omits empty S1/S2 guesses.\n\nSecond, the Independent Roman Domination half has a real bug. The ISCP DP in Theorem 17 claims to enforce \"exactly one set from each flag-2 block,\" but the recurrence does not track whether a set from the current block was already selected. When S_{j+1} is not the first set of its block, the pick option calls OPT[W\\S_{j+1}, j, 0], resetting the block's flag to 0. Nothing prevents that subproblem from containing an earlier set from the same block, so adding S_{j+1} gives two sets from a flag-2 block, violating condition (a). The concrete counterexample works: U={a,b}, F={S1={a}, S2={b}}, one flag-2 block. No valid solution exists, but the DP returns 4 by picking both sets. This is not a contrived edge case; it arises naturally after the IRD-CVD reduction. The recurrence also uses b=0 in subproblems even though b was defined only over {1,2}. I believe this is a genuine gap, not a typo.\n\nSo the paper deserves a serious referee, but not acceptance in its current form. The RD-CVD results and the lower bounds are worth publishing; the IRD-CVD claim is unproven. A fix would require an extra state bit or a different DP formulation, and the authors should also clarify the summation and the duplicate E2 definition.\n\nMy recommendation: send to peer review, but expect major revision. The referees should focus on Theorem 17 and the ISCP recurrence.\n\nBest,\n[Your name]","headline":"The Roman Domination half is solid; the Independent variant's FPT DP has a genuine exact-one bug that sinks Theorem 19 as written.","tokens_in":14297,"tokens_out":4460,"would_cite":true,"duration_ms":41057,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","68Q27","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that Roman Domination and Independent Roman Domination, parameterized by the number k of vertices whose deletion leaves a cluster graph, are fixed-parameter tractable with running time 4^k n^{O(1)}, and that the 4^k base…","keywords":["Roman Domination","Independent Roman Domination","distance to cluster","cluster vertex deletion","fixed-parameter tractability","SETH","kernelization"],"falsifier":"Take a small graph with cluster deletion set S of size 2 or 3 and three cliques in G−S whose flags force a flag-1 block to be left empty while a later flag-2 block is filled; run the DP from Theorem 12 and compare its answer with a brute-force enumeration of all 3^n labelings. Any instance where the two disagree on the minimum Roman domination weight falsifies the recurrence.","tokens_in":13314,"feed_emoji":"🏛️","tokens_out":7453,"duration_ms":65979,"temperature":0.7,"pith_summary":"Roman domination asks for a labeling of vertices by 0, 1, 2 with minimum total weight in which every 0-labeled vertex has a 2-labeled neighbor; independent Roman domination adds the requirement that the non-zero labels form an independent set. This paper studies both problems on graphs that are k vertex deletions away from a cluster graph, i.e., graphs with a set S of k vertices whose removal leaves a disjoint union of cliques. It proves that both problems are fixed-parameter tractable with parameter k, solvable in 4^k $n^{{O(1)}}$ time. The same paper shows that the running-time base 4 cannot be lowered to $2^{{εk}}$ for Roman Domination unless SETH fails, and that the problem admits no polynomial kernel unless NP⊆coNP/poly.","feed_headline":"Roman domination solved in 4^k time on near-cluster graphs","feed_subtitle":"Both Roman domination variants run in 4^k n^O(1); SETH blocks the 2^{εk} shortcut.","key_machinery":"The central object is a partition-respecting set cover that the paper calls Set-CoverWithPartition (and its independent variant Independent-Set-CoverWithPartition). Candidate sets are the neighborhoods inside S of individual vertices of G−S; vertices of the same clique form one block, and each block carries a flag 1 or 2 recording whether that clique has one vertex, or two or more vertices, not already protected by S2. The DP state OPT[W,j,b] holds the minimum cost of covering W⊆S using the first j candidate sets while the flag of the current block is temporarily b; transitions charge 2 for picking a set, add 1 for every flag-1 block left untouched, and reset earlier blocks to their original flags. This flag bookkeeping is what allows the algorithm to remember, in only 3·$2^{{|S|}}$·m states, which cliques still demand a picked vertex.","core_discovery":"For a graph G with a cluster vertex deletion set S of size k, the paper establishes that Roman Domination (RD-CVD) and Independent Roman Domination (IRD-CVD) can be solved in 4^k $n^{{O(1)}}$ time. The algorithm guesses the two sets S1,S2 of vertices of S that receive labels 1 and 2 in an optimal solution, then exploits the structural fact that in any clique of G−S having two vertices unprotected by S2, some vertex of that clique can be assumed to carry label 2. This converts the residual problem into a partition-respecting set cover: each clique becomes a block of candidate subsets of S, flagged by whether it must contain at least one (or exactly one, in the independent case) chosen vertex, and the cost is 2 per chosen vertex plus 1 per flag-1 block left empty. A dynamic program indexed by subsets W⊆S and positions among the candidate sets solves each converted instance in $2^{{|S|}}$ $n^{{O(1)}}$ time, and summing over all guesses of S1,S2 yields 4^k $n^{{O(1)}}$. The lower-bound section constructs a split graph from a d-hitting-set instance so that a hitting set of size t corresponds exactly to a Roman dominating function of weight 2t, which transfers both the SETH lower bound and the no-polynomial-kernel result.","pith_inferences":["The flag-compression DP is likely to transfer to other 'choose vertices with block constraints' covering problems on cluster graphs, such as variants of domination that only require one protected vertex per clique.","The conditional lower bound does not rule out an O((4−δ)^k n^{O(1)}) algorithm; the next natural target is whether the state space can be reduced below 2^{|S|} per guess.","A similar SETH lower bound should hold for the independent variant, since the same split-graph gadget with an independent-set condition admits an analogous reduction, though the paper only proves the lower bound for Roman Domination.","Because the cluster part is solved by set cover over the k deletion vertices, the algorithm's practical bottleneck is the 2^k DP over subsets of S; structural parameters that shrink k, such as neighborhood diversity, may be the more useful way to attack real instances."],"forward_implications":["Roman Domination and Independent Roman Domination are both fixed-parameter tractable when the parameter is the distance to a cluster graph, with running time 4^k n^{O(1)}.","A cluster vertex deletion set of size k is the only global structure needed; the algorithms do not require bounded treewidth or any property beyond the deletion set itself.","Under SETH, the 4^k factor cannot be improved all the way to 2^{εk} for Roman Domination parameterized by distance to cluster, so the exponential base is not an accident.","Unless NP⊆coNP/poly, Roman Domination parameterized by distance to cluster has no polynomial kernel, so no polynomial-time preprocessing can compress the instance to size polynomial in k.","The same lower bounds hold for Roman Domination parameterized by vertex cover number, because the constructed graph is a split graph whose clique side U is a vertex cover."],"supporting_citations":[{"why":"Supplies the dominating-set-in-almost-cluster approach that this paper adapts to Roman domination.","marker":"[10]"},{"why":"Provides the 2^{|U|} set-cover algorithm whose DP pattern the partition set-cover recurrences extend.","marker":"[9]"},{"why":"Gives the 1.92^k n^{O(1)} cluster vertex deletion algorithm used when a deletion set is not supplied.","marker":"[3]"},{"why":"States the SETH-equivalent d-hitting-set lower bound that the reduction targets.","marker":"[4]"},{"why":"Gives the no-polynomial-kernel result for d-hitting set parameterized by universe size that is transferred by polynomial-parameter transformation.","marker":"[6]"},{"why":"States the theorem that a polynomial-parameter transformation transfers kernel lower bounds, used in the kernel argument.","marker":"[2]"},{"why":"Introduces the SETH conjecture that the conditional lower bound relies on.","marker":"[11]"}],"fun_headline_variants":["Roman domination in 4^k time on cluster-deletion graphs","Roman domination FPT: 4^k n^O(1) for near-cluster graphs","4^k algorithm for Roman domination on cluster-deletion graphs","Roman domination: 4^k time, SETH lower bound, no poly kernel","Roman domination: 4^k on near-cluster, SETH says 2^εk impossible"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The correctness claim for both algorithms rests on the DP recurrences' assumption that resetting earlier blocks to their original flags while tracking only the current block's modified flag correctly handles every pattern of empty and non-empty cliques; if that state compression misses any combination, the computed optimum could be wrong.","fun_headline_variants_meta":{"raw":{"variants":["Roman domination in 4^k time on cluster-deletion graphs","Roman domination FPT: 4^k n^O(1) for near-cluster graphs","4^k algorithm for Roman domination on cluster-deletion graphs","Roman domination: 4^k time, SETH lower bound, no poly kernel","Roman domination: 4^k on near-cluster, SETH says 2^εk impossible"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000987,"raw_usage":{"total_tokens":4377,"prompt_tokens":1327,"completion_tokens":3050,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":943,"completion_tokens_details":{"reasoning_tokens":2946}},"tokens_in":943,"tokens_out":3050,"duration_ms":24227,"temperature":1.0,"reasoning_tokens":2946,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:52:49.817358+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small graph with cluster deletion set S of size 2 or 3 and three cliques in G−S whose flags force a flag-1 block to be left empty while a later flag-2 block is filled; run the DP from Theorem 12 and compare its answer with a brute-force enumeration of all 3^n labelings. Any instance where the two disagree on the minimum Roman domination weight falsifies the recurrence.","supporting_citations":[{"cited_title":"Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs","cited_arxiv_id":"2405.10556","evidence_quote":"Supplies the dominating-set-in-almost-cluster approach that this paper adapts to Roman domination."},{"cited_title":"Fomin and Dieter Kratsch","cited_arxiv_id":null,"evidence_quote":"Provides the 2^{|U|} set-cover algorithm whose DP pattern the partition set-cover recurrences extend."},{"cited_title":"A fast branching algorithm for cluster vertex deletion","cited_arxiv_id":null,"evidence_quote":"Gives the 1.92^k n^{O(1)} cluster vertex deletion algorithm used when a deletion set is not supplied."},{"cited_title":"On problems as hard as cnf-sat","cited_arxiv_id":null,"evidence_quote":"States the SETH-equivalent d-hitting-set lower bound that the reduction targets."},{"cited_title":"Kernelization lower bounds through colors and ids","cited_arxiv_id":null,"evidence_quote":"Gives the no-polynomial-kernel result for d-hitting set parameterized by universe size that is transferred by polynomial-parameter transformation."},{"cited_title":"Bodlaender, St \\' e phan Thomass \\' e , and Anders Yeo","cited_arxiv_id":null,"evidence_quote":"States the theorem that a polynomial-parameter transformation transfers kernel lower bounds, used in the kernel argument."}],"review_version":1}