{"id":"c5323065-7ea8-4476-8d44-501253f7a1b9","arxiv_id":"2412.15663","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves that Vector Domination is W[1]-hard when parameterized by neighborhood diversity, and gives fixed-parameter algorithms for Distance Vector Domination under modular-width and treewidth parameters.","lead":"This paper introduces Distance Vector Domination, a graph problem that generalizes both distance and multiple domination, and maps out when the problem is easy or hard based on structural parameters. It proves a strong hardness result for a broad graph parameter and gives fixed-parameter algorithms for several structured graph classes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's modular-width RD algorithm is wrong: Algorithm 1 treats the selected vertex as needing domination and rejects valid singleton solutions (e.g., K2), so a central FPT claim is false as stated.","rationale":"The reader's weakest_assumption focuses on Lemma 1, and that missing proof is indeed a serious gap: the W[1]-hardness of VD with respect to neighborhood diversity is the paper's headline and depends entirely on an unproved iff. However, the most decisive and easily checkable defect is in the RD modular-width algorithm. Algorithm 1's A_i check is inconsistent with Definition 1 because a vertex put into the solution does not need to be dominated. On K2 this causes the algorithm to miss the optimum; with the alternative convention for the undefined min over an empty set, it accepts an invalid solution on a three-vertex instance. This is a concrete falsification of Lemma 3 and Theorem 5, not a mere omission, so the paper cannot be accepted as is. The verdict remains reject; no adjustment to the reader's judgement is needed.","tokens_in":13588,"tokens_out":15984,"duration_ms":145565,"concrete_test":"Execute Algorithm 1 exactly as written on G=K2 with parse tree G1⊗G2 and d=(1,1). For each SH⊆{1,2}, in increasing size, record (R,S). The outputs are false for SH={1} and SH={2} and true only for SH={1,2}, yielding solution size 2 although {x} is a valid RD set of size 1. Also run the variant with min∅=0 on G1={a,b} independent, G2={y}, H=K2, d=(1,1,1), SH={1}; it returns true though b is undominated. Either execution falsifies Lemma 3 and Theorem 5.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The sharpest load-bearing failure is in the claimed fixed-parameter algorithm for RD on bounded modular-width (Theorem 5), not just in the unproved hardness lemma. Definition 1 exempts selected vertices from domination, but Algorithm 1 includes the would-be selected vertex in the set A_i of vertices of module i that must be dominated from inside the module. Concretely, take G=K2 with modules G1={x}, G2={y} and d_v=1 for both vertices. The unique optimal RD set has size 1, e.g. {x}. With the standard convention min∅=∞, for SH={1} the algorithm sets ℓ_1=∞ and A_1={x}; since N_{G1}(x)=∅, it returns false, and SH={2} is rejected similarly; only SH={1,2} is accepted, so the reported optimum is 2. If one instead sets min∅=0, the algorithm accepts SH={1} on the instance where G1 is an independent set {a,b}, G2={y}, H=K2, and d=(1,1,1), selecting a while b remains undominated. Thus Lemma 3 is false under either convention, and Theorem 5, together with the RD row of Table 1, is not merely unproved but contradicted by a two-vertex instance. The W[1]-hardness proof additionally rests on the unproved Lemma 1, but this concrete algorithm failure is the most load-bearing defect.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Distance Vector Domination (DVD), a parameterized domination problem in which each vertex v has a demand t_v and a radius d_v, and a set S is valid when every non-selected vertex v has at least t_v selected vertices within distance d_v. The manuscript claims that the special case Vector Domination (VD) is W[1]-hard with respect to neighborhood diversity even when all radii are 1 (Theorem 3 and Corollary 1), and that several variants are fixed-parameter tractable: RD with modular-width (Theorem 5), VD with modular-width plus solution size k (Theorem 6), DVD with modular-width plus k (Theorem 7), VD with treewidth plus maximum demand (Theorem 8), and RD with treewidth plus maximum radius (Theorem 9). The proofs are based on a reduction from Multicolored Clique and on modular decomposition and treewidth dynamic programming.","tokens_in":13933,"tokens_out":6439,"duration_ms":51023,"significance":"If all claims were correct, the paper would be a useful contribution: it unifies distance and multiple domination in a single framework, and it extends the known parameterized complexity map for dense structural parameters such as neighborhood diversity and modular-width. The problem statement and the overview table are clear. However, the paper currently ships no machine-checked proofs or reproducible code, and its significance depends entirely on lemmas that are either unproved or contradicted by explicit instances. In particular, one of the advertised FPT algorithms (Theorem 5) is demonstrably wrong on a two-vertex graph, and the main hardness reduction rests on an unproved equivalence. The positive contributions are therefore not established in the present form.","major_comments":[{"comment":"Lemma 1 asserts an iff between a multicolored clique in (G,c,q) and a VD solution of size k in the constructed graph G', but no proof of this equivalence is given. This lemma is the entire basis for Theorem 3 and Corollary 1, so the main negative result is unverified. In particular, the demands in Equations (2) and (3) and the budget k are never shown to enforce that a solution selects one vertex per color, one edge per color pair, and consistent incidences between the selected vertices and edges.","section":"Section 2, Lemma 1"},{"comment":"Lemma 2 states that for RD there exists an optimal solution selecting at most one vertex from each module V(G_i) of the modular decomposition. No proof is provided. Theorem 5 relies on this lemma to justify the exhaustive search over subsets S_H of [p], so the correctness of the modular-width FPT algorithm is not established even before considering the execution of Algorithm 1.","section":"Section 3.1, Lemma 2"},{"comment":"Algorithm 1 is incorrect for the problem defined in Definition 1. Take G = K2 with modules G1={x}, G2={y}, H=K2, and d_v=1 for every vertex. The set S={x} is a valid RD set of size 1, since y is covered by x and selected vertices need not be dominated. For S_H={1}, the algorithm computes ℓ_1 = min∅ = ∞ and A_1 = {x}; because N_{G1}(x)=∅, it returns false, and S_H={2} is rejected symmetrically. Only S_H={1,2} is accepted, so the reported optimum is 2. If one instead adopts the convention min∅=0, the algorithm accepts S_H={1} on the instance where G1 is an independent set {a,b}, G2={y}, and H=K2 with d=(1,1,1), selecting a while b remains undominated. Thus Lemma 3 is false under either convention for min∅, and Theorem 5, together with the RD row of Table 1, is contradicted by a two-vertex instance.","section":"Section 3.1, Algorithm 1 and Theorem 5"},{"comment":"The claimed FPT algorithm for RD parameterized by treewidth plus maximum radius d is not described. The text only says that the authors use 'a strategy similar to the one adopted in [8]' and then states the running time. No states, transition rules, correctness proof, or analysis of the dependency on d and tw are given. Since Table 1 advertises this as a contribution, the claim is currently unverified.","section":"Section 4, Theorem 9"}],"minor_comments":[{"comment":"The text says 'two vertices u, v have the same same type'; this should be 'the same type'.","section":"Section 2, Neighborhood diversity"},{"comment":"The definition of ℓ_i uses a minimum over an empty set when |S_H|=1; the intended convention (∞) should be stated explicitly.","section":"Algorithm 1"},{"comment":"The phrase 'approximated in polynomial time by a factor log n + 2' would be clearer as 'within a factor of log n + 2'.","section":"Introduction, Theorem 2"},{"comment":"Reference [20] is dated 2024 for an arXiv preprint from 2007; please verify the year and version cited.","section":"References"}],"recommendation":"reject","confidential_remarks":"This is a reject rather than a major revision because the manuscript contains multiple independent load-bearing gaps: the main hardness lemma is unproved, Lemma 2 is unproved, Theorem 9 is only referenced, and Theorem 5 is contradicted by a concrete two-vertex instance. Substantial new technical work would be required to restore even the main positive and negative claims, so the current version cannot serve as a basis for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe key fact you should know: the RD algorithm on modular-width (Theorem 5) is wrong. On K2 with modules {x} and {y} and d=(1,1), the unique optimal RD set has size 1 (e.g., {x}), but Algorithm 1 with the usual convention min∅=∞ rejects the single-module subsets because it includes the would-be selected vertex in the set A_i of vertices that must be dominated from inside the module. With min∅=0 it accepts an invalid solution on a star, selecting a leaf while the other leaf remains undominated. Lemma 3 is false and Theorem 5, together with the RD row of Table 1, does not survive.\n\nThe paper does have genuinely new material. The DVD problem is a reasonable unification of distance and multiple domination, and the claimed W[1]-hardness of Vector Domination with respect to neighborhood diversity would answer an open question if the proof were complete. The treewidth-plus-tau DP for VD (Theorem 8) looks plausible and improves the earlier branchwidth-based result. The hardness reduction is elaborate and may well be correct.\n\nThe soft spots are substantial. Lemma 1, the equivalence at the heart of the W[1]-hardness reduction, is asserted without proof. Theorem 9 is a one-line reference to Borradaile--Le with no algorithmic details. And the modular-width RD algorithm is not merely missing a proof; it is contradicted by a two-vertex example. That last defect is load-bearing. As written, the paper does not support its central claims.\n\nWho should read this? Parameterized complexity researchers working on domination variants with dense structural parameters. If the authors fix the RD algorithm (or restrict it to cases where the flaw disappears, e.g., all d_v >= 2), supply the missing proof of Lemma 1, and give full details for Theorem 9, the paper could become solid. Right now it needs major revision.\n\nRecommendation: reject in current form, but invite resubmission after the authors repair Theorem 5 and fill the proof gaps. I would still send it to a serious referee, because the hardness result and the treewidth DP are potentially valuable and deserve expert scrutiny.","headline":"The modular-width RD algorithm (Theorem 5) is contradicted by a two-vertex instance, and the hardness proof relies on an unproved lemma; the paper needs major repair, but the DVD problem and the treewidth DP for VD are worth a serious look.","tokens_in":14416,"tokens_out":7388,"would_cite":false,"duration_ms":60052,"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":"Distance Vector Domination, a graph problem modeling immunization against fake narratives, is W[1]-hard with respect to neighborhood diversity even when all radii are 1, while several structural variants admit fixed-parameter algorithms.","keywords":["Distance Vector Domination","Vector Domination","R-domination","parameterized complexity","neighborhood diversity","modular-width","treewidth","W[1]-hardness"],"falsifier":"For a small $q$, build the gadget graph $G'$ described in the proof for a multicolored clique instance whose only $q$-cliques are known, solve the VD decision problem exactly, and compare the minimum solution size against the claimed budget; a mismatch would refute Lemma 1 and with it the W[1]-hardness claim.","tokens_in":13397,"feed_emoji":"🛡️","tokens_out":7100,"duration_ms":58125,"temperature":0.7,"pith_summary":"Distance Vector Domination (DVD) is a graph problem that asks for a small set of vertices such that every other vertex receives enough selected vertices within its personal radius, with a per-vertex demand. The paper's central negative result is that the special case with all radii equal to one, Vector Domination, is W[1]-hard when parameterized by neighborhood diversity, meaning that this structural measure does not make the problem fixed-parameter tractable. On the positive side, the paper gives fixed-parameter algorithms for radius-only domination parameterized by modular-width, for vector and distance-vector domination parameterized by modular-width together with solution size, and for the two one-sided variants parameterized by treewidth together with the maximum demand or the maximum radius. A reader should care because the problem models choosing a small set of individuals to immunize against fake narratives, and the results map which structural features of a network make that choice efficiently computable.","feed_headline":"Vector domination stays hard on neighborhood-diverse graphs","feed_subtitle":"New proof: all-radius-1 case is W[1]-hard, yet modular-width and treewidth variants run in FPT time.","key_machinery":"The reduction is carried by three kinds of gadgets: bag (an independent set whose vertices share all neighbors) and clique building blocks arranged into selection gadgets (one per color), multiple gadgets (one per color pair), and incidence gadgets (two per unordered color pair). The demands inside the incidence gadgets are chosen so that only a vertex pair corresponding to an actual edge of the original graph can satisfy them; the budget forces exactly $q$ selected vertices and exactly one selected vertex per color. On the algorithmic side, the positive results run either on a modular decomposition parse tree, where modules are induced subgraphs whose vertices share all neighbors outside the module, or on a nice tree decomposition, where a dynamic program tracks binary states (selected or not) and residual demands for the vertices in each bag.","core_discovery":"On its own terms, the paper shows that Vector Domination (VD), and therefore Distance Vector Domination, remains W[1]-hard with respect to neighborhood diversity even when every radius is 1. The proof reduces from Multicolored Clique, building a graph $G'$ from selection gadgets (two cliques and a bag per color), multiple gadgets (bags and cliques per color pair), and incidence gadgets (three bags per ordered color pair) whose demands encode vertex indices and edge endpoints; the budget is $k = qr + \\binom{q}{2}(2r+3)s$. Lemma 1 asserts the constructed VD instance has a solution of size $k$ exactly when $G$ has a multicolored clique of size $q$, and the graph's neighborhood diversity is $O(q^2)$. The paper also contributes FPT algorithms: RD in time $O(mw\\,2^{mw} n)$, VD in $O(mw\\, k (k+1)^{mw} n^2)$, DVD in $O(mw^2 k (k+1)^{2mw} n^2)$, VD in $O(tw^2 2^{tw} (\\tau+1)^{tw} n)$, and RD in $O(tw (2\\delta+1)^{tw} (tw^2+n) n^2 \\log n)$.","pith_inferences":["A direct corollary the authors do not spell out is that the same construction, once Lemma 1 is supplied, should also rule out FPT algorithms for VD parameterized by any parameter that is upper-bounded by neighborhood diversity, beyond the modular-width and clique-width cases mentioned in the paper.","The open gap named in the paper, an FPT algorithm for DVD parameterized by treewidth together with $k$, $\\tau$, or $\\delta$, is a natural next target; the two treewidth algorithms here solve only the one-sided variants of the problem.","One testable extension would be to instantiate the reduction on small random graphs and solve the VD instance exactly, comparing the true minimum solution size against the claimed budget; that would provide an empirical check on the unproven Lemma 1.","The misinformation-motivated framing suggests an applied direction worth exploring: on graphs with small modular-width, the practical bottleneck for computing an immunizing set may be obtaining the modular decomposition itself rather than evaluating the domination condition."],"forward_implications":["Unless FPT equals W[1], Vector Domination has no fixed-parameter algorithm parameterized only by neighborhood diversity, and the same holds for the more general Distance Vector Domination.","The hardness transfers to modular-width and clique-width, which are more general structural parameters than neighborhood diversity, so the negative result covers dense graph classes beyond the constructed instance.","Radius-only domination (R-domination) is tractable in FPT time on bounded modular-width graphs, with running time $O(mw\\,2^{mw} n)$.","Adding the solution size $k$ to modular-width makes both vector and distance-vector domination FPT, with running times exponential only in $mw$ and polynomial in $n$.","On bounded-treewidth graphs, vector domination is FPT when the maximum demand is added as a parameter, and radius-only domination is FPT when the maximum radius is added."],"supporting_citations":[{"why":"Supplies the W[1]-hardness of Multicolored Clique and the regular-color, regular-edge instantiations used as the reduction source.","marker":"[23]"},{"why":"Provides the bag-and-clique gadget design that the selection, multiple, and incidence gadgets adapt for this reduction.","marker":"[26]"},{"why":"Introduces neighborhood diversity, the structural parameter claimed to be bounded by $O(q^2)$ in the constructed graph.","marker":"[45]"},{"why":"Supplies the nice tree-decomposition normalization and the $O(tw \\cdot n)$ bag bound used by the treewidth algorithms.","marker":"[42]"},{"why":"Gives the optimal dynamic program for $r$-domination on tree decompositions whose strategy the RD/treewidth algorithm follows.","marker":"[8]"},{"why":"Provides the previous branchwidth-based FPT algorithm for vector domination whose running time Theorem 8 improves.","marker":"[38]"},{"why":"Establishes the W[1]-hardness of R-domination parameterized by treewidth, the backdrop against which the positive treewidth results are set.","marker":"[39]"}],"fun_headline_variants":["W[1]-hard vector domination even with unit radii","VD hard on diverse graphs at radius 1","FPT on modular width; W[1]-hard on diversity","Neighborhood diversity still W[1]-hard at radius 1","Distance vector domination: FPT on treewidth, hard on diversity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Lemma 1 asserts the equivalence between a solution of size $k$ in the constructed VD instance and a multicolored clique of size $q$ in the original graph; it is stated without proof, and the W[1]-hardness theorem collapses if the gadget analysis fails.","fun_headline_variants_meta":{"raw":{"variants":["W[1]-hard vector domination even with unit radii","VD hard on diverse graphs at radius 1","FPT on modular width; W[1]-hard on diversity","Neighborhood diversity still W[1]-hard at radius 1","Distance vector domination: FPT on treewidth, hard on diversity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001316,"raw_usage":{"total_tokens":5356,"prompt_tokens":933,"completion_tokens":4423,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":4338}},"tokens_in":549,"tokens_out":4423,"duration_ms":23691,"temperature":1.0,"reasoning_tokens":4338,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:13:35.437856+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small $q$, build the gadget graph $G'$ described in the proof for a multicolored clique instance whose only $q$-cliques are known, solve the VD decision problem exactly, and compare the minimum solution size against the claimed budget; a mismatch would refute Lemma 1 and with it the W[1]-hardness claim.","supporting_citations":[{"cited_title":"Cygan, F.V","cited_arxiv_id":null,"evidence_quote":"Supplies the W[1]-hardness of Multicolored Clique and the regular-color, regular-edge instantiations used as the reduction source."},{"cited_title":"Dvorák, D","cited_arxiv_id":null,"evidence_quote":"Provides the bag-and-clique gadget design that the selection, multiple, and incidence gadgets adapt for this reduction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces neighborhood diversity, the structural parameter claimed to be bounded by $O(q^2)$ in the constructed graph."},{"cited_title":"Borradaile and H","cited_arxiv_id":null,"evidence_quote":"Gives the optimal dynamic program for $r$-domination on tree decompositions whose strategy the RD/treewidth algorithm follows."},{"cited_title":"Ishii, H","cited_arxiv_id":null,"evidence_quote":"Provides the previous branchwidth-based FPT algorithm for vector domination whose running time Theorem 8 improves."},{"cited_title":"Katsikarelis, M","cited_arxiv_id":null,"evidence_quote":"Establishes the W[1]-hardness of R-domination parameterized by treewidth, the backdrop against which the positive treewidth results are set."}],"review_version":1}