Pith. sign in

REVIEW 2 major objections 4 minor 48 references

Hardness of Dynamic Core and Truss Decompositions

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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

desk verdict 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. read the letter →

arxiv 2509.13584 v2 pith:FCZGSBSK submitted 2025-09-16 cs.DS cs.CC

Yan S. Couto , Cristina G. Fernandes This is my paper · ORCID
classification cs.DScs.CC MSC 68Q1768Q2568R1068W40
keywords dynamicgraphalgorithmsk-coredecompositioncoremaintenancetrussconditionallowerboundsOMvconjectureSETHcircuitvalueproblem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [Section 7, Theorem 4] 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.
  2. [Section 7, Theorem 5] 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.
minor comments (4)
  1. [Section 4, proof of Theorem 4] 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.
  2. [Section 5, Theorem 2] 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 ε.
  3. [Section 3.1] 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.
  4. [Section 8, Lemma 4] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: reductions are self-contained and anchored in external conjectures; only a non-load-bearing self-citation of the authors' own code appears.

full rationale

The paper's derivation chain is not circular. The lower bounds are conditional reductions from dynamic MCVP to k-core, k-truss, approximate core, and directed core, then composed with the external OMv and SETH conjectures. Proposition 1 constructs graph GC from a circuit C with an explicit correctness argument via gate gadgets; Propositions 2-4 give analogous self-contained gadget reductions. Proposition 6 reduces OuMv to MCVP using a standard witness-path construction, and Theorem 1 invokes the external Proposition 5 (Henzinger et al. theorem) as the hardness anchor. Similarly, the SETH chain uses the external Sparsification Lemma, and the cell-probe chain uses the external Fredman-Saks DynXor lower bound. These are independent, externally stated results with stated assumptions, not self-citations. The positive 2-core algorithm is a new constructive result proved from Lemmas 3 and 4 using ETT/LCT/HDT data structures; it is code-reproduced, not a renaming or repackaging of the conjectures. The only self-citation is a reference to the authors' own implementation [41], which is not load-bearing. The review flags two substantive correctness risks in Section 7, but they are not circularity: the proof of Theorem 4 asserts without proof that if s* does not change core value then no core value changes, and asserts 'In fact, this subgraph is exactly the 3-core of GM(u,v)' without proving the invariant for intermediate graphs; the final use of 'Proposition 5 with epsilon=1' is also a boundary case. These are potential gaps in the reduction, not definitional equivalence, fitted-input prediction, or self-citation chains. Accordingly, circularity score is 1 (essentially none, with a minor self-citation that does not affect the central claims).

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

No new particles or forces. The axioms are standard computational hardness conjectures and data structure primitives; the only free parameter is the delta split in the SETH reduction, which is not fitted to data but is a choice in the proof. The reductions and the 2-core algorithm are the actual contributions.

free parameters (1)
  • split parameter delta in SETH reduction = delta = min((1-eps)/t, 0.49)
    In Theorem 2, delta is chosen by the authors to balance terms in the SETH reduction; it depends on the unspecified polynomial exponent t of the hypothetical algorithm, so it is not a fixed constant of the problem.
assumptions (5)
  • domain assumption OMv conjecture (Conjecture 1) and the OuMv equivalence from Henzinger et al. [18]
    All the OMv lower bounds rest on this conjecture; it is explicitly labeled as a conjecture in Section 4.
  • domain assumption SETH (Conjecture 2) and the sparsification lemma for k-SAT with O(N) clauses
    The SETH lower bounds rely on this conjecture and on the sparsification lemma from Impagliazzo et al.; cited in Section 5.
  • standard math Fredman-Saks DynXor lower bound (Lemma 2) in the cell probe model
    Section 6 uses the known lower bound that DynXor requires o(log n / log log n) time per operation; this is a cited lemma from [10].
  • domain assumption Existence of dynamic connectivity algorithm HDT (Holm et al.)
    The 2-core algorithm in Section 8 relies on the HDT data structure for maintaining a spanning forest under edge insertions/deletions.
  • standard math Euler tour tree and link-cut tree operations are correct and maintain the needed queries
    Section 8.2 uses standard ETT and LCT data structures; the paper cites standard references and provides the algorithmic logic.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hardness of Dynamic Core and Truss Decompositions." pith.science (2026). https://pith.science/paper/FCZGSBSK

@misc{pith2026250913584,
  author       = {Pith},
  title        = {Pith review of: Hardness of Dynamic Core and Truss Decompositions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FCZGSBSK}},
  note         = {Machine review of arXiv:2509.13584}
}
read the original abstract

The k-core of a graph is its maximal subgraph with minimum degree at least k, and the core value of a vertex u is the largest k for which u is contained in the k-core of the graph. Among cohesive subgraphs, k-core and its variants have received a lot of attention recently, particularly on dynamic graphs, as reported by Hanauer, Henzinger, and Schulz in their recent survey on dynamic graph algorithms. We answer questions on k-core stated in the survey, proving that there is no efficient dynamic algorithm for k-core or to find (2 - {\epsilon})-approximations for the core values, unless we can improve decade-long state-of-the-art algorithms in many areas including matrix multiplication and satisfiability, based on the established OMv and SETH conjectures. Some of our results show that there is no dynamic algorithm for k-core asymptotically faster than the trivial ones. This explains why most recent research papers in this area focus not on a generic efficient dynamic algorithm, but on finding a bounded algorithm, which is fast when few core values change per update. However, we also prove that such bounded algorithms do not exist, based on the OMv conjecture. We present lower bounds also for a directed version of the problem, and for the edge variant of the problem, known as k-truss. On the positive side, we present a polylogarithmic dynamic algorithm for 2-core.

Figures

Figures reproduced from arXiv: 2509.13584 by the authors.

Figure 1
Figure 1. Building blocks of the reduction from MCVP to 3-core. Input edges are red and output edges are blue. Input vertices either do not exist or are output vertices of other gates. Proof. Let us consider the case k = 3. Given a circuit C with output gate g ∗ , we will describe a graph GC with a vertex s ∗ such that Ks∗ ≥ 3 if and only if the circuit value is 1. Each 0-gate in C corresponds to a vertex in GC , and each 1-g… view at source ↗
Figure 2
Figure 2. Building blocks of the reduction from MCVP to (2 − ϵ)- ApproxCoreValue for k = 3. Input edges are red and output edges are blue. not propagate and s ∗ is not in the (k + 2)-core. This proves the correctness of the reduction. If C has size N, then GC will have O(N k3 ) = O(N) vertices and edges. Each update in C corresponds to O(k 2 ) = O(1) updates in GC and each query in C corresponds to a single query in GC . So M… view at source ↗
Figure 3
Figure 3. Building blocks of the reduction from MCVP to 4-truss, βi is the value of gate i. Dashed red edges represent the wires ji and ki. Double edges are actually a K4, from which we are using a single edge. With this reduction, each edge Oi is in the 4-truss iff the value of gate i is 1. 3.4 Directed core decomposition Giatsidis et al. [12] extended the notion of k-cores to directed graphs. The (k, l)- core of a directed … view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Building blocks of the reduction from MCVP to (0, 2)-core. 4 OMV-based lower bounds In the OMv problem for “online” N × N Boolean matrix multiplication, one is given the first matrix, and then the columns of the second matrix one at a time. The first matrix may be prep…
Figure 5
Figure 5. Figure 5: (a) Simulating an AND-gate with in-degree 7 and out-degree 5. (b) Sketch of CM(u, v), omitting binary trees that simulate unbounded in- and out-degree. In this section, we use the OMv conjecture to prove lower bounds for MCVP and thus CoreValue. We start by arguing tha…
Figure 6
Figure 6. Figure 6: Reduction from k-SAT to MCVP on stage v, omitting binary trees used to simulate unbounded in- and out-degree. time since δ < 1 2 , finishing the proof for this case. For the incremental case of MCVP, build C U F normally and, for each v, build C U F (v) keeping track o…
Figure 7
Figure 7. Figure 7: Wiring gates in CX depending on the value of xi . Proposition 8. If fully dynamic MCVP on a circuit of size N can be solved in ⟨p(N), u(N), q(N)⟩ time, then DynXor on a vector of size n can be solved with O(u(n)) time per update and O(u(n) + q(n)) time per query. Proof…
Figure 8
Figure 8. Figure 8: Example that proves the unboundedness of some core maintenance algo [PITH_FULL_IMAGE:figures/full_fig_p021_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 7 canonical work pages

  1. [1]

    In: IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS)

    Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS). pp. 434–443 (2014). https://doi.org/10.1109/FOCS.2014.53

    doi:10.1109/focs.2014.53 2014

  2. [2]

    Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems (2014), http://arxiv.org/abs/1402.0054

    arXiv 2014

  3. [3]

    Anderson, R., Mayr, E.W.: A P-complete problem and approximations to it. Tech. rep., Stanford University (1984)

    1984

  4. [4]

    Batagelj, V., Zaveršnik, M.: AnO(m) algorithm for cores decomposition of net- works (2003), http://arxiv.org/abs/cs/0310049

    arXiv 2003

  5. [5]

    National secu- rity agency technical report16(3.1), 1–29 (2008)

    Cohen, J.: Trusses: Cohesive subgraphs for social network analysis. National secu- rity agency technical report16(3.1), 1–29 (2008)

    2008

  6. [6]

    In: Introduc- tion to algorithms, pp

    Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: RAM model. In: Introduc- tion to algorithms, pp. 25–26. Fourth edn. (2022)

    2022

  7. [7]

    ACM Trans

    Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlström, M.: On problems as hard as CNF-SAT. ACM Trans. Algorithms12(3), 1–24 (2016). https://doi.org/10.1145/2925416

    doi:10.1145/2925416 2016

  8. [8]

    Demaine, E.: Lecture Notes: Link-Cut Trees (2012), https://courses.csail.mit.edu/ 6.851/spring12/scribe/L19.pdf, MIT, Advanced Data Structures (Spring’12)

    2012

Show all 48 references
  1. [9]

    IEEE Trans

    Fang, Y., Wang, Z., Cheng, R., Wang, H., Hu, J.: Effective and efficient community search over large directed graphs. IEEE Trans. Knowl. Data Eng.31(11), 2093– 2107 (2019). https://doi.org/10.1109/TKDE.2018.2872982

  2. [10]

    In: 21st Annual ACM Symposium on Theory of Computing (STOC)

    Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. In: 21st Annual ACM Symposium on Theory of Computing (STOC). pp. 345–354 (1989). https://doi.org/10.1145/73007.73040

    1989

  3. [11]

    In: 5th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)

    Gabert, K., Pinar, A., Çatalyürek, U.V.: Batch dynamic algorithm to findk-core hierarchies. In: 5th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA). pp. 1–10 (2022). https://doi.org/10.1145/353454...

    2022

  4. [12]

    In: IEEE 11th International Conference on Data Mining (ICDM)

    Giatsidis, C., Thilikos, D.M., Vazirgiannis, M.: D-cores: measuring collaboration of directed graphs based on degeneracy. In: IEEE 11th International Conference on Data Mining (ICDM). pp. 201–210 (2011). https://doi.org/10.1109/ICDM.2011.46 26 Y.S. Couto and C.G. Fernandes

    2011 doi

  5. [13]

    Oxford University Press (1995)

    Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P- Completeness Theory. Oxford University Press (1995)

    1995

  6. [14]

    In: 52nd International Conference on Parallel Processing (ICPP)

    Guo, B., Sekerinski, E.: Parallel order-based core maintenance in dynamic graphs. In: 52nd International Conference on Parallel Processing (ICPP). pp. 122–131 (2023). https://doi.org/10.1145/3605573.3605597

    2023

  7. [15]

    Guo, B., Sekerinski, E.: Simplified algorithms for order-based core mainte- nance. J. Supercomputing80(13), 19592–19623 (2024). https://doi.org/10.1007/ s11227-024-06190-x

    2024

  8. [16]

    Hanauer, K., Henzinger, M.R., Schulz, C.: Recent advances in fully dynamic graph algorithms – a quick reference guide. ACM J. Exp. Algorithmics27, 1–45 (2022). https://doi.org/10.1145/3555806

    2022 doi

  9. [17]

    Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with poly- logarithmic time per operation. J. ACM46(4), 502–516 (1999). https://doi.org/ 10.1145/320211.320215

    1999

  10. [18]

    In: 47th Annual ACM Symposium on Theory of Computing (STOC)

    Henzinger, M.R., Krinninger, S., Nanongkai, D., Saranurak, T.: Unifying and strengthening hardness for dynamic problems via the Online Matrix-Vector Multi- plication Conjecture. In: 47th Annual ACM Symposium on Theory of Computing (STOC). pp. 21–30 (2015). https://doi.org/10.1...

    2015

  11. [19]

    In: 30th Annual ACM Symposium on Theory of Computing (STOC)

    Holm, J., De Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully- dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and bicon- nectivity. In: 30th Annual ACM Symposium on Theory of Computing (STOC). pp. 79–89 (1998). https://doi.org/10.1145/2766...

    1998

  12. [20]

    In: 2017 ACM on Conference on Information and Knowledge Man- agement (CIKM)

    Hu, S., Wu, X., Chan, T.H.H.: Maintaining densest subsets efficiently in evolving hypergraphs. In: 2017 ACM on Conference on Information and Knowledge Man- agement (CIKM). pp. 929–938 (2017). https://doi.org/10.1145/3132847.3132907

    2017

  13. [21]

    Synthesis Lectures on Data Management (2019)

    Huang, X., Lakshmanan, L.V.S., Xu, J.: Community Search over Big Graphs. Synthesis Lectures on Data Management (2019). https://doi.org/10.1007/ 978-3-031-01874-9

    2019

  14. [22]

    Acta Math.182(1), 105–142 (1999)

    Håstad, J.: Clique is hard to approximate withinn1−ϵ. Acta Math.182(1), 105–142 (1999). https://doi.org/10.1007/BF02392825

    1999 doi

  15. [23]

    Journal of Computer and System Sciences62(2), 367–375 (2001)

    Impagliazzo, R., Paturi, R.: On the complexity ofk-SAT. Journal of Computer and System Sciences62(2), 367–375 (2001). https://doi.org/10.1006/jcss.2000.1727

    2001

  16. [24]

    https://doi.org/10.1006/jcss.2001.1774

    Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences63(4), 512–530 (2001). https://doi.org/10.1006/jcss.2001.1774

    2001

  17. [25]

    In: Optimization Algorithms for Planar Graphs, pp

    Klein, P., Shay, M.: Chapter 18: Splay trees and link-cut trees. In: Optimization Algorithms for Planar Graphs, pp. 249–280 (2021), https://planarity.org/Klein_ splay_trees_and_link-cut_trees.pdf

    2021

  18. [26]

    IEEE Trans

    Li, R.H., Yu, J.X., Mao, R.: Efficient core maintenance in large dynamic graphs. IEEE Trans. Knowl. Data Eng.26(10), 2453–2465 (2014). https://doi.org/10. 1109/TKDE.2013.158

    2014

  19. [27]

    The VLDB Journal29(5), 1075–1099 (2020)

    Liu, B., Yuan, L., Lin, X., Qin, L., Zhang, W., Zhou, J.: Efficient (α,β)-core computation in bipartite graphs. The VLDB Journal29(5), 1075–1099 (2020). https://doi.org/10.1007/s00778-020-00606-9

    2020 doi

  20. [28]

    In: 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    Liu,Q.C.,Shi,J.,Yu,S.,Dhulipala,L.,Shun,J.:Parallelbatch-dynamicalgorithms fork-core decomposition and related graph problems. In: 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). pp. 191–204 (2022). https: //doi.org/10.1145/3490148.3538569

    2022

  21. [29]

    The VLDB Journal 29(1), 61–92 (2020)

    Malliaros, F.D., Giatsidis, C., Papadopoulos, A.N., Vazirgiannis, M.: The core de- composition of networks: theory, algorithms and applications. The VLDB Journal 29(1), 61–92 (2020). https://doi.org/10.1007/s00778-019-00587-4 Hardness of Dynamic Core and Truss Decompositions 27

    2020 doi

  22. [30]

    Theoretical Computer Science130(1), 203–236 (1994)

    Miltersen,P.B.,Subramanian,S.,Vitter,J.S.,Tamassia,R.:Complexitymodelsfor incremental computation. Theoretical Computer Science130(1), 203–236 (1994). https://doi.org/10.1016/0304-3975(94)90159-7

    1994 doi

  23. [31]

    PhD Thesis, Mas- sachusetts Institute of Technology (2008)

    Pătraşcu, M.: Lower bound techniques for data structures. PhD Thesis, Mas- sachusetts Institute of Technology (2008)

    2008

  24. [32]

    In: 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

    Pătraşcu, M., Williams, R.: On the possibility of faster SAT algorithms. In: 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 1065–1075 (2010). https://doi.org/10.1137/1.9781611973075.86

    2010 doi

  25. [33]

    In: Sixth IEEE International Conference on Data Mining - Work- shops (ICDMW’06)

    Saito, K., Yamada, T.: Extracting communities from complex networks by the k-dense method. In: Sixth IEEE International Conference on Data Mining - Work- shops (ICDMW’06). pp. 300–304 (2006). https://doi.org/10.1109/ICDMW.2006. 76

    2006 doi

  26. [34]

    The VLDB Journal 25(3), 425–447 (2016)

    Sarıyüce, A.E., Gedik, B., Jacques-Silva, G., Wu, K.L., Çatalyürek, U.V.: In- crementalk-core decomposition: algorithms and evaluation. The VLDB Journal 25(3), 425–447 (2016). https://doi.org/10.1007/s00778-016-0423-8

    2016 doi

  27. [35]

    Schwarz, K.: Lecture Notes: Euler Tour Trees (2023), https://web.stanford.edu/ class/cs166/lectures/15/Small15.pdf, Stanford, CS166, Class 15

    2023

  28. [36]

    Social Networks5(3), 269–287 (1983)

    Seidman, S.B.: Network structure and minimum degree. Social Networks5(3), 269–287 (1983). https://doi.org/10.1016/0378-8733(83)90028-X

    1983 doi

  29. [37]

    In: 13th Annual ACM Symposium on Theory of Computing (STOC)

    Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. In: 13th Annual ACM Symposium on Theory of Computing (STOC). pp. 114–122 (1981). https: //doi.org/10.1145/800076.802464

    1981

  30. [38]

    ACM Trans

    Sun,B.,Chan,T.H.H.,Sozio,M.:Fullydynamicapproximatek-coredecomposition in hypergraphs. ACM Trans. Knowl. Discov. Data14(4), 39:1–39:21 (2020). https: //doi.org/10.1145/3385416

    2020 doi

  31. [39]

    Tian, A., Zhou, A., Wang, Y., Chen, L.: Maximal D-truss search in dynamic di- rected graphs. Proc. VLDB Endow.16(9), 2199–2211 (2023). https://doi.org/10. 14778/3598581.3598592

    2023

  32. [40]

    Wang, J., Cheng, J.: Truss decomposition in massive networks. Proc. VLDB En- dow.5(9), 812–823 (2012). https://doi.org/10.14778/2311906.2311909

    2012

  33. [41]

    Yan Soares Couto: Dynamic 2-core (2024), https://github.com/yancouto/phd/ tree/main/dynamic_2core

    2024

  34. [42]

    ACM28(3), 615–628 (1981)

    Yao, A.C.C.: Should tables be sorted? J. ACM28(3), 615–628 (1981). https://doi. org/10.1145/322261.322274

    1981

  35. [43]

    Yufan You: Maintain subtree information using link/cut trees (2019), https:// codeforces.com/blog/entry/67637

    2019

  36. [44]

    In: Du, D.Z., Wang, J

    Zhang, F., Liu, B., Fang, Q.: Core decomposition, maintenance and applications. In: Du, D.Z., Wang, J. (eds.) Complexity and Approximation, vol. 12000, pp. 205– 218 (2020). https://doi.org/10.1007/978-3-030-41672-0_12

    2020 doi

  37. [45]

    Theoretical Computer Science941, 140–155 (2023)

    Zhang, F., Liu, B., Liu, Z., Fang, Q.: Order based algorithms for the core main- tenance problem on edge-weighted graphs. Theoretical Computer Science941, 140–155 (2023). https://doi.org/10.1016/j.tcs.2022.11.008

    2023 doi

  38. [46]

    In: 2019 International Conference on Management of Data (SIGMOD)

    Zhang,Y.,Yu,J.X.:Unboundednessandefficiencyoftrussmaintenanceinevolving graphs. In: 2019 International Conference on Management of Data (SIGMOD). pp. 1024–1041 (2019). https://doi.org/10.1145/3299869.3300082

    2019

  39. [47]

    In: IEEE 33rd International Conference on Data Engineering (ICDE)

    Zhang, Y., Yu, J.X., Zhang, Y., Qin, L.: A fast order-based approach for core main- tenance. In: IEEE 33rd International Conference on Data Engineering (ICDE). pp. 337–348 (2017). https://doi.org/10.1109/ICDE.2017.93

    2017 doi

  40. [48]

    IEEE Transactions on Knowledge and Data Engineering36(9), 4766–4780 (2024)

    Zhang,Y., Yu,J.X., Zhang, Y., Qin, L.: Maintaining top-tcores in dynamicgraphs. IEEE Transactions on Knowledge and Data Engineering36(9), 4766–4780 (2024). https://doi.org/10.1109/TKDE.2023.3332638

    2024

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.