{"id":"db2ff3a7-13af-482d-9873-beef13b448d9","arxiv_id":"2507.11446","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Dominating Set Reconfiguration under token sliding is W[2]-hard on graphs of bounded treewidth and pathwidth, and its directed version is NP-hard on shallow DAGs, marking the first known separation from independent-set reconfiguration.","lead":"This paper shows that rearranging dominating sets by sliding tokens along edges is computationally hard even on very sparse graphs, and even when the reconfiguration path is short. It contrasts sharply with the analogous independent-set problem, which is easy in the same settings, and resolves an open question in reconfiguration complexity.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The validator reduction's start set S does not dominate the red vertex s, so the constructed ReBuDSR-TS instances are invalid as written.","rationale":"The reader's weakest_assumption correctly targets the synchronization of the validator gadget, but the more load-bearing issue is that the reduction does not even produce a valid input instance: S is not a red-blue dominating set because the red vertex s has no neighbor in S. The text of Construction 4.1 is explicit that s is adjacent only to u^ℓ_{i,j} for 1≤j≤n, and the constructions in Theorems 4.3 and 4.7 place S = {s_1,…,s_k,h_0}; h_0 is connected only to p^ℓ_{j'} vertices. Therefore the initial configuration fails the mandatory domination condition. This is not a stylistic gap but a failure of the many-one reduction, because the target of the reduction is not a legal instance of the reconfiguration problem. The flaw appears to be easily repairable by adding edges from each sℓ to s (and verifying the rest of the proof), so the central theorems may survive a revision. Consequently, the reader's CONDITIONAL verdict remains appropriate: the paper needs major revision, not outright rejection, but the current text does not establish the claimed lower bounds. The synchronization concern raised by the reader is secondary and should also be addressed after the base case is fixed.","tokens_in":14469,"tokens_out":15963,"duration_ms":175855,"concrete_test":"Build the graph H from Theorem 4.3 for G = K_1 (single vertex v_1), k=1, n=1. Enumerate N[{s_1,h_0}]: s_1 is adjacent only to p^1_3 and p^1_1; h_0 only to p^1_3 and p^1_2; the red vertex s is adjacent only to u^1_{1,1}. Hence s ∉ N[{s_1,h_0}], so S is not a red-blue dominating set. If the authors intended an edge (sℓ,s), add it and recheck Claim 4.5's induction: the base case (j=0) must show s dominated by S, and the step must still force each token to advance exactly one column per clock move. If adding the edge is not sufficient to restore a valid reduction, the W[2]-hardness proof needs a new gadget.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Construction 4.1, the red vertex s is made adjacent only to the internal blue path vertices u^ℓ_{i,j} with 1≤j≤n; the endpoints sℓ=u^ℓ_{i,0} and dℓ are not adjacent to s. In Theorem 4.3 (and similarly Theorem 4.7 and the directed adaptations in Section 5), the start set is S = {s_1,…,s_k, h_0}. The path vertex h_0 is adjacent only to the p^ℓ_{j'} vertices, not to s, so no vertex of S is adjacent to the red vertex s. Thus S is not a red-blue dominating set, and (H,S,D) is not a valid ReBuDSR-TS instance: the definition requires the initial configuration to be a dominating set. The proof's first phase slides tokens from sℓ to u^ℓ_{i,1}; even if the post-move configuration dominates s, the sequence cannot legally start from a non-dominating S. This invalidates the reduction underlying Theorems 4.3, 4.7, 4.11 and 4.12, since every produced instance fails the problem's input conditions. The reader's concern about the synchronization invariants in Claims 4.6/4.9 is real, but the initial non-domination is a more basic failure that must be repaired first.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the token-sliding reconfiguration of dominating sets, both undirected (DSR-TS) and directed (DSR-DTS). It introduces a red-blue ``validator'' gadget and reduces from Dominating Set. The claimed results are: DSR-TS is W[2]-hard parameterized by k+pw+ι (Theorem 4.11), and W[2]-hard parameterized by k even on graphs of bounded pathwidth and treewidth (Theorem 4.12); in the directed setting, DSR-DTS is NP-hard on DAGs of depth 3, NP-hard on DAGs with fixed pathwidth 9 and treewidth 5, and W[2]-hard for DAGs parameterized by k+pw. The authors frame these as the first setting where independent-set reconfiguration is FPT but dominating-set reconfiguration is not, and they discuss simultaneous independent work on the same question.","tokens_in":14685,"tokens_out":7472,"duration_ms":94698,"significance":"If the reductions are correct, the paper gives a substantial answer to an open question: dominating set reconfiguration under token sliding is not FPT on bounded-treewidth graphs, in contrast to the token jumping variant and to independent set reconfiguration, and the directed variant is hard even on DAGs where the independent set version is FPT. The reductions are from the external W[2]-hard Dominating Set problem, so the hardness claims are grounded independently of the authors' prior work. The gadget constructions are natural and the stated bounds are small, which is valuable. However, the validity of the main reductions is currently blocked by a concrete flaw in the construction of the initial configuration, and a second, more subtle synchronization argument is not fully established. The paper's contribution will be solid once these issues are repaired.","major_comments":[{"comment":"The initial configuration S is not a red-blue dominating set, so the produced instances are not valid ReBuDSR-TS instances as defined. In Construction 4.1, the red vertex s is adjacent only to the vertices u^ℓ_i,j with 1≤j≤n, and it is not adjacent to sℓ = u^ℓ_i,0, dℓ, or any h vertex; the h vertices are adjacent only to the p^ℓ vertices. In Theorem 4.3 the start set is S = {s_1,...,s_k,h_0}, so no vertex of S dominates s. Since DSR-TS and ReBuDSR-TS require the initial configuration to be a dominating set, the reconfiguration sequence described in the proof cannot legally begin. The same flaw affects Theorem 4.7 and the directed adaptations in Section 5, and therefore the consequences Theorem 4.11, Theorem 4.12, Theorem 5.4, and Theorem 5.5. The construction must be modified, for example by adding edges from s to each sℓ and then rechecking every domination argument in the sequence.","section":"Section 4.1, Construction 4.1 and Theorem 4.3"},{"comment":"The synchronization proof does not rule out a gadget token switching between the internal paths P_i and P_i' at the shared endpoints sℓ and dℓ. For a fixed ℓ, all paths sℓ-u^ℓ_i,1-...-u^ℓ_i,n-dℓ share only sℓ and dℓ; a token that returns to sℓ could in principle depart along a different path. Claim 4.9 asserts that after a forward or backward move the ℓ-th token lies on some u^ℓ_i,j with the correct column j, but it does not prove that the index i is fixed for the whole sequence. The later extraction of the set I = {i_1,...,i_k} after the last time a=b is well-defined only under this additional invariance, and the application of Lemma 4.2 to that fixed index set is otherwise unjustified. The parity constraints may indeed prevent such switches, but the proof as written does not formalize this, and the invariant is load-bearing for Theorems 4.7 and 4.12.","section":"Section 4.2, Claim 4.9"},{"comment":"The stated treewidth values are inconsistent. Claim 4.8 constructs a tree decomposition whose largest bag contains 7 vertices and concludes treewidth 6; Lemma 4.10 increases the treewidth by 3, which yields treewidth 9. The abstract says treewidth 9, but Theorem 4.12 states treewidth 10. The pathwidth bound 13 is consistent with Claim 4.8's pathwidth 10 plus the additive 3 from Lemma 4.10. The treewidth statement should be corrected and the decomposition checked so that the exact numerical claims in the theorem, abstract, and proof agree.","section":"Section 4.3, Theorem 4.12 versus Claim 4.8 and the abstract"}],"minor_comments":[{"comment":"The sentence ``Dominating Set is known to be W[1]-hard'' is misleading; Dominating Set is W[2]-complete, and the paper's reductions should be described as FPT reductions from Dominating Set.","section":"Section 2, Parameterized Complexity"},{"comment":"The text describing the vertex construction is corrupted: the word ``Vertices:'' is repeated many times, and the membership lists ``a1,a2,a3,a5∈S and a1,a2,a4,a7∈S'' are incoherent because both lists contain a1 and a2. Please rewrite this passage and align it with Figure 1.","section":"Section 3, Theorem 3.1 proof"},{"comment":"The displayed formula for the iteration parameter is hard to parse; in particular, the set whose cardinality is taken mixes the starting position with entries and the condition ``α_{i-1}(t)≠α_i(t)=v'' is ambiguous. A precise verbal definition would improve readability.","section":"Section 2, Definition 2.1"},{"comment":"The parameter dfvs is used without being defined in the preliminaries; the directed feedback vertex set should be defined explicitly.","section":"Section 5, Theorem 5.2 and Lemma 5.3"},{"comment":"There are several editorial errors in this section: the sentence ``Not the validator gadget to yields even better bounds but blows up k'' is incomplete, and ``We now proof that ReBuDSR-DTS is hard...'' should read ``We now prove...''.","section":"Section 6, opening and proof of Claim 6.5"}],"recommendation":"major_revision","confidential_remarks":"The initial non-domination flaw in Construction 4.1 invalidates the reductions as written, but it is likely repairable by a local modification of the gadget or the start set; the synchronization gap in Claim 4.9 also needs a rigorous treatment. The authors are open about the simultaneous related work [6], and the iteration-parameter separation is the distinctive contribution. I recommend major revision: the paper should not be accepted until the reductions are corrected and the exact treewidth inconsistency is resolved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know before reading closely: the core reductions in Section 4 do not produce valid ReBuDSR-TS instances. In Construction 4.1, the red vertex s is adjacent only to internal blue path vertices u^ell_{i,j} with 1 <= j <= n. The start vertices s_ell (u^ell_{i,0}) and the clock vertex h_0 are not adjacent to s, so the proposed start set S = {s_1,...,s_k, h_0} fails to dominate s. Since ReBuDSR requires every configuration to be a red-blue dominating set, the instances are illegal from step zero. This affects Theorems 4.3, 4.7, 4.11, and 4.12, and likely the directed adaptations in Section 5. The synchronization concerns you flagged are real, but this initial non-domination is a more basic failure that must be repaired first.\n\nThe paper is not without merit. The question is a good one: it targets the open case [7, Question 10], and the lower constants (treewidth 9/10, pathwidth 13) would improve on the independent simultaneous work [6]. The DAG depth-3 NP-hardness and the directed variants add coverage. The red-blue gadget is a reasonable strategy, and the authors are transparent about the overlap with [6].\n\nThat said, there are multiple soft spots beyond the fatal one. The treewidth numbers are inconsistent: the abstract says 9, Theorem 4.12 says 10, and Claim 4.8 says 6 with a bag count that suggests 7. Section 2 defines treewidth as largest bag size plus one, off by one from the standard convention. The synchronization Claims 4.6 and 4.9 are sketched and need real expansion, especially Claim 4.9 with the unbounded clock. The claimed first separation between ISR-TS and DSR-TS relies on the FPT result from the authors' own preprint [9]; that dependency should be verified or clearly flagged.\n\nOn balance, the core idea is salvageable, for instance by adding s to the start set or making the clock vertex dominate s. But the current manuscript does not establish its main theorems. A referee could work through a fix, so it merits peer review in that sense, but the paper needs major revision and re-verification before acceptance. If you are assigning referees, this is a legitimate target, though expect a heavy revision cycle.","headline":"The central reductions fail because the start set does not dominate the red vertex s; the paper needs a fix but the target question is worth referee time.","tokens_in":748,"tokens_out":1991,"would_cite":false,"duration_ms":46793,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","05C85","68Q27","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes that the token-sliding version of dominating set reconfiguration is W[2]-hard on graphs of bounded pathwidth and treewidth, and that the directed variant is already intractable on very shallow DAGs.","keywords":["dominating set reconfiguration","token sliding","W[2]-hardness","pathwidth","treewidth","directed acyclic graphs","fixed-parameter tractability","reconfiguration"],"falsifier":"Run a brute-force state search on the validator construction with k=2 and a small graph G (say three vertices) to enumerate all token configurations reachable while dominating all red vertices; if any reachable configuration has a gadget token on a different index path than the one it started on when the clock has not yet finished, the synchronization invariant that the reduction depends on fails.","tokens_in":14221,"feed_emoji":"♟️","tokens_out":7986,"duration_ms":89594,"temperature":0.7,"pith_summary":"The paper attacks an open question about reconfiguration: when you must transform one dominating set into another of the same size by sliding a single token along an edge at a time, keeping the set dominating at every step, is the problem fixed-parameter tractable in the set size k? The answer given here is no, even for very sparse graphs: DSR-TS is W[2]-hard for parameter k on undirected graphs with pathwidth 13 and treewidth 10, and W[2]-hard for k together with pathwidth and the newly introduced iteration parameter. For directed token sliding, the paper shows NP-hardness already on DAGs of depth 3, and W[2]-hardness on DAGs parameterized by k and pathwidth. These results matter because the parallel independent-set and token-jumping problems are FPT in the same regimes, so they map a sharp boundary where the dominating-set sliding problem escapes tractability.","feed_headline":"No FPT for token-sliding domination, even at pathwidth 13","feed_subtitle":"Even bounding the number of visits per vertex does not make the problem tractable unless W[2]=FPT.","key_machinery":"The validator gadget: given a graph G and integer k, it creates k blue paths, one per token, each path having a segment for every vertex of G; red vertices $p^\\ell_1$, $p^\\ell_2$, $p^\\ell_3$ and $s$ are connected so that a token on path position $(i,j)$ can only move in synchronization with a clock, and the red vertex $s$ is dominated exactly when the chosen indices $\\{i_1,\\dots,i_k\\}$ form a dominating set of G (Lemma 4.2). A blue path or 3-cycle acts as the clock that forces all gadget tokens to advance exactly one position per tick, and the parity connections to $p^\\ell_1,\\dots,p^\\ell_3$ are what lock the tokens to their chosen index path. The mechanism transfers the reconfiguration question to the existence of a dominating set by extracting the indices of the tokens when the clock completes its traversal.","core_discovery":"The central claim is that the reconfiguration problem DSR-TS remains W[2]-hard when parameterized by the dominating set size k even when the input graph has constant pathwidth 13 and treewidth 10, and even when the reconfiguration sequence is constrained to have iteration 1 and pathwidth is added to the parameter. The directed variant DSR-DTS is NP-hard on DAGs of depth 3 and W[2]-hard on DAGs parameterized by k plus pathwidth, and remains NP-hard on DAGs of pathwidth 9 and treewidth 5. The authors build reductions from dominating set through a red-blue validator gadget and a clock gadget, and transfer the hardness from the red-blue variant to the uncolored problem via gadgets that trap tokens in their components. In the undirected case the same construction, without the iteration bound, gives hardness on graphs whose pathwidth and treewidth are fixed small constants.","pith_inferences":["A natural next step is to test whether the same validator gadget can express other domination-like reconfiguration problems, such as connected dominating set or total dominating set, under token sliding, which would likely inherit the same sparse hardness.","Because the reduction's width bounds come from the clock gadget, replacing the 3-cycle clock with a different bounded-width synchronizer might lower the treewidth bound further, a question the paper leaves open.","The depth-2 tractability result suggests a broader program: for each fixed depth d, determine the complexity of DSR-DTS on DAGs of depth d, with the likely threshold at d=3.","The W[2]-hardness for DSR-TS on bounded pathwidth does not rule out XP algorithms; an empirical or theoretical check of whether a dynamic program with complexity n^{O(k)} exists on such graphs would delineate the boundary more sharply."],"forward_implications":["No fixed-parameter algorithm for DSR-TS parameterized by k exists on graphs of bounded pathwidth or treewidth unless FPT = W[2].","In the same sparse settings where independent set reconfiguration under token sliding is known to be fixed-parameter tractable, the dominating set version is provably hard, separating the two problems.","The iteration parameter, which bounds how often a token may visit a vertex, does not buy tractability: hardness holds even with iteration 1 when k and pathwidth are parameters.","For DAGs, depth is a sharp boundary: DSR-DTS is solvable in linear time on depth 2 but NP-hard on depth 3, and remains W[2]-hard on DAGs when k and pathwidth are parameters.","The explicit width bounds (pathwidth 13, treewidth 10 undirected; pathwidth 9, treewidth 5 directed) mean the hardness holds on graphs that are genuinely narrow, not just asymptotically sparse."],"supporting_citations":[{"why":"Defines the iteration parameter and shows ISR-TS is FPT on DAGs, the contrasting result the paper's hardness bounds are built against.","marker":"[9]"},{"why":"Introduces directed token sliding and shows ISR-DTS is W[1]-hard on DAGs, the setting and problem variant the paper extends to dominating sets.","marker":"[12]"},{"why":"Independently and simultaneously proves a similar hardness result for DSR-TS via a different technique; the paper compares its smaller pathwidth and treewidth bounds to it.","marker":"[6]"},{"why":"Surveys reconfiguration problems and highlights the open question on dominating set reconfiguration under token sliding that this paper resolves.","marker":"[7]"}],"fun_headline_variants":["Token-sliding domination W[2]-hard even at pathwidth 13","Even bounded visits don't fix dominating set reconfiguration","Sparse graphs fail to yield FPT for token-sliding domination","Directed token-sliding domination NP-hard on DAGs","Harder than independent sets: dominating set reconfiguration resists FPT"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole reduction rests on the synchronization invariant that, at every clock step, each gadget token sits exactly one column ahead of the clock token and never switches between the k index paths; if a token could drift or switch paths in some reachable configuration, the extracted indices need not form a dominating set.","fun_headline_variants_meta":{"raw":{"variants":["Token-sliding domination W[2]-hard even at pathwidth 13","Even bounded visits don't fix dominating set reconfiguration","Sparse graphs fail to yield FPT for token-sliding domination","Directed token-sliding domination NP-hard on DAGs","Harder than independent sets: dominating set reconfiguration resists FPT"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0019,"raw_usage":{"total_tokens":7512,"prompt_tokens":1078,"completion_tokens":6434,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":694,"completion_tokens_details":{"reasoning_tokens":6345}},"tokens_in":694,"tokens_out":6434,"duration_ms":54378,"temperature":1.0,"reasoning_tokens":6345,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:10:31.559633+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a brute-force state search on the validator construction with k=2 and a small graph G (say three vertices) to enumerate all token configurations reachable while dominating all red vertices; if any reachable configuration has a gadget token on a different index path than the one it started on when the clock has not yet finished, the synchronization invariant that the reduction depends on fails.","supporting_citations":[{"cited_title":"Token Sliding Reconfiguration on DAGs","cited_arxiv_id":"2504.10671","evidence_quote":"Independently and simultaneously proves a similar hardness result for DSR-TS via a different technique; the paper compares its smaller pathwidth and treewidth bounds to it."}],"review_version":1}