{"id":"a396816a-b6a9-471a-9516-d6b1373c53b7","arxiv_id":"2509.13584","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Dynamic k=3 core and truss decompositions are conditionally hard under OMv and SETH, while dynamic 2-core admits a polylog algorithm.","lead":"This paper proves conditional lower bounds showing that dynamic k-core, truss, and related decompositions have no fast generic algorithms unless major complexity conjectures fail, and it provides a polylogarithmic algorithm for the dynamic 2-core problem, confirming k=3 as the hardness threshold.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's bounded-FCM lower bound rests on an unproven invariant: if s* stays out of the 3-core, no other vertex can enter it. The proof neither states nor proves this, and the construction does not obviously enforce it.","rationale":"The reader's CONDITIONAL verdict identified the bounded-maintenance proof as a soft spot, specifically the eps=1 application of the OuMv equivalence and the non-fully-formal 'stop the algorithm' step. My pass agrees with that location but pinpoints a sharper problem: the stopping rule depends on an unproved monotonicity claim. If that claim is false, Theorem 4 (and Theorem 5) fail as written, and the abstract's 'no bounded algorithm' contribution is unsupported. The main OMv/SETH lower bounds for CoreValue and its variants are based on the MCVP-to-core reductions and appear internally sound; the 2-core algorithm is also independently supported by an implementation. Since the issue is testable by direct computation on the gadget and may be fixable by proving the invariant or adjusting the construction, a conditional verdict is appropriate rather than outright rejection. I found no internal flaw in the central reduction itself, and the concern is not with the standard conjectures used, but with a specific unproved claim in the proof.","tokens_in":21861,"tokens_out":26090,"duration_ms":300243,"concrete_test":"Implement the Theorem 4 gadget for a small OuMv instance, e.g., N=2, M=[[1,0],[0,0]], u=(1,0), v=(0,1) (so u^T M v=0), and insert the wires 1->L1 and R2->g* one at a time in each order, starting from G_M. After each insertion, compute the exact 3-core. If any vertex other than s* has core value 3 while K_{s*}=2, the invariant is false and the early-stopping rule is unsound. Repeat exhaustively over all u,v and insertion orders; a single such partial 3-core also falsifies the proof as written.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Section 7, Theorem 4 reduces OuMv to incremental FCM by adding wires one at a time. The proof contains the sentence: 'If, after adding an edge, the core value of s* does not change, then no core value changes.' This is load-bearing: it is what lets the algorithm stop after f(2^{2d+1}) steps and conclude u^T M v = 1. But no lemma establishes it. The graph built from Propositions 1 and 6 is monotone: inserting a wire can turn on a gate's subgraph without turning on g*. Nothing rules out an intermediate graph in which a proper set of vertices (e.g., a path from the modified 1-gate to some R_j, with the final R_j-to-g* wire absent) becomes a 3-core while s* remains at core value 2. In that case the affected set is large, the bounded algorithm may run long, and the modified algorithm would stop and incorrectly answer '1'. The proof needs an invariant that the 3-core of every intermediate graph is contained in the set of gates whose value is 1 and whose reachability to g* is already realized; this is not shown and is not implied by the final-graph argument. Theorem 5 inherits the gap. The final 'by Proposition 5 with eps=1' step is also suspect, since eps=1 makes the forbidden bound O(NQ+N^2), matching the achieved time.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies dynamic algorithms for k-core and related cohesive subgraph problems. It proves conditional lower bounds based on the OMv conjecture and SETH: no dynamic algorithm for MCVP, and hence for k-core (k≥3), (2−ε)-approximate core value, k-truss (k≥4), and directed (k,l)-core, can achieve polylogarithmic time, or even O(m^{1/2−ε}) update / O(m^{1−ε}) query time. An unconditional cell-probe lower bound of Ω(log n / log log n) is also given. For the maintenance versions (FCM and FTM), the paper claims that no bounded algorithm exists in the RAM model under OMv. On the positive side, it presents a polylogarithmic dynamic algorithm for 2-core, implemented and tested. The reductions are explicit and use constant-size gadgets for monotone circuit evaluation; the 2-core algorithm uses dynamic spanning forests, Euler tour trees, and link-cut trees.","tokens_in":22221,"tokens_out":20036,"duration_ms":193419,"significance":"If correct, the paper settles a central open question from the Hanauer–Henzinger–Schulz survey: dynamic core decomposition for k≥3 cannot be maintained in polylog time under standard fine-grained hypotheses. The lower bounds are the first for this problem family and are obtained via clean reductions from MCVP. The 2-core algorithm is an elegant positive result, with a machine-checked implementation, and it tightens the contrast with the k≥3 hardness. The main weakness is the proof of the unboundedness results for core/truss maintenance (Theorems 4 and 5), which rests on an unproved invariant. The OMv-, SETH-, and cell-probe-based parts appear sound.","major_comments":[{"comment":"The proof relies on the statement: 'If, after adding an edge, the core value of s* does not change, then no core value changes' and the consequent stopping rule. No lemma establishes this invariant. In the incremental construction of G_M(u,v), a proper subset of vertices could in principle enter the 3-core before s* does; the 3-core propagation argument is only asserted, not proved, for intermediate graphs. The correctness of the OuMv simulation depends on the invariant that the 3-core of every intermediate graph is contained in the subgraphs of gates whose value is 1 and whose reachability to g* is already realized, and that the first core-value change forces s* into the 3-core. Please add a formal induction over the edge insertions, or otherwise prove this invariant. Without it, the claimed contradiction to OMv is not established.","section":"Section 7, Theorem 4"},{"comment":"The proof of the truss maintenance unboundedness is a one-paragraph sketch and inherits the same gap as Theorem 4. The sentence 'while the circuit value of C_M is 0, only a constant number of edges change their truss value whenever a wire is inserted or removed, because the 4-truss does not propagate from the 1-gate unless the circuit value is 1' is not justified. The 4-truss gadgets from Proposition 3 could in principle have partial propagation in intermediate states, and the bounded FTM algorithm's runtime guarantee would then fail. Theorem 5 needs its own invariant, or a reduction that transfers the Theorem 4 invariant to the truss setting.","section":"Section 7, Theorem 5"}],"minor_comments":[{"comment":"The final step says 'by Proposition 5 with ε=1'. Since Proposition 5 is stated for ε>0, ε=1 is admissible, but the sentence should make explicit that this yields c(N,Q)=O(NQ+N^2), which is the forbidden bound for ε=1. Alternatively, one can derive the contradiction directly by taking Q=N in the OMv conjecture.","section":"Section 4, proof of Theorem 4"},{"comment":"The proof chooses δ = min{(1−ε)/t, 0.49}, which requires ε<1. The statement quantifies over all ε>0. Please restrict to 0<ε<1 (the cases ε≥1 are subsumed by smaller ε) or explain the handling of large ε.","section":"Section 5, Theorem 2"},{"comment":"The claim that the reduction in Proposition 1 constitutes a polylog incremental reduction and hence gives P-hardness under IPL reductions is stated informally. Please make the mapping of 1-bit updates explicit, or cite a precise theorem from [30] showing that MCVP is IPL-complete, so the transitivity argument is clear.","section":"Section 3.1"},{"comment":"The proof of Lemma 4 is concise but correct. For the reader's convenience, please state explicitly that the first and last special vertices are with respect to the Euler tour of the tree rooted at u, and that the self-loop positions are used. The current wording can be misread when the tree has a single special vertex.","section":"Section 8, Lemma 4"}],"recommendation":"major_revision","confidential_remarks":"The paper's main conditional lower bounds and the 2-core algorithm are likely correct and significant. The outstanding issue is the missing invariant in Theorems 4 and 5: if the authors can supply a rigorous proof (or a modified construction that enforces it), the paper should be accepted. The referee report raises this as the sole load-bearing gap; the rest of the technical content appears sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this is the paper that finally gives conditional lower bounds for dynamic k-core and truss problems, and it includes a real positive result—a polylog algorithm for 2-core. The k=3 threshold is the main takeaway.\n\nWhat's genuinely new: the reductions from dynamic monotone circuit value to 3-core are explicit and the gadgets check out. The OMv and SETH applications are standard but executed cleanly. The connection to IPL (Miltersen et al.'s incremental polylog class) is a nice observation that deserves more attention. The 2-core algorithm using an Euler tour tree plus link-cut tree is elegant, implemented, and tested.\n\nThe real soft spot is Section 7. The unboundedness proof for core maintenance rests on an invariant the paper never states: if s* is not in the 3-core, then no other vertex is. The construction is designed to make this true—the modified 1-gate is an arrow whose input is s*, so the 3-core cannot spread without s*—but the proof never formalizes it. The stress-test note about an intermediate 3-core not containing s* does not actually land, because the arrow gadget would block it; but a referee should ask for a lemma. The 'stop the algorithm' step is also under-specified: the proof never says what happens if an insertion that moves s* still finishes within the budget, and the final query after all insertions is not described. The use of Proposition 5 with eps=1 sits at the boundary of the statement; probably fine, but it needs a justification. These are fixable gaps, not a broken core.\n\nThe truss and approximate lower bounds are more sketched, with figures doing work that should be formalized. Acceptable for a preprint, but they need more detail before publication. The abstract also overstates a bit: the bounds are conditional, and the OMv update bound still leaves a gap to the trivial O(m).\n\nOverall: the central claims—no polylog for k>=3, sharp threshold at 2, conditional hardness for truss and approximation—hold up. This is aimed at dynamic graph algorithm researchers and answers open questions from the Hanauer et al. survey. It deserves a serious referee. I'd send it to peer review, expecting Section 7 to be tightened.","headline":"Real conditional lower bounds for dynamic k-core/truss plus a clean polylog 2-core algorithm; Section 7 needs a formal invariant but the central results look right.","tokens_in":22669,"tokens_out":17454,"would_cite":true,"duration_ms":172956,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","68R10","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that dynamic k-core, its (2−ε)-approximate version, and k-truss decompositions have no polylogarithmic-time algorithm, and no bounded incremental maintenance algorithm, unless the OMv conjecture or SETH fails; for 2-core, i","keywords":["dynamic graph algorithms","k-core decomposition","core maintenance","truss decomposition","conditional lower bounds","OMv conjecture","SETH","circuit value problem"],"falsifier":"An O(N^{3−ε}) algorithm for OMv would falsify the OMv-based theorems; a single mismatch in the gate-gadget simulation on a toy circuit (e.g., one 1-gate feeding one OR-gate) would refute the reduction.","tokens_in":21765,"feed_emoji":"🕸️","tokens_out":8131,"duration_ms":91730,"temperature":0.7,"pith_summary":"The paper aims to settle open questions about dynamic graph algorithms for cohesive subgraphs. It claims that maintaining the k-core, the k-truss, or a (2−ε)-approximation of core values is inherently expensive: for every fixed k≥3, no algorithm with polylogarithmic update time exists, and under the OMv conjecture no algorithm with O(m^{1/2−ε}) update time exists, unless long-standing conjectures about matrix multiplication and SAT fail. The same machinery shows that called bounded core-maintenance algorithms, which are fast when few core values change, cannot exist in the RAM model under OMv. On the positive side, the paper gives a polylogarithmic dynamic algorithm for the 2-core, so the hardness begins exactly at k=3. A reader should care because these results explain why existing dynamic core algorithms are heuristic and open a clean threshold question between 2 and 3.","feed_headline":"No fast dynamic k-core unless OMv or SETH fails","feed_subtitle":"Even approximations, trusses, and maintenance hit the same barrier; only the 2-core case has a polylog algorithm.","key_machinery":"The load-bearing object is the constant-size 'arrow' gate gadget used in reductions from monotone circuits: an oriented two-vertex structure whose output vertex lies in the 3-core exactly when its input vertex does. Chaining these arrows inside AND/OR gate gadgets makes 3-core membership of the circuit-output vertex simulate the Boolean value of the circuit. For approximations, a generalized gadget forces core values 2k (circuit true) against k+1 (false), creating a gap any (2−ε)-approximation could detect. The positive algorithm instead maintains a spanning forest with Euler-tour trees and link-cut trees, using the characterization that a vertex is in the 2-core iff it has an extra edge or","core_discovery":"Central claim: dynamic k-core (and truss, directed, approximate) is as hard as the dynamic circuit value problem. The proof constructs, from any bounded monotone Boolean circuit C, a graph G_C with a vertex s* whose core value is at least 3 iff the circuit evaluates to 1; each gate becomes a constant-size gadget in which 3-core membership propagates exactly like Boolean values. Composition with reductions from OuMv and k-SAT yields OMv and SETH lower bounds, and composition with DynXor yields an unconditional cell-probe lower bound. A separate argument shows no bounded incremental maintenance algorithm under OMv, while an Euler-tour-tree and link-cut-tree based algorithm maintains 2-core mem","pith_inferences":["It is natural to extend the same gate-gadget construction to hypergraph cores or bipartite cores, which the paper hints may also be hard; that would generalize the dynamic barrier beyond ordinary graphs.","The parallel between P-hardness and dynamic hardness (via polylog incremental reductions) suggests a broader research program: problems that resist parallelization may tend to resist dynamization, providing a heuristic for predicting dynamic lower bounds.","The 2-core algorithm gives a concrete baseline for experiment: benchmark it against existing core-maintenance heuristics on dynamic networks with rare core-value changes; lower bounds predict a worst-case instance where current heuristics take linear time despite a tiny affected set.","The approximation gap between the lower bound (no 2−ε) and the known upper bound (4+ε) invites an attempt at a 2-approximation; the lower bounds suggest such an algorithm would need techniques different from the circuit-gadget reductions."],"forward_implications":["Dynamic core and truss decomposition are conditionally hard: no polylog algorithm and no O(m^{1/2−ε})-update algorithm under OMv; no O(m^{1−ε}) algorithm under SETH.","Approximating core values is not fundamentally easier: a (2−ε) approximation inherits the same lower bounds, so the known polylog (4+ε) approximation is near the lower-bound limit.","Existing core-maintenance heuristics cannot be turned into bounded algorithms in the RAM model: under OMv there are worst-case inputs where even an insertion changing no core value forces work proportional to the graph size.","The hardness transfers to the directed (k,l)-core and to k-truss for fixed k, so denser and directed cohesive-subgraph variants face the same dynamic barrier.","The 2-core is tractable with polylog updates, so the complexity threshold in the core hierarchy sits between k=2 and k=3.","The reductions imply that polylog dynamic k-core would dynamize every problem in P under polylog incremental reductions, making the barrier parallel to classical P-hardness."],"fun_headline_variants":["Dynamic k-core and truss are hard unless OMv or SETH fails","No fast dynamic core, truss, or approximations under OMv/SETH","Even bounded maintenance of k-core is impossible under OMv","Polylog dynamic algorithm only for 2-core, not k-core","Hardness for dynamic k-core, truss, and directed variants"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the OMv conjecture and SETH are true; without those conjectures, the lower bounds for dynamic k-core, truss, and approximation collapse, and the unconditional cell-probe bound depends on the existing DynXor lower bound.","fun_headline_variants_meta":{"raw":{"variants":["Dynamic k-core and truss are hard unless OMv or SETH fails","No fast dynamic core, truss, or approximations under OMv/SETH","Even bounded maintenance of k-core is impossible under OMv","Polylog dynamic algorithm only for 2-core, not k-core","Hardness for dynamic k-core, truss, and directed variants"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000268,"raw_usage":{"total_tokens":1479,"prompt_tokens":794,"completion_tokens":685,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":538,"completion_tokens_details":{"reasoning_tokens":591}},"tokens_in":538,"tokens_out":685,"duration_ms":7547,"temperature":1.0,"reasoning_tokens":591,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T16:25:28.441217+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"An O(N^{3−ε}) algorithm for OMv would falsify the OMv-based theorems; a single mismatch in the gate-gadget simulation on a toy circuit (e.g., one 1-gate feeding one OR-gate) would refute the reduction.","supporting_citations":[],"review_version":1}