{"id":"c1885423-5fbe-4bdc-be86-f8d90c56461f","arxiv_id":"2412.15671","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors prove that (d,r)-domination is fixed-parameter tractable by modular-width plus demand, admits polynomial compressions by modular-width and iterated type partition number plus demand, and admits a polynomial kernel by neighborhood diversity plus demand.","lead":"This paper gives faster exact algorithms for a generalized domination problem in which each vertex must be covered several times within a fixed distance. The methods exploit modular structure in graphs and yield polynomial-size kernels for several structural parameters.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4's itp+demand compression ILP omits the extra-vertex variables used in Section 3; on K_{3,3} with d=1 it rejects a valid size-2 dominating set, so Lemma 5 and Theorem 6 are unsupported.","rationale":"The reader's weakest assumption was Lemma 1, but the most decisive problem is elsewhere. Lemma 1(ii) is plausibly true: modules of a connected graph are preserved under graph powers, and the applications to K∪I and cographs survive the power step. Lemma 1(i) as stated is too broad -- for an arbitrary class containing all cliques, powers of a module need not stay in the class -- but that generality is not needed for the paper's concrete parameters. The real blocker is Section 4. The ILP there tries to certify (d,1)-domination using only minimum t-dominating sets per itp module, but an optimal global solution may select extra vertices in a module purely to dominate adjacent modules. The FPT algorithm in Section 3 models these extras with x_i; Section 4 has no analogue. K_{3,3} with d=1 is a minimal witness: a size-2 dominating set exists, yet the ILP cannot represent it because each independent module's minimum 1-dominating set has size 3. This makes Lemma 5's equivalence claim false and removes the proof of Theorem 6. The FPT result (Theorem 2) may well be correct, but the paper as submitted contains a demonstrably incorrect construction for one of its advertised compression results, so the current verdict should move from CONDITIONAL to REJECT, or at least to major revision with Section 4 replaced.","tokens_in":14265,"tokens_out":35928,"duration_ms":351223,"concrete_test":"Implement the Section 4 ILP (constraints (1)-(4)) with module costs computed by the paper's own recurrence on G=K_{3,3}, taking the two independent 3-vertex sides as the itp modules, d=1, and k=2. The ILP should return infeasible because its only choices are 0 or 3 vertices per module. Independently verify that {a1,b1}, one vertex in each side, is a (1,1)-dominating set of K_{3,3}. If the ILP instead returns feasible, my reading is wrong; otherwise Lemma 5's reduction is invalid.","verdict_should_be":"REJECT","load_bearing_attack":"The paper's Section 4 compression result depends on an ILP whose only per-module choice is a minimum (t,1)-dominating set of size c_Mi(t), with no provision for selecting additional vertices that serve only to dominate neighboring modules. The Section 3 algorithm explicitly handles exactly this situation with variables x_i; Section 4 drops them. This is not a cosmetic omission. Let G=K_{3,3}, decomposed into its two independent 3-vertex modules, so itp(G)=2. For d=1, the set consisting of one vertex from each side is a (1,1)-dominating set of size 2. But each module has c_M(1)=3, since an edgeless module needs all its vertices selected to dominate itself. The Section 4 ILP therefore permits only 0 or 3 selected vertices per module and reports the instance with k=2 infeasible. The claimed equivalence in Lemma 5 is false, and Theorem 6, which transfers this construction to (d,r)-domination, is unsupported. This failure is internal to the (d,1) case and does not depend on Lemma 1 or on graph powers.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the (d,r)-Domination problem, in which every vertex outside the selected set must have at least d selected vertices within distance r. The main results are: (1) an FPT algorithm parameterized by modular-width plus demand, based on a bottom-up dynamic program over the modular decomposition tree with a small ILP at each node; (2) a polynomial compression for (1,r)-Domination parameterized by modular-width on connected graphs; (3) a polynomial compression for (d,r)-Domination parameterized by iterated type partition number plus demand; and (4) a polynomial kernelization for (d,r)-Domination parameterized by neighborhood diversity plus demand. A central lemma asserts that modular-width and G-modular cardinality do not increase when passing to the r-th power G^r, which the paper uses to reduce all radius-r results to the radius-1 case.","tokens_in":14599,"tokens_out":23179,"duration_ms":222952,"significance":"If correct, the FPT algorithm in Section 3 would be a concrete and useful contribution: it gives an explicit, checkable ILP-based algorithm for a parameter that can be small on dense graphs, and the compression and kernelization results would extend known kernelization results for Dominating Set to richer structural parameters. The Section 3 algorithm is specified in enough detail to be credible and appears sound. However, the paper currently contains a false ILP in Section 4, and several load-bearing statements (Theorem 3, Lemma 5, Lemma 6, and Lemma 1) are either unproved or, in the case of Lemma 1(i), false in the stated generality. The significance is therefore contingent on substantial revision.","major_comments":[{"comment":"The ILP in Section 4 has no variables for selecting a non-minimum number of vertices from a module when those vertices are needed only to dominate neighboring modules. It can only choose a minimum (t,1)-dominating set of size c_Mi(t) for one value of t, or no set at all. In the Section 3 algorithm this gap is filled by the extra-vertex variables x_i; Section 4 drops them. This is not a cosmetic omission. For G=K_{3,3} with d=1, the two sides are independent-set modules of size 3, so c_Mi(1)=3. The set consisting of one vertex from each side is a (1,1)-dominating set of size 2, but the ILP only permits 0 or 3 selected vertices per module and therefore declares the size-2 solution infeasible. Hence the claimed equivalence in Lemma 5 is false and Theorem 6 is unsupported. The ILP must be extended with extra-vertex variables as in Section 3 before applying the Frank-Tardos compression.","section":"Section 4, ILP (1)-(4), Lemma 5, Theorem 6"},{"comment":"Theorem 3, which states that Dominating Set admits a polynomial compression parameterized by modular-width on connected graphs, is the entire basis for the claimed PC for (1,r)-Domination in Theorem 4, but it is stated without proof. The problem COLORED DOMINATION is defined, but no reduction from Dominating Set to it is described, and no argument shows how the modular structure is used to obtain a polynomial bound. Since the known non-existence results in [40,45] are for disconnected graphs, the connected case is a genuine new claim rather than a routine corollary. A complete proof must be supplied before this result can be accepted.","section":"Section 3.1, Theorem 3"},{"comment":"The kernelization in Theorem 7 depends on Lemma 6, which asserts that there is an optimal (d,r)-dominating set using at most 2d-1 vertices from each clique or independent-set module. The lemma is stated without proof. The subsequent pruning argument only shows that, if such a solution exists, its cardinalities can be preserved after pruning; it does not prove the bound. In particular, for r>1 one must argue that selected vertices in a module contribute uniformly to vertices at distance at most r, including paths that pass through the module. Please add a proof or a precise exchange argument.","section":"Section 5, Lemma 6"},{"comment":"Lemma 1 is asserted without proof and is used to pass from (d,1)-domination to (d,r)-domination in Theorem 1, Corollary 1, and Theorems 2, 4, 6, and 7. Part (i) is false in the stated generality. Let G be the graph class consisting of all cliques together with C6. Then K is contained in G and G-mc(C6)=1 because C6 is in G. However, C6^2 is K_{3,3}, whose proper modules are contained in one side of the bipartition; since the sides are independent sets and not cliques or C6, any G-modular partition of C6^2 needs at least three parts. Thus G-mc(C6^2)>1. The authors should either restrict the statement to the classes actually used (K union I and the cograph class) and prove the monotonicity for those classes, or formulate a correct general condition. Part (ii) also needs a proof.","section":"Section 2.1, Lemma 1"}],"minor_comments":[{"comment":"The row for mw is misaligned; it is difficult to tell which entries correspond to (1,1), (1,r), (d,1), and (d,r).","section":"Table 1"},{"comment":"There is a typo in the sentence introducing the neighborhood: 'by2 N(v)' should be 'by N(v)'.","section":"Section 2"},{"comment":"Reference [14] is listed as arXiv:0710.3901 with year 2024; the publication year should be corrected to the original year of the paper.","section":"References"},{"comment":"The proof of Lemma 2 would benefit from a sentence explaining why the ILP computes c_M(t) and not merely a lower bound; the current text jumps from the ILP statement to the runtime bound.","section":"Section 3, Lemma 2"}],"recommendation":"major_revision","confidential_remarks":"The main reason for major revision is the false ILP in Section 4; this is a load-bearing error, not a presentation issue. The paper also states Theorem 3, Lemma 5, and Lemma 6 without proofs, which is not acceptable for a journal submission. The FPT part in Section 3 looks sound and credible, and the Section 4 error appears repairable by adding the missing extra-vertex variables before applying the Frank-Tardos compression. I therefore do not recommend rejection, but the revision must fix the false equivalence and supply the missing proofs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Three things worth knowing. First, the FPT algorithm in Theorem 2 is real: the modular decomposition DP with the small ILP is correctly specified and gives the claimed runtime for (d,r)-domination parameterized by mw+d. The extra-vertex variables in the Section 3 ILP are exactly what is needed, and the runtime analysis is careful. Second, the itp-based polynomial compression in Section 4 is broken as stated. The ILP only lets each module contribute a minimum (t,1)-dominating set, with no extra vertices. On K_{3,3} with d=1, the valid size-2 solution that picks one vertex from each side cannot be represented; each module is forced to contribute either 0 or 3 vertices, so the claimed equivalence in Lemma 5 is false. This is an internal failure of the (d,1) case and does not depend on graph powers. Third, Lemma 1 (mw and G-mc do not increase under graph powers) is plausible but unproved, and it is load-bearing for every radius-r statement, including Theorem 2. A short proof or a citation for it is needed.\n\nWhat is genuinely new: the mw+d FPT result, the power-graph bridge for modular parameters, and the claimed connected-graph PC by mw (Theorems 3–4). The latter is interesting but also stated without proof, so I would treat it as a conjecture until the construction appears.\n\nSofter spots, in proportion: Lemma 6 (the 2d−1 bound per module) is also unproved; the Section 5 PK might be fixable but needs a proof. The Section 4 flaw, however, is not a minor gap — it is a counterexample that invalidates Theorem 6 as written. The rest of the paper's citation pattern is fine; the self-citations to [13] are relevant and not padding.\n\nWho should read this: researchers working on parameterized domination with modular parameters. The FPT part will be a useful citation. The compression claims should not be cited until they are repaired or removed.\n\nRecommendation: send this to a serious referee. The FPT algorithm deserves publication, and the flawed PC section is exactly what peer review should catch. If I were the editor, I would ask for a major revision that fixes or deletes the itp compression section before anything else.","headline":"Solid FPT algorithm for (d,r)-domination by modular width plus demand, but the polynomial compressions rest on unproved or false lemmas; the itp-based compression is broken as written.","tokens_in":15088,"tokens_out":5560,"would_cite":true,"duration_ms":53808,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","68Q27","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves (d,r)-domination is fixed-parameter tractable in modular width plus demand, and gives polynomial compressions for two wider decomposition measures.","keywords":["(d,r)-domination","dominating set","parameterized complexity","modular decomposition","modular width","neighborhood diversity","iterated type partition","polynomial kernel"],"falsifier":"Exhaustively enumerate all connected graphs on at most seven vertices, computing $mw(G)$ and $mw(G^2)$ by brute force; the first example with $mw(G^2)>mw(G)$ refutes Lemma 1 and, with it, the power-graph reductions for $r\\ge 2$. A structural probe is to take a module $M$ of $G$ and check whether two vertices of $M$ acquire different external neighborhoods in $G^r$; if they do, $M$ is no longer a module of the power graph.","tokens_in":14059,"feed_emoji":"🧩","tokens_out":12892,"duration_ms":79398,"temperature":0.7,"pith_summary":"This paper asks how hard it is to find a small set of vertices that covers every other vertex at least $d$ times within distance $r$, the $(d,r)$-domination problem. Its main answer is that modular structure plus demand makes the problem tractable: the problem is fixed-parameter tractable parameterized by modular width plus $d$, and it admits polynomial compressions and a polynomial kernel for the wider iterated-type-partition and neighborhood-diversity parameters. Since a $(d,r)$-dominating set of $G$ is exactly a $(d,1)$-dominating set of the $r$-th power $G^r$, the results are channeled through one reduction, assuming that taking powers does not enlarge the decomposition parameters. The stated motivation is immunization against misinformation: a small $(d,r)$-dominating set identifies people who, within a trust radius $r$ and after $d$ exposures, can debunk a false narrative.","feed_headline":"New FPT algorithm solves (d,r)-domination via modular width","feed_subtitle":"Distance and multiplicity domination both reduce to radius 1 when modular-width stays small","key_machinery":"The load-bearing mechanism is a bottom-up cost computation on the modular parse tree. For each module $M$, the algorithm keeps $c_M(t)$ for $t=0,1,\\dots,d$, the minimum size of a $(t,1)$-dominating set of $G[M]$. A module whose children are $G_1,\\dots,G_\\ell$ is solved by an integer program with at most $\\ell$ variables, picking how much each child module contributes and how many extra vertices inside it are selected; the fixed-variable integer programming bound gives the $O(\\ell^{2.5\\ell+o(\\ell)}\\log|V(G)|)$ factor. The compression results reuse the same costs in an integer program over the outline graph and shrink its coefficients with simultaneous Diophantine approximation. The bridge to radius $r$ is the power-graph lemma: since $(d,r)$-dominating sets equal $(d,1)$-dominating sets of $G^r$, the same machinery applies to $G^r$.","core_discovery":"The central claim is that $(d,r)$-domination becomes tractable once the graph's modular structure and the demand are small. A $(d,r)$-dominating set of $G$ is exactly a $(d,1)$-dominating set of the $r$-th power $G^r$, and the paper's Lemma 1 states that modular-width and the restricted modular cardinality do not grow when passing to $G^r$. Under that premise, the paper proves $(d,r)$-DOMINATION is fixed-parameter tractable parameterized by $mw(G)+d$, with running time $O(mw^{2.5mw+o(mw)} d(d+1)^{mw}|V(G)| \\log |V(G)|)$. It also proves a polynomial compression for $(1,r)$-domination parameterized by modular width, a polynomial compression parameterized by $itp(G)+d$, and a polynomial kernel parameterized by $nd(G)+d$, the last by pruning every module to $2d$ vertices.","pith_inferences":["The most direct extension is to test Lemma 1 computationally on small graphs; since it is stated without proof, a single counterexample would split the paper's results into a radius-1 half and a radius-unknown half.","The module-pruning rule behind the neighborhood-diversity kernel is a general recipe: any domination variant where only the count of chosen vertices inside a module matters can likely be kernelized by truncating each module to $O(d)$ vertices.","The cost-recursion with an integer program over child modules looks adaptable to weighted vertices or non-uniform per-vertex demands, at the price of a larger cost array $c_M(t)$."],"forward_implications":["If the results are correct, $(d,r)$-domination is fixed-parameter tractable in $mw(G)+d$, so graphs with small modular structure and small demand are solvable even when the optimum is large.","Because the power-graph step is assumed to be free, the radius $r$ adds no new parameter: the same algorithm covers every distance.","For $d=1$, the problem has a polynomial compression parameterized by modular width on connected graphs, a boundary that is known to fail for the unrestricted input class.","The combined parameter $itp(G)+d$ yields a polynomial compression, while $nd(G)+d$ yields a polynomial kernel whose graph has at most $2d\\cdot nd(G)$ vertices."],"supporting_citations":[{"why":"Defines the (d,r)-domination problem and establishes its NP-completeness; the paper's starting point.","marker":"[3]"},{"why":"Gives the linear-time modular decomposition that yields the parse tree the algorithms traverse.","marker":"[14]"},{"why":"States the fixed-variable integer programming running time that determines the FPT exponent in Algorithm 1.","marker":"[43]"},{"why":"Gives the simultaneous Diophantine approximation result used to compress the integer program in the itp compression.","marker":"[29]"},{"why":"Provides the corollary on compressing weighted linear inequalities over binary vectors that the itp compression applies.","marker":"[21]"},{"why":"Provides the FPT algorithm for d-domination under neighborhood diversity and the restricted modular-cardinality framework that the paper lifts to radius r.","marker":"[39]"},{"why":"Gives the FPT dominating-set algorithm parameterized by modular width used for the d=1 case.","marker":"[48]"},{"why":"Introduces the iterated type partition parameter and its dominating-set algorithms, which the corresponding compression extends.","marker":"[13]"},{"why":"Supplies the FPT dominating-set algorithm parameterized by neighborhood diversity that Theorem 1 uses for the d=1 power graph.","marker":"[46]"}],"fun_headline_variants":["FPT for (d,r)-domination when modular width is small","Modular decomposition yields kernels for (d,r)-domination","Small modules make (d,r)-domination tractable","Fixed-parameter tractability of (d,r)-domination","Modular-width FPT for distance and multiple domination"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 1, stated without proof in Section 2.1: for every connected graph $G$, $mw(G^r)\\le mw(G)$ and the restricted modular cardinality of $G^r$ is at most that of $G$. Every radius-$r$ result in the paper is obtained by passing to $G^r$, so if this monotonicity ever fails, the entire generalization from $r=1$ to arbitrary $r$ collapses.","fun_headline_variants_meta":{"raw":{"variants":["FPT for (d,r)-domination when modular width is small","Modular decomposition yields kernels for (d,r)-domination","Small modules make (d,r)-domination tractable","Fixed-parameter tractability of (d,r)-domination","Modular-width FPT for distance and multiple domination"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000681,"raw_usage":{"total_tokens":3051,"prompt_tokens":860,"completion_tokens":2191,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":476,"completion_tokens_details":{"reasoning_tokens":2106}},"tokens_in":476,"tokens_out":2191,"duration_ms":14569,"temperature":1.0,"reasoning_tokens":2106,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:13:10.271917+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhaustively enumerate all connected graphs on at most seven vertices, computing $mw(G)$ and $mw(G^2)$ by brute force; the first example with $mw(G^2)>mw(G)$ refutes Lemma 1 and, with it, the power-graph reductions for $r\\ge 2$. A structural probe is to take a module $M$ of $G$ and check whether two vertices of $M$ acquire different external neighborhoods in $G^r$; if they do, $M$ is no longer a module of the power graph.","supporting_citations":[{"cited_title":"Bean, M.A","cited_arxiv_id":null,"evidence_quote":"Defines the (d,r)-domination problem and establishes its NP-completeness; the paper's starting point."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the fixed-variable integer programming running time that determines the FPT exponent in Algorithm 1."},{"cited_title":"Frank, É","cited_arxiv_id":null,"evidence_quote":"Gives the simultaneous Diophantine approximation result used to compress the integer program in the itp compression."},{"cited_title":"Etscheid, S","cited_arxiv_id":null,"evidence_quote":"Provides the corollary on compressing weighted linear inequalities over binary vectors that the itp compression applies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the FPT dominating-set algorithm parameterized by modular width used for the d=1 case."},{"cited_title":"Koutecký","cited_arxiv_id":null,"evidence_quote":"Supplies the FPT dominating-set algorithm parameterized by neighborhood diversity that Theorem 1 uses for the d=1 power graph."}],"review_version":1}