{"id":"c3991a63-9fe3-4e8d-928c-7cf6e815df71","arxiv_id":"2505.07268","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"This paper introduces Connected Components Reconfiguration with component-jumping and component-sliding rules and gives linear or quadratic time algorithms on paths, cographs, and chordal graphs.","lead":"Connected Components Reconfiguration (CCR) makes each moving token a connected blob of graph vertices, generalizing the classic Independent Set Reconfiguration problem. This paper gives fast algorithms on paths, cographs, and chordal graphs, while the general problem remains PSPACE-complete.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The chordal result rests on Lemma 5, whose proof in Appendix C is not valid as written: the asserted shortest cycle through chosen vertices need not exist and need not be induced; however an independent clique-tree argument suggests the lemma is true, so the result is likely repairable.","rationale":"The reader's weakest assumption is exactly the point I would stress: Lemma 5 is the load-bearing step for Corollary 1, and the supplied proof is a three-sentence sketch that asserts the existence and inducedness of a cycle through arbitrary vertices without justification. I agree that this warrants a CONDITIONAL verdict: the manuscript should be revised to supply a correct proof of Lemma 5 before the chordal result can be considered fully verified. I did not find a separate counterexample, and an independent clique-tree argument indicates the lemma is actually true, so the concern is about proof completeness rather than the truth of the central claim. I also checked Theorem 5's greedy step: deleting the chosen component pair from the CC-Piran graph faithfully models applying the corresponding CJ move, so the forest argument is sound once even-hole-freeness is available. No other load-bearing issue emerged.","tokens_in":12241,"tokens_out":26089,"duration_ms":288677,"concrete_test":"Replace the appendix proof of Lemma 5 with the clique-tree argument: for chordal G, build a clique tree T; for each component C in C(A)\\C(B) union C(B)\\C(A), define S_C as the union of T_v over v in C; prove S_C is connected, same-side S_C families are pairwise disjoint, and the CC-Piran graph has an edge exactly when two such sets intersect. If this verification succeeds, Lemma 5 and Corollary 1 stand. As an independent search, enumerate small chordal graphs and all pairs A,B of equal-size component subsets and test whether the resulting CC-Piran graph contains an induced C4 or C6; finding one would refute the chordal claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim Corollary 1 depends on Lemma 5, which says the CC-Piran graph of a chordal graph is even-hole-free. The proof in Appendix C is not valid as written. It assumes that an induced even cycle in the CC-Piran graph yields vertices v_A^i, v_B^i and then takes a shortest cycle C* through those vertices 'in this order,' claiming C* must be induced. Both steps fail in general: the touch relations only provide edges between possibly different vertices of neighboring components, so a cycle through the arbitrarily chosen vertices need not exist; and a shortest cycle constrained to contain prescribed vertices is not necessarily induced, because a chord can create a shorter cycle that omits one of the prescribed vertices. Thus the text does not establish Lemma 5, and Corollary 1 is unsupported as written. That said, the lemma appears to be true: in a clique tree T of a chordal graph, each component C of A or B corresponds to the connected set S_C of clique nodes containing vertices of C; distinct A-components have disjoint S_C, and likewise for B-components; CC-Piran edges are exactly intersections S_C cap S_C'. Hence the CC-Piran graph is an intersection graph of subtrees of a tree, so it is chordal and, being bipartite, a forest. The flaw is therefore a proof gap in the manuscript rather than a discovered counterexample to the theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Connected Components Reconfiguration (CCR), a generalization of independent set reconfiguration in which each intermediate set must induce connected components whose sizes match a prescribed multiset M. Two new rules are proposed: component jumping (CJ) and component sliding (CS), together with a one-vertex variant CS1. The paper proves that CCR is PSPACE-complete in general, gives an O(n) algorithm for CCR-CS on paths and an O(n^2) algorithm for CCR-CJ on paths, gives an O(|V|+|E|) algorithm for CCR-CS on cographs, and gives an O(|V|+|E|) algorithm for CCR-CJ on chordal graphs when all components have equal size. The chordal result is obtained through a new CC-Piran graph, an extension of the Piran graph of Kamiński et al., and rests on the claim that for chordal G the CC-Piran graph is even-hole-free.","tokens_in":12502,"tokens_out":16875,"duration_ms":185814,"significance":"If the results hold, they form a worthwhile contribution to combinatorial reconfiguration. The token-as-component abstraction is natural and the contrast between the new rules and the classical TJ/TS rules is interesting; in particular, Corollary 1 shows that induced matching reconfiguration under CJ on chordal graphs is linear, whereas under TJ it is PSPACE-complete. The paper is constructive, with explicit algorithms and time bounds, and it uses standard cited tools rather than fitted or post-hoc assumptions. The path-CJ buffer argument and the CC-Piran graph framework are the main conceptual strengths. However, two proof gaps, one in Lemma 5 and one in Lemma 4, currently prevent the corresponding theorems from being considered fully established.","major_comments":[{"comment":"","section":"Appendix C, Lemma 5"},{"comment":"","section":"Appendix B.1, Lemma 4"},{"comment":"","section":"Section 4, Lemma 1"}],"minor_comments":[{"comment":"","section":"Definition 3"},{"comment":"","section":"Theorem 5"},{"comment":"","section":"Algorithm 2"},{"comment":"","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely correct after repair. The Appendix C gap in Lemma 5 is the main obstacle; a clique-tree proof appears to settle the lemma, so I recommend major revision rather than rejection. The Lemma 4 induction also needs a careful fix. The path results and the CC-Piran greedy argument are the strongest parts and should survive revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The new problem is the real contribution: treating connected components as tokens under CJ/CS is a natural generalization of ISR that changes the complexity landscape, and the paper backs it with two concrete algorithmic results and one hardness reduction. The path results are clean: Lemma 2's buffer inversion characterization is a nice reduction to sorting, and the quadratic bound is justified by the ISR lower bound. The cograph algorithm is a faithful generalization of Kamiński et al. with a plausible induction in Lemma 4; the cases are terse but the structure is standard and I believe it holds. The equal-size CJ result on chordal graphs, via the CC-Piran graph, is the most interesting part: it gives a real separation between TJ and CJ, and Corollary 1's contrast with induced matching reconfiguration is a good insight.\n\nNow the soft spots, in proportion. The proof of Lemma 5 in Appendix C is not valid as written. The stress-test note is right: an induced even cycle in the CC-Piran graph gives adjacency relations between components, but those edges do not pin down specific vertices within each component that can be arranged into a cycle in G. A 'shortest cycle through the vertices in this order' need not exist, and even if it does, it is not automatically induced, because a chord could produce a shorter cycle that skips one of the prescribed vertices. So Corollary 1 is unsupported by the text as it stands.\n\nThat said, I agree with the stress-test's independent assessment that the lemma is true. Via clique trees of a chordal graph, each A- or B-component corresponds to the connected set of clique nodes containing its vertices; CC-Piran edges correspond exactly to intersections of those sets. The CC-Piran graph is therefore an intersection graph of subtrees of a tree, so it is chordal, and since it is bipartite, it is a forest. That repair is short and direct. So the right reading is not 'the theorem is false' but 'the published proof has a gap that an expert can fill.'\n\nThe paper ships no code, but it does not need it: the algorithms are described well enough to implement, and the reductions are parameter-free. Citation pattern is good; it builds on Kamiński et al. and Elbassioni appropriately.\n\nVerdict: I would send this to peer review. The gap in Lemma 5 should be fixed, and Lemma 4 deserves a fuller write-up, but the problem definition and the path/cograph results are worth publishing on their own they are a serious contribution. A competent referee can verify the repair and make the recommendation straightforward:\naccept after the proof of Lemma 5 is replaced with the clique-tree argument (or another correct one).","headline":"Solid new problem formulation and clean path/cograph results; the chordal result is likely correct but rests on a lemma whose written proof is not valid as written.","tokens_in":13030,"tokens_out":663,"would_cite":true,"duration_ms":8780,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","05C85","68R10","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces Connected Components Reconfiguration and proves that equal-size component jumping is solvable in linear time on chordal graphs.","keywords":["combinatorial reconfiguration","connected components","component jumping","component sliding","cographs","chordal graphs","independent set reconfiguration","CC-Piran graph"],"falsifier":"Exhibit a chordal graph G and two equal-size component configurations A and B whose auxiliary touch graph contains an induced 4-cycle (or any even cycle); Lemma 5 states no such configuration exists, so this would refute the linear-time chordal algorithm.","tokens_in":12010,"feed_emoji":"🧩","tokens_out":5570,"duration_ms":50494,"temperature":0.7,"pith_summary":"The paper proposes a new reconfiguration problem in which the objects being moved are connected components of a graph vertex subset, with prescribed sizes, rather than single vertices. It introduces two movement rules, component jumping and component sliding, and asks whether one configuration of components can be transformed into another while every intermediate configuration has the same multiset of component sizes. Because independent-set reconfiguration is the special case where every component has size 1, the general problem is PSPACE-complete. The paper's main positive results are linear-time algorithms on paths for sliding, on cographs for sliding, and on chordal graphs for jumping when all components have the same size. A sympathetic reader would care because these are among the first tractability results for a reconfiguration problem whose tokens are themselves connected subgraphs.","feed_headline":"Equal-size component jumping is linear-time on chordal graphs","feed_subtitle":"New component-jumping rule lets connected tokens reconfigure in O(|V|+|E|), extending a classic independent-set result.","key_machinery":"The load-bearing object is the CC-Piran graph $\\Pi_{cc}(A,B)$, a bipartite graph whose vertices are the connected components of $A$ that are not components of $B$, and vice versa, with an edge when two components' vertex sets touch (their union is connected). The paper shows that when all components have the same size and $\\Pi_{cc}(A,B)$ is even-hole-free—hence, being bipartite, a forest—there is always a component of $B\\setminus A$ with at most one neighbor in $A\\setminus B$, so the greedy 'move any unmatched component onto a target component' algorithm terminates in exactly $|A\\setminus B|$ steps and is therefore shortest. Lemma 5 bridges this combinatorics to chordal graphs by claiming that chordality of $G$ forbids induced even cycles in $\\Pi_{cc}(A,B)$. For paths and cographs, the machinery is instead a leftmost-position buffer/inversion-sort argument and a cotree-based divide-and-conquer.","core_discovery":"The central discovery is that when every connected component has the same size, the reconfiguration of components under the jumping rule is governed entirely by a sparse auxiliary graph, the CC-Piran graph $\\Pi_{cc}(A,B)$, whose vertices are the components that differ between $A$ and $B$ and whose edges record when two components touch. If this auxiliary graph is even-hole-free, a simple greedy algorithm reconfigures $A$ into $B$ in a shortest possible way, moving one component per step. Since chordal graphs guarantee that $\\Pi_{cc}(A,B)$ is even-hole-free, it follows that for chordal $G$ and equal-size components, CCR-CJ is solvable in $O(|V|+|E|)$ time and a shortest reconfiguration sequence can be found in the same bound. The same $O(|V|+|E|)$ bound holds for component sliding on cographs, while on paths sliding is solvable in linear time and jumping in quadratic time.","pith_inferences":["The forest-greedy argument suggests a wider principle: whenever the CC-Piran graph is a forest, equal-size component jumping is tractable via a matching-like greedy, so identifying graph classes where $\\Pi_{cc}(A,B)$ is forest-like would yield more linear-time results.","The path result's buffer/inversion perspective connects CCR-CJ to sorting with a buffer; one could test whether the quadratic bound is tight for paths with more than two distinct sizes.","The paper's Figure 3 example shows that with unequal component sizes the greedy fails; an immediate open test is whether chordal graphs with two size classes are already PSPACE-complete under CJ, which would sharply delimit the equal-size assumption.","The contrast between sliding and jumping hints that sliding constraints make cographs easy while jumping on chordal graphs is easy only in the equal-size case; extrapolating to trees may reveal a complexity dichotomy."],"forward_implications":["If $G$ is chordal and every component in $A$ and $B$ has the same size, $A$ and $B$ are reconfigurable under component jumping exactly when they have the same component-size multiset, and a shortest reconfiguration sequence can be produced in linear time.","Component sliding and component sliding-by-one-vertex are equivalent for reconfigurability, so the cograph linear-time result applies to both rules.","On paths, component sliding reconfigurability is exactly equality of the left-to-right sequence of component sizes, while component jumping adds a buffer-based condition computable in quadratic time.","Induced matching reconfiguration, which is PSPACE-complete under token jumping on chordal graphs, becomes linear-time under component jumping when tokens are the connected components themselves, showing that the choice of token shape changes complexity."],"supporting_citations":[{"why":"Supplies the Piran-graph forest-greedy method for independent set reconfiguration that the paper generalizes to connected components.","marker":"[14]"},{"why":"Gives the characterization of cographs (P4-free, every induced subgraph or its complement disconnected) used in the cograph algorithm.","marker":"[3]"},{"why":"Provides the cotree decomposition used to implement the cograph algorithm in linear time.","marker":"[4]"},{"why":"Lemma 6 (existence of a sequence of connected vertex subsets changing one vertex at a time) underlies the proof that CS and CS1 are equivalent.","marker":"[6]"},{"why":"Shows induced matching reconfiguration is PSPACE-complete under token jumping on chordal graphs, the contrast for the chordal linear-time result.","marker":"[7]"},{"why":"Gives the quadratic lower bound for sliding-token sequences on paths that the paper's path results match in length.","marker":"[5]"}],"fun_headline_variants":["Component jumping hits linear time on chordal graphs","Equal-size component reconfiguration solved in O(V+E) on chordal graphs","CCR: component sliding and jumping get linear time on key graph families","Same-size components jump in linear time on chordal graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The chordal result rests on the claim that contracting the differing connected components of A and B in a chordal graph never creates a forced even cycle in the auxiliary touch graph; the paper's proof of this fact is a brief sketch that assumes the shortest cycle exists without constructing it.","fun_headline_variants_meta":{"raw":{"variants":["Component jumping hits linear time on chordal graphs","Equal-size component reconfiguration solved in O(V+E) on chordal graphs","CCR: component sliding and jumping get linear time on key graph families","Same-size components jump in linear time on chordal graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000288,"raw_usage":{"total_tokens":1712,"prompt_tokens":991,"completion_tokens":721,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":648}},"tokens_in":607,"tokens_out":721,"duration_ms":6695,"temperature":1.0,"reasoning_tokens":648,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:23:59.166978+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a chordal graph G and two equal-size component configurations A and B whose auxiliary touch graph contains an induced 4-cycle (or any even cycle); Lemma 5 states no such configuration exists, so this would refute the linear-time chordal algorithm.","supporting_citations":[{"cited_title":"Theoretical computer science439, 9–15 (2012)","cited_arxiv_id":null,"evidence_quote":"Supplies the Piran-graph forest-greedy method for independent set reconfiguration that the paper generalizes to connected components."},{"cited_title":"Dis- crete Applied Mathematics3(3), 163–174 (1981)","cited_arxiv_id":null,"evidence_quote":"Gives the characterization of cographs (P4-free, every induced subgraph or its complement disconnected) used in the cograph algorithm."},{"cited_title":"SIAM Journal on Computing14(4), 926–934 (1985)","cited_arxiv_id":null,"evidence_quote":"Provides the cotree decomposition used to implement the cograph algorithm in linear time."},{"cited_title":"Journal of Graph Algorithms and Applications 19(1), 273–280 (2015)","cited_arxiv_id":null,"evidence_quote":"Lemma 6 (existence of a sequence of connected vertex subsets changing one vertex at a time) underlies the proof that CS and CS1 are equivalent."},{"cited_title":"In: International Conference and Workshops on Algorithms and Computation","cited_arxiv_id":null,"evidence_quote":"Shows induced matching reconfiguration is PSPACE-complete under token jumping on chordal graphs, the contrast for the chordal linear-time result."},{"cited_title":"Theoretical Computer Science600, 132–142 (2015)","cited_arxiv_id":null,"evidence_quote":"Gives the quadratic lower bound for sliding-token sequences on paths that the paper's path results match in length."}],"review_version":1}