{"id":"ccedec59-7a4f-4ec8-b45a-d4688da78189","arxiv_id":"2607.00637","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An iterative graph-lifting algorithm that automatically refines path-complete graphs via analysis of active constraints to approximate the joint spectral radius of switched linear systems.","lead":"This paper introduces an iterative algorithm that refines path-complete graphs by splitting nodes based on optimality conditions to generate stability certificates for switched linear systems. The approach aims to compute or closely approximate the joint spectral radius more effectively than prior methods.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Active-constraint graph may fail to identify nodes whose splitting yields a strictly tighter or exact JSR certificate","rationale":"The reader's weakest assumption matches the single algorithmic step whose correctness is required for both the exactness claim and the reported outperformance. Because the review was performed on the abstract, the same load-bearing point remains after the placeholder full-text instruction; no independent verification (e.g., machine-checked proof or reproducible code) is mentioned that would remove the need to test this step directly.","tokens_in":1684,"tokens_out":340,"duration_ms":17535,"concrete_test":"Take the smallest switched system in the numerical section whose exact JSR is known analytically. Solve the initial LP, extract the active-constraint subgraph, apply the paper's node-splitting rule, and re-solve; if the new bound equals the old bound while the sufficient condition remains unsatisfied, the identification procedure does not guarantee improvement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The algorithm's refinement step rests on the claim that the subgraph induced by active constraints in the optimality conditions of the path-complete JSR LP correctly flags bottleneck nodes for local lifting. The abstract asserts that a sufficient condition for exact JSR is derived from this analysis and that splitting produces refinement when the condition fails, yet supplies no explicit statement of the optimality conditions, the induced-graph construction, or a proof that the chosen splits preserve path-completeness while strictly decreasing the objective. If the active-set analysis omits cross-path dependencies or if the lifting operation can leave the bound unchanged, the iteration may terminate at a suboptimal certificate even when the sufficient condition is not met.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper proposes an iterative algorithm for automatically refining path-complete graphs to approximate or attain the exact joint spectral radius (JSR) of switched linear systems. It performs a graph-theoretic analysis of the optimality conditions of the associated linear program to derive a sufficient condition under which a given path-complete graph yields the exact JSR. When the condition fails, the algorithm constructs the subgraph induced by active constraints to identify bottleneck nodes, applies local lifting via node splitting to refine the graph while preserving path-completeness, and iterates. Numerical experiments indicate that the method outperforms existing approaches on all tested challenging instances.","tokens_in":1818,"tokens_out":496,"duration_ms":18768,"significance":"If the central claims hold, the work offers a systematic, optimization-driven procedure for improving path-complete stability certificates, with the potential to achieve exact JSR more reliably than prior heuristic or manual designs. The grounding in optimality conditions of the JSR LP and the empirical outperformance on hard instances are notable strengths that could advance computational methods for stability analysis of switched systems.","major_comments":[{"comment":"The section deriving the sufficient condition for exact JSR (based on active-constraint analysis): the argument that the induced subgraph correctly identifies all bottleneck nodes whose splitting yields exactness must explicitly rule out omitted cross-path dependencies in the path-complete graph; without this, the sufficiency claim risks being incomplete.","section":"Section on sufficient condition and active constraints"},{"comment":"The section on the local lifting operation: it is not shown that node splitting always produces a strictly tighter bound (or preserves feasibility) when the sufficient condition fails; if the lifting can leave the JSR upper bound unchanged due to unaccounted interactions, the iteration may terminate suboptimally even when refinement is possible.","section":"Section on graph lifting and refinement"}],"minor_comments":[{"comment":"The numerical experiments section would benefit from reporting the fraction of instances where the sufficient condition is met and from including an ablation on the effect of different splitting heuristics.","section":"Numerical experiments"},{"comment":"Notation for the path-complete graph, the LP variables, and the active-set subgraph should be introduced with a single consistent table or diagram to aid readability.","section":"Preliminaries"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the constructive and detailed comments. We address each major comment below, indicating the revisions we will make to clarify and strengthen the arguments in the manuscript.","responses":[{"response":"We appreciate the referee pointing out the need for an explicit treatment of cross-path dependencies. Path-completeness ensures that every finite switching sequence corresponds to at least one path in the graph, so any interaction between paths that could affect the optimality conditions of the JSR linear program must appear as an active constraint. Consequently the induced subgraph on active constraints already incorporates all such interactions. To make this reasoning fully transparent we will insert a short clarifying paragraph immediately after the statement of the sufficient condition, explicitly invoking the path-completeness definition to rule out omitted cross-path dependencies.","revision_made":"yes","referee_comment":"[Section on sufficient condition and active constraints] The section deriving the sufficient condition for exact JSR (based on active-constraint analysis): the argument that the induced subgraph correctly identifies all bottleneck nodes whose splitting yields exactness must explicitly rule out omitted cross-path dependencies in the path-complete graph; without this, the sufficiency claim risks being incomplete."},{"response":"The referee correctly notes that a formal guarantee on the effect of the local lifting step is not stated. While the construction is motivated by the active-constraint subgraph and the numerical results show improvement, we do not provide a general proof that node splitting always yields a strictly smaller optimal value of the linear program (hence a strictly tighter JSR upper bound) while preserving feasibility and path-completeness. We will add a short proposition establishing these properties by exhibiting an explicit feasible solution on the lifted graph whose objective value is strictly better whenever the sufficient condition fails.","revision_made":"yes","referee_comment":"[Section on graph lifting and refinement] The section on the local lifting operation: it is not shown that node splitting always produces a strictly tighter bound (or preserves feasibility) when the sufficient condition fails; if the lifting can leave the JSR upper bound unchanged due to unaccounted interactions, the iteration may terminate suboptimally even when refinement is possible."}],"tokens_in":1352,"tokens_out":462,"duration_ms":39803,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper's main contribution is an iterative refinement loop that starts from a path-complete graph, solves the associated LP, extracts the active constraints, builds an induced subgraph to flag bottleneck nodes, and performs local node splits to lift the graph. This is new in the way it ties optimality conditions directly to the lifting decision rather than relying on generic heuristics or exhaustive search.\n\nIt does a clean job of stating a sufficient condition under which the current graph already gives the exact JSR, and the numerical section shows the method beating prior approaches on the harder test cases without blowing up the graph size. The approach stays grounded in the existing path-complete framework instead of inventing new certificate classes.\n\nThe soft spot is the step that claims the active-constraint subgraph correctly identifies nodes whose split will produce a strictly better bound. The abstract asserts this works and that path-completeness is preserved, but the stress-test concern about possible missed cross-path dependencies is reasonable; if the full proof only shows sufficiency for exactness and not that every iteration improves when the condition fails, the loop could stall short of the optimum on some instances. The experiments do not appear to quantify how often the sufficient condition is met versus how often lifting is needed.\n\nThis is aimed at researchers who already use path-complete or JSR LP methods and want an automatic tightening tool. It is worth sending to peer review because the algorithmic idea is well-motivated and the numerics are presented as competitive, even if the refinement guarantee needs tighter justification.","headline":"The iterative active-constraint lifting procedure is a concrete algorithmic step forward for automatic path-complete JSR certificates, with a usable sufficient condition for exactness.","tokens_in":2270,"tokens_out":377,"would_cite":false,"duration_ms":12986,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"An iterative algorithm refines path-complete graphs by local node splitting to attain the exact joint spectral radius when a sufficient condition holds.","keywords":["path-complete graphs","joint spectral radius","switched linear systems","stability certificates","graph lifting","iterative algorithm","optimization"],"falsifier":"A switched linear system on which the sufficient condition is reported to hold yet the computed value differs from the true joint spectral radius obtained by any independent method.","tokens_in":2582,"feed_emoji":"🔄","tokens_out":582,"duration_ms":25772,"temperature":0.7,"pith_summary":"The paper develops an iterative procedure for constructing path-complete stability certificates for switched linear systems. It uses a graph-theoretic examination of optimality conditions in the underlying optimization problem to determine when a given labeled directed graph yields the exact joint spectral radius. When the condition fails, the method isolates bottleneck nodes from the active-constraint subgraph and refines the graph by splitting those nodes. The process repeats until either the exact value is reached or further improvement is obtained. This matters because the joint spectral radius governs worst-case trajectory growth under arbitrary switching, and manual design of tight certificates has been difficult.","feed_headline":"Iterative node splitting yields exact JSR certificates","feed_subtitle":"Active-constraint analysis automates refinement of path-complete graphs for switched linear stability","key_machinery":"Path-complete graphs (labeled directed graphs encoding algebraic stability certificates via an associated optimization problem), refined by local lifting (node splitting) guided by the active-constraint subgraph.","core_discovery":"The central claim is that analysis of the graph induced by active constraints in the path-complete optimization problem identifies nodes whose local lifting produces a strictly better certificate, and that a derived sufficient condition on this refined graph guarantees it attains the exact joint spectral radius.","pith_inferences":["The same active-constraint analysis could guide refinement in related graph-based certificate problems outside switched linear systems.","Systems with periodic or constrained switching signals might admit analogous lifting rules derived from their own optimality conditions.","The method's reported scalability suggests it could serve as a subroutine inside branch-and-bound or mixed-integer solvers for joint spectral radius."],"forward_implications":["Whenever the sufficient condition is satisfied after lifting, the resulting certificate equals the exact joint spectral radius.","The procedure terminates with an exact certificate on instances where the condition becomes true.","The refinement adds nodes only locally, keeping the graphs parsimonious.","Numerical tests show the method outperforms prior state-of-the-art approaches on all challenging instances examined."],"fun_headline_variants":["Active constraints spot nodes for exact-JSR graph lifting","Iterative node splitting from bottlenecks yields exact JSR","Active-set graph analysis drives path-complete refinement","Bottleneck nodes lifted iteratively for exact JSR certificates"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The active constraints correctly identify bottleneck nodes whose splitting produces a strictly better or exact certificate.","fun_headline_variants_meta":{"raw":{"variants":["Active constraints spot nodes for exact-JSR graph lifting","Iterative node splitting from bottlenecks yields exact JSR","Active-set graph analysis drives path-complete refinement","Bottleneck nodes lifted iteratively for exact JSR certificates"]},"model":"grok-4.3","cost_usd":0.006315,"raw_usage":{"total_tokens":2934,"prompt_tokens":601,"num_sources_used":0,"completion_tokens":60,"cost_in_usd_ticks":63149500,"prompt_tokens_details":{"text_tokens":601,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2273,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":601,"tokens_out":60,"duration_ms":15789,"temperature":1.0,"reasoning_tokens":2273,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-02T08:06:29.094986+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A switched linear system on which the sufficient condition is reported to hold yet the computed value differs from the true joint spectral radius obtained by any independent method.","supporting_citations":[],"review_version":1}