pith. sign in

arxiv: 2606.26639 · v1 · pith:RCYGYN6Cnew · submitted 2026-06-25 · 💻 cs.DS · cs.DM· math.CO

Fast Enumeration of Minimal Removable Sets in Monotone Systems with Application to Core Collapse Analysis

Kan Shota , Kazuya Haraguchi This is my paper

Pith reviewed 2026-06-26 02:30 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.CO
keywords minimal removable setsmonotone systemsk-corescore collapseenumeration algorithmsgraph algorithmsnetwork vulnerability
0
0 comments X

The pith

Minimal removable sets of a k-core can be enumerated in O((n+m) log n) time once the system is shown to satisfy the in-dominating seed property.

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

The paper places the enumeration of minimal removable sets inside a general monotone-system framework defined on an underlying graph. It first gives an O((n+m)n τ_ω)-time algorithm that works for any monotone system. It then introduces the in-dominating seed property and proves that any system possessing the property admits an O((n+m) log n ⋅ τ_ω)-time enumeration algorithm. Because ordinary k-cores satisfy the property, the improved bound applies directly to the core-collapse problem, yielding an O((n+m) log n)-time method for listing every minimal vertex set whose removal shrinks the k-core. The same property also produces an O((n+m) log n)-delay algorithm for listing every possible k-core subgraph.

Core claim

For a monotone system on a graph that satisfies the in-dominating seed property, all minimal removable sets of any solution can be enumerated in O((n+m) log n ⋅ τ_ω) time. Standard k-cores satisfy the property, so their minimal removable sets can be listed in O((n+m) log n) time. The framework further yields an O((n+m) log n)-delay algorithm that enumerates every k-core subgraph of a given graph.

What carries the argument

The in-dominating seed property of a monotone system, which permits an ordering of candidate seeds that supports logarithmic-time removal checks and output-sensitive enumeration.

If this is right

  • MinRS enumeration for any k-core improves from quadratic to near-linear in the size of the graph.
  • All k-core subgraphs of a graph can be listed with O((n+m) log n) delay per solution.
  • The same bounds hold for weighted k-cores, multi-layer k-cores, and (k,ℓ)-cores.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The technique may extend to other degeneracy-based subgraphs such as densest subgraphs or truss decompositions that also admit monotone characterizations.
  • Practical network-analysis tools could use the algorithm to rank vertices by their potential to trigger large core collapses.
  • Directed or weighted variants of the in-dominating seed property could be defined and checked for other core-like structures.

Load-bearing premise

That every standard k-core satisfies the in-dominating seed property.

What would settle it

A concrete k-core on which the number of minimal removable sets cannot be listed within O((n+m) log n) total time, or an explicit counter-example graph whose k-core violates the in-dominating seed property.

Figures

Figures reproduced from arXiv: 2606.26639 by Kan Shota, Kazuya Haraguchi.

Figure 1
Figure 1. Figure 1: 3-cores of proper subgraphs of G inclusion-wise maximal induced subgraph such that the minimum degree is no less than k, where the k-core of G is unique [20]. We call G a k-core graph if the k-core of G is G itself (i.e., the minimum degree of G is no less than k). We regard a null graph as a k-core graph. The k-core of a graph G can be computed in linear time by a simple iterative proce￾dure [2] and has v… view at source ↗
Figure 2
Figure 2. Figure 2: A 1-SR digraph H = (B, F) for B = B⊥, where B pr S = {B1,1, B1,2, . . . , B5,1} is a set of 14 seeds. Each seed constitutes a singleton in B⊥ and corresponds to a seed-subset node indicated by a square. For i ∈ [1, 5], we denote by ρi the closure of a seed Bi,j ; e.g., ρ1 = ρ(B1,1) = · · · = ρ(B1,4). Among ρ1, . . . , ρ5, we assume ρ2 ⊊ ρ1 and ρ5 ⊊ ρ4 for the inclusion relationship, and hence ρ2, ρ3 and ρ5… view at source ↗
Figure 3
Figure 3. Figure 3: A 1-SR digraph H′ = (B[F], F′ ) that is constructed for the 1-SR digraph H = (B, F) in [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A counterexample such that the local monotone system based on weighted [PITH_FULL_IMAGE:figures/full_fig_p022_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A counterexample such that the local monotone system based on multi-layer [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗
read the original abstract

In network vulnerability analysis, it is crucial to evaluate the robustness of $k$-cores against vertex removals. A $k$-core is often fragile since removing a few vertices can trigger a large reduction in the core size, a phenomenon known as core collapse. In this paper, we study the problem of enumerating all minimal removable sets (MinRSs) of a given $k$-core, where a MinRS is a minimal nonempty set of vertices whose removal results in a smaller $k$-core graph. We consider this problem within a general mathematical framework based on monotone systems. We show that, for a monotone system that is given with an underlying graph $G=(V,E)$, all MinRSs of a solution can be enumerated in $O((n+m)n\tau_\omega)$ time, where $n=|V|$, $m=|E|$ and $\tau_\omega$ denotes the computation time of evaluating the monotone function of the system. Furthermore, if the system satisfies the newly defined in-dominating seed property, the complexity drops to $O((n+m) \log n \cdot \tau_\omega)$ time. We prove that standard $k$-cores in undirected graphs satisfy this property, enabling MinRS enumeration in $O((n+m)\log n)$ time, a significant improvement over the baseline. We also extend our framework to enumerate all solutions in a given monotone system. This yields an $O((n+m)\log n)$-delay algorithm for all $k$-core subgraphs, outperforming an algorithm given by [Boley et al., Theoretical Computer Science, 2010]. Our framework is applicable to various $k$-core extensions, including weighted $k$-cores, multi-layer $\boldsymbol{k}$-cores, and $(k,\ell)$-cores.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper develops a monotone-system framework for enumerating minimal removable sets (MinRSs) of solutions in graphs. It gives a general O((n+m)n τ_ω)-time algorithm and shows that the newly defined in-dominating seed property reduces the bound to O((n+m) log n · τ_ω). The authors prove that undirected k-cores satisfy the property, yielding an O((n+m) log n) MinRS algorithm; they also obtain an O((n+m) log n)-delay algorithm for enumerating all k-core subgraphs (improving Boley et al., TCS 2010) and extend the framework to weighted, multi-layer, and (k,ℓ)-cores.

Significance. If the stated proofs of the in-dominating seed property and the resulting complexity bounds are correct, the work supplies a substantial improvement over the naïve O((n+m)n τ_ω) baseline for MinRS enumeration in core-collapse analysis and a faster delay algorithm for listing all k-core subgraphs. The general monotone-system abstraction may be reusable for other graph problems whose deletion operators are monotone.

minor comments (2)
  1. [Abstract] The abstract states that proofs exist for the time bounds and the k-core property; the main text should explicitly locate these proofs (e.g., “Theorem 4.3” or “§5”) so readers can locate the derivations without searching.
  2. Notation for τ_ω is introduced in the abstract but should be restated once in the preliminaries section with a clear definition of the monotone function evaluation oracle.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, recognition of the significance of the monotone-system framework, and the recommendation for minor revision. The referee's description of the contributions matches our manuscript accurately.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation begins from the monotone-system framework, defines the in-dominating seed property, and supplies an explicit proof that undirected k-cores satisfy the property; the O((n+m) log n) bound then follows directly from substituting that property into the general enumeration algorithm. No step reduces a claimed result to a fitted parameter, a self-citation chain, or a definitional tautology; the cited prior work (Boley et al.) is used only for external comparison, not as load-bearing justification for the new property or complexity. The entire chain is therefore self-contained against external mathematical verification.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The framework rests on the standard definition of monotone systems and the newly introduced in-dominating seed property; no free parameters or invented entities are required.

axioms (2)
  • domain assumption A monotone system is given together with an underlying graph G=(V,E) on which the monotone function can be evaluated in time τ_ω.
    Invoked in the statement of the general enumeration result.
  • ad hoc to paper Standard k-cores satisfy the in-dominating seed property.
    This property is defined in the paper and asserted to hold for k-cores to obtain the improved bound.

pith-pipeline@v0.9.1-grok · 5870 in / 1285 out tokens · 62007 ms · 2026-06-26T02:30:08.583348+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 26 canonical work pages · 1 internal anchor

  1. [1]

    Batagelj and M

    V. Batagelj and M. Zaverˇ snik. Generalized cores.arXiv preprint arXiv:cs/0202039,

    Pith/arXiv arXiv

  2. [2]

    doi:10.48550/arXiv.cs/0202039

    work page doi:10.48550/arxiv.cs/0202039

  3. [3]

    Batagelj and M

    V. Batagelj and M. Zaverˇ snik. AnO(m) algorithm for cores decomposition of net- works.arXiv preprint, 2003. doi:10.48550/arXiv.cs/0310049

    work page doi:10.48550/arxiv.cs/0310049 2003

  4. [4]

    Batagelj and M

    V. Batagelj and M. Zaverˇ snik. Fast algorithms for determining (generalized) core groups in social networks.Advances in Data Analysis and Classification, 5(2):129– 145, 2011. doi:10.1007/s11634-010-0079-y

    work page doi:10.1007/s11634-010-0079-y 2011

  5. [5]

    G. J. Baxter, S. N. Dorogovtsev, K.-E. Lee, J. F. F. Mendes, and A. V. Goltsev. Critical dynamics of thek-core pruning process.Physical Review X, 5(3):031017,

  6. [6]

    doi:10.1103/PhysRevX.5.031017

    work page doi:10.1103/physrevx.5.031017

  7. [7]

    Boley, T

    M. Boley, T. Horv´ ath, A. Poign´ e, and S. Wrobel. Listing closed sets of strongly ac- cessible set systems with applications to data mining.Theoretical Computer Science, 411:691–700, 2010. doi:10.1016/j.tcs.2009.10.024

    work page doi:10.1016/j.tcs.2009.10.024 2010

  8. [8]

    Cerulli, D

    M. Cerulli, D. Serra, C. Sorgente, C. Archetti, and I. Ljubi´ c. Mathematical program- ming formulations for the collapsedk-core problem.European Journal of Operational Research, 311(1):56–72, 2023. doi:10.1016/j.ejor.2023.04.038

    work page doi:10.1016/j.ejor.2023.04.038 2023

  9. [9]

    A. I. Emerson, S. Andrews, I. Ahmed, T. Azis, and J. A. Malek. K-core decomposition of a protein domain co-occurrence network reveals lower cancer mutation rates for interior cores.Journal of Clinical Bioinformatics, 5(1):1, 2015. ISSN 2043-9113. doi:10.1186/s13336-015-0016-6

    work page doi:10.1186/s13336-015-0016-6 2015

  10. [10]

    K. T. Ferdous, S. Balasubramanian, V. Srinivasan, and A. Thomo. Brain network similarity using k-cores. InProceedings of the 2023 IEEE/ACM International Con- ference on Advances in Social Networks Analysis and Mining, ASONAM ’23, pages 575–582, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400704093. doi:10.1145/3625007.3627318

    work page doi:10.1145/3625007.3627318 2023

  11. [11]

    Galimberti, F

    E. Galimberti, F. Bonchi, and F. Gullo. Core decomposition and densest subgraph in multilayer networks. InProceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM ’17, pages 1807–1816, New York, NY, USA, Nov

    2017

  12. [12]

    doi:10.1145/3132847.3132993

    ACM. doi:10.1145/3132847.3132993

    work page doi:10.1145/3132847.3132993

  13. [13]

    Garas, F

    A. Garas, F. Schweitzer, and S. Havlin. Ak-shell decomposition method for weighted networks.New Journal of Physics, 14(8):083030, Aug 2012. ISSN 1367-2630. doi:10.1088/1367-2630/14/8/083030. 26

    work page doi:10.1088/1367-2630/14/8/083030 2012

  14. [14]

    Giatsidis, D

    C. Giatsidis, D. M. Thilikos, and M. Vazirgiannis. D-cores: measuring collaboration of directed graphs based on degeneracy.Knowledge and Information Systems, 35: 311–343, 2013. doi:10.1007/s10115-012-0539-0

    work page doi:10.1007/s10115-012-0539-0 2013

  15. [15]

    A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes.k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects.Physical Review E, 73(5):056101, 2006. doi:10.1103/PhysRevE.73.056101

    work page doi:10.1103/physreve.73.056101 2006

  16. [16]

    Honcharov, A

    D. Honcharov, A. E. Sarıy¨ uce, R. Laishram, and S. Soundarajan. Skeletal cores and graph resilience. InMachine Learning and Knowledge Discovery in Databases: Research Track, volume 14171 ofLecture Notes in Computer Science, pages 293–308. Springer, 2023. doi:10.1007/978-3-031-43418-1 18

    work page doi:10.1007/978-3-031-43418-1 2023

  17. [17]

    A. E. Isaac and S. Sinha. Analysis of core–periphery organization in protein contact networks reveals groups of structurally and functionally critical residues.Journal of Biosciences, 40(4):683–699, Oct 2015. ISSN 0250-5991. doi:10.1007/s12038-015-9554- 0

    work page doi:10.1007/s12038-015-9554- 2015

  18. [18]

    D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou. On generating all maximal independent sets.Information Processing Letters, 27(3):119–123, 1988. ISSN 0020-

    1988

  19. [19]

    doi:10.1016/0020-0190(88)90065-8

    work page doi:10.1016/0020-0190(88)90065-8

  20. [20]

    J. Luo, H. Molter, and O. Such´ y. A parameterized complexity view on collapsing k-cores.Theory of Computing Systems, 65(8):1243–1282, 2021. doi:10.1007/s00224- 021-10045-w

    work page doi:10.1007/s00224- 2021

  21. [21]

    Y. Lv, B. Zhou, J. Wang, and Q. Xuan. Targetedk-node collapse problem: To- wards understanding the robustness of localk-core structure.Physica A: Statistical Mechanics and its Applications, 641:129732, 2024. doi:10.1016/j.physa.2024.129732

    work page doi:10.1016/j.physa.2024.129732 2024

  22. [22]

    Y. Lv, B. Zhou, J. Wang, S. Yu, and Q. Xuan. MONA: An efficient and scalable strategy for targetedk-nodes collapse.IEEE Transactions on Circuits and Systems II: Express Briefs, 71(6):3106–3110, 2024. doi:10.1109/TCSII.2024.3357102

    work page doi:10.1109/tcsii.2024.3357102 2024

  23. [23]

    F. D. Malliaros, C. Giatsidis, A. N. Papadopoulos, and M. Vazirgiannis. The core decomposition of networks: Theory, algorithms and applications.The VLDB Journal, 29(1):61–92, 2020. doi:10.1007/s00778-019-00587-4

    work page doi:10.1007/s00778-019-00587-4 2020

  24. [24]

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

    work page doi:10.1016/0378-8733(83)90028-x 1983

  25. [25]

    K. Shin, T. Eliassi-Rad, and C. Faloutsos. Patterns and anomalies ink-cores of real- world graphs with applications.Knowledge and Information Systems, 54(3):677–710, Mar 2018. ISSN 0219-1377. doi:10.1007/s10115-017-1077-6. 27

    work page doi:10.1007/s10115-017-1077-6 2018

  26. [26]

    Tada and K

    T. Tada and K. Haraguchi. A linear delay algorithm in SD set system and its ap- plication to subgraph enumeration.Journal of Computer and System Sciences, 152: 103637, 2025. doi:10.1016/j.jcss.2025.103637

    work page doi:10.1016/j.jcss.2025.103637 2025

  27. [27]

    M. Tang, W. Lei, and S. Lian. A k-core analysis to large-scale web API collaboration networks. In2020 International Conference on Service Science (ICSS), pages 90–95,

  28. [28]

    doi:10.1109/ICSS50103.2020.00022

    work page doi:10.1109/icss50103.2020.00022 2020

  29. [29]

    The Anatomy of the Facebook Social Graph

    J. Ugander, B. Karrer, L. Backstrom, and C. Marlow. The anatomy of the Facebook social graph.arXiv preprint, Nov 2011. doi:10.48550/arXiv.1111.4503

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1111.4503 2011

  30. [30]

    Zhang, Y

    F. Zhang, Y. Zhang, L. Qin, W. Zhang, and X. Lin. Finding critical users for social network engagement: The collapsedk-core problem. InProceedings of the Thirty- First AAAI Conference on Artificial Intelligence, pages 245–251. AAAI Press, 2017. doi:10.1609/aaai.v31i1.10482

    work page doi:10.1609/aaai.v31i1.10482 2017

  31. [31]

    B. Zhou, Y. Lv, J. Wang, J. Zhang, and Q. Xuan. Attacking the core structure of complex network.IEEE Transactions on Computational Social Systems, 10(4): 1428–1442, 2023. doi:10.1109/TCSS.2022.3188522. 28

    work page doi:10.1109/tcss.2022.3188522 2023