arxiv: 2602.19328 · v2 · submitted 2026-02-22 · 💻 cs.DS · cs.CC

Recognition: 1 theorem link

· Lean Theorem

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)

Bhaskar DasGupta , Katie Kruzan

Authors on Pith no claims yet

Pith reviewed 2026-05-15 20:30 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords Ollivier-Ricci curvaturecritical edgesgraph algorithmscomputational complexitynetwork vulnerabilityperfect matchingedge detection

0 comments

The pith

Ollivier-Ricci curvature changes identify critical edges in undirected graphs, with detection problems shown to be algorithmically hard and linked to perfect matching tasks.

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

The paper introduces a formal framework for locating critical edges in an undirected graph by tracking how much the Ollivier-Ricci curvature of the graph changes after each possible edge removal. It supplies both polynomial-time algorithms for some versions of the detection task and inapproximability results for others. The hardness proofs establish direct connections to the exact perfect matching problem, the perfect matching blocker problem on bipartite graphs, and standard combinatorial packing and covering problems. A reader would care because the framework turns a geometric notion of network shape into a set of well-defined algorithmic questions whose complexity can now be analyzed with existing tools from matching theory.

Core claim

The paper defines critical edges as those whose removal produces the largest shifts in Ollivier-Ricci curvature and studies the computational complexity of identifying them. It shows that certain curvature-based detection problems are solvable in polynomial time while others are NP-hard to approximate, with explicit reductions that relate them to exact perfect matching and to blocker problems for perfect matchings.

What carries the argument

Ollivier-Ricci curvature on undirected graphs, used as a difference measure that quantifies the structural effect of deleting a single edge.

If this is right

Some curvature-based critical-edge problems admit exact polynomial-time solutions.
Other versions are inapproximable within certain factors unless P equals NP.
The problems reduce to or from exact perfect matching and perfect-matching blocker problems on bipartite graphs.
Results transfer to related packing and covering problems via the established reductions.

Where Pith is reading between the lines

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

The framework could be applied to real-world networks to rank edges by vulnerability without enumerating all removals.
If the curvature measure correlates with empirical failure impact, it would give a parameter-free way to prioritize maintenance in transportation or communication graphs.
Testing the ranking against betweenness or degree centrality on the same graphs would show whether curvature adds new information beyond degree-based heuristics.

Load-bearing premise

That the size of the curvature change after an edge is removed reliably signals how much that edge matters to the overall network structure.

What would settle it

A small graph in which the edge whose removal produces the smallest curvature change turns out to disconnect the graph or increase its diameter more than an edge with a larger curvature change.

Figures

Figures reproduced from arXiv: 2602.19328 by Bhaskar DasGupta, Katie Kruzan.

**Figure 1.** Figure 1: LP-formulation for EMD on the set of nodes Vu and Vv with |V1| × |V2| variables. Comments are enclosed by (* and *). The value of the objective function corresponding to a valid (not necessarily optimal) solution ⃗z = {zv1,v2 | v1 ∈ Vu, v2 ∈ Vv} that satisfy all the constraints is denoted by TRANSPORT-COSTG(⃗z, Vu, Vv, Pu, Pv) (thus, EMDG(Vu, Vv, Pu, Pv) = min⃗z { TRANSPORT-COSTG(⃗z, Vu, Vv, Pu, Pv)}). 2.2… view at source ↗

read the original abstract

In recent years extensions of manifold Ricci curvature to discrete combinatorial objects such as graphs and hypergraphs (popularly called as "network shapes"), have found a plethora of applications in a wide spectrum of research areas ranging over metabolic systems, transcriptional regulatory networks, protein-protein-interaction networks, social networks and brain networks to deep learning models but, in contrast, they have been looked at by relatively fewer researchers in the algorithms and computational complexity community. As an attempt to bring these network Ricci-curvature related problems under the lens of computational complexity and foster further inter-disciplinary interactions, we provide a formal framework for studying algorithmic and computational complexity issues for detecting critical edges in an undirected graph using Ollivier-Ricci curvatures and provide several algorithmic and inapproximability results for problems in this framework. Our results show some interesting connections between our problems, the exact perfect matching and perfect matching blocker problems for bipartite graphs and two well-known combinatorial packing/covering problems.

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.

Desk Editor's Note private letter to a colleague

The paper defines problems for edges that shift Ollivier-Ricci curvature a lot when removed, then classifies them via reductions to perfect matching blocker and packing problems.

read the letter

The paper sets up problems for detecting edges whose removal causes significant shifts in Ollivier-Ricci curvature and then derives algorithmic and inapproximability results through reductions to exact perfect matching and perfect matching blocker problems, along with some packing problems. What is new here is the formal complexity framework around these curvature-driven problems. Prior work on network Ricci curvature has mostly focused on applications in biology and social networks, so bringing explicit algorithmic questions and hardness results to the table is a fresh angle. The reductions give the claims a direct tie to established combinatorial results. The paper does well in spelling out how the curvature change problems map onto the matching blocker and packing settings. Those links are specific enough to support both positive and negative results without loose ends. The soft spots are in the motivation and the lack of grounding. The definition of criticality is tied entirely to curvature deltas, but the paper does not show why this captures structural importance better than simpler measures like degree or betweenness. Because the results are complexity classifications of the defined problems, this does not invalidate them, but it does make the work feel somewhat self-contained. There are no small examples or discussions of how these problems behave on typical graphs, which would help readers see the point. This is for complexity researchers interested in geometric properties of graphs. A reader who follows both network curvature papers and matching theory would find the connections useful. It deserves serious peer review because the reductions appear sound and the new problems are well-scoped. I recommend putting it through the review process.

Referee Report

0 major / 2 minor

Summary. The paper introduces a formal framework for detecting critical edges in undirected graphs by measuring changes in Ollivier-Ricci curvature after edge removal. It defines a family of problems in this framework and derives algorithmic results together with inapproximability results, including reductions that connect the problems to the exact perfect matching problem, perfect matching blocker problems on bipartite graphs, and standard combinatorial packing/covering problems.

Significance. If the stated reductions and complexity classifications hold, the work usefully imports discrete curvature concepts from network science into the computational complexity literature. The explicit links to perfect-matching blocker and packing problems are concrete and could support further algorithmic study; the purely combinatorial formulation avoids reliance on unproven empirical claims about curvature identifying structurally important edges.

minor comments (2)

The abstract asserts algorithmic and inapproximability results without even a one-sentence sketch of the key reductions or problem definitions; adding a brief indication of the main technical approach would improve accessibility.
Notation for the curvature-change threshold and the precise objective functions of the defined problems should be introduced with a dedicated preliminary section or table to avoid ambiguity when the reductions are presented.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful review and positive evaluation of our manuscript. We appreciate the recommendation for minor revision and will incorporate any necessary adjustments in the revised version. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines a family of combinatorial decision and optimization problems centered on edges whose removal induces large changes in Ollivier-Ricci curvature, then establishes algorithmic results and inapproximability via explicit polynomial-time reductions to the perfect-matching blocker problem and to standard packing/covering problems. These reductions are one-directional mappings between independently defined graph-theoretic objects and do not rely on any quantity being defined in terms of itself, on fitted parameters renamed as predictions, or on self-citations whose validity is presupposed by the present work. The central claims therefore remain self-contained combinatorial statements.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, axioms, or invented entities are stated. Standard graph-theoretic assumptions (undirected simple graphs, finite vertex sets) are implicitly used but not enumerated.

pith-pipeline@v0.9.0 · 5461 in / 1083 out tokens · 20149 ms · 2026-05-15T20:30:27.747115+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

formal framework for studying algorithmic and computational complexity issues for detecting critical edges in an undirected graph using Ollivier-Ricci curvatures

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages · 1 internal anchor

[1]

and Barab ´asi, A.-L

Albert, R. and Barab ´asi, A.-L. (2002). Statistical mechanics of complex networks.Reviews of Modern Physics, 74:47–97

work page 2002
[2]

S., Gitter, A., G ¨ursoy, G., Paul, P., and Sontag, E

Albert, R., DasGupta, B., Hegde, R., Sivanathan, G. S., Gitter, A., G ¨ursoy, G., Paul, P., and Sontag, E. (2011). Computationally efficient measure of topological redundancy of biological and social networks. Physical Review E, 84:036117

work page 2011
[3]

Albert, R., DasGupta, B., and Mobasheri, N. (2014). Topological implications of negative curvature for biological and social networks.Physical Review E, 89:032811

work page 2014
[4]

and Sturm, K.-T

Bacher, K. and Sturm, K.-T. (2010). Localization and tensorization properties of the curvature- dimension condition for metric measure spaces.Journal of Functional Analysis, 259(1):28–56

work page 2010
[5]

Bridson, M. R. and H ¨afliger, A. (1999).Metric Spaces of Non-Positive Curvature. Springer-Verlag Berlin Heidelberg, 1 edition

work page 1999
[6]

and Dyer, M

Bubley, R. and Dyer, M. (1997). Path coupling: A technique for proving rapid mixing in markov chains. InProceedings 38th Annual Symposium on Foundations of Computer Science, pages 223–231

work page 1997
[7]

Chatterjee, T., Albert, R., Thapliyal, S., Azarhooshang, N., and DasGupta, B. (2021a). Detecting net- work anomalies using forman-ricci curvature and a case study for human brain networks.Scientific Reports, 11

work page
[8]

Chatterjee, T., DasGupta, B., and Albert, R. (2021b). A review of two network curvature measures. In Rassias, T. M. and Pardalos, P. M., editors,Nonlinear Analysis and Global Optimization, volume 167 of Springer Optimization and Its Applications, pages 51–69. Springer

work page
[9]

Chien, I., Lin, C.-Y ., and Wang, I.-H. (2018). Community detection in hypergraphs: Optimal statistical limit and efficient algorithms. In Storkey, A. and Perez-Cruz, F., editors,Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 ofProceedings of Machine Learning Research, pages 871–879. PMLR

work page 2018
[10]

Coupette, C., Dalleiger, S., and Rieck, B. (2023). Ollivier-ricci curvature for hypergraphs: A unified framework. InThe Eleventh International Conference on Learning Representations

work page 2023
[11]

DasGupta, B., Grigorescu, E., and Mukherjee, T. (2023). On computing discretized ricci curvatures of graphs: Local algorithms and (localized) fine-grained reductions.Theoretical Computer Science, 975:114127

work page 2023
[12]

V ., and Yahyanejad, F

DasGupta, B., Janardhanan, M. V ., and Yahyanejad, F. (2020). Why did the shape of your network change? (on detecting network anomalies via non-local curvatures).Algorithmica, 82(7):1741–1783

work page 2020
[13]

and Liang, J

DasGupta, B. and Liang, J. (2016).Models and Algorithms for Biomolecules and Molecular Networks. Wiley-IEEE Press, New Jersey

work page 2016
[14]

and Steurer, D

Dinur, I. and Steurer, D. (2014). Analytical approach to parallel repetition. InProceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, pages 624–633, New York, NY , USA. Association for Computing Machinery

work page 2014
[15]

Eidi, M., Farzam, A., Leal, W., Samal, A., and Jost, J. (2020). Edge-based analysis of networks: curvatures of graphs and hypergraphs.Theory in Biosciences, 139:337–348. 21

work page 2020
[16]

Feige, U. (1998). A threshold of ln n for approximating set cover.Journal of the ACM, 45(4):634–652

work page 1998
[17]

and Padilla, F

Foltin, R. and Padilla, F. (2002). Cheerleading radical en pink & silver. culture de la manifestation : entre conformisme et confrontation.Transversal - eipcp Multilingual Webjournal

work page 2002
[18]

Forman, R. (2003). Bochner’s method for cell complexes and combinatorial ricci curvature.Discrete and Computational Geometry, 29(3):323–374

work page 2003
[19]

Gromov, M. (1987). Hyperbolic groups. In Gersten, S. M., editor,Essays in Group Theory, volume 8, pages 75–263. Springer, New York, NY

work page 1987
[20]

Gromov, M. (1991). Sign and geometric meaning of curvature.Rendiconti del Seminario Matematico e Fisico di Milano, 61:9–123

work page 1991
[21]

Gurjar, R., Korwar, A., Messner, J., Straub, S., and Thierauf, T. (2016). Planarizing gadgets for perfect matching do not exist.ACM Transactions on Computation Theory, 8(4)

work page 2016
[22]

Gurjar, R., Korwar, A., Messner, J., and Thierauf, T. (2017). Exact perfect matching in complete graphs.ACM Transactions on Computation Theory, 9(2):1–20

work page 2017
[23]

Kamalian, R. R. and Mkrtchyan, V . V . (2007). Two polynomial algorithms for special maximum matching constructing in trees.arXiv preprint arXiv:0707.2295v1

work page internal anchor Pith review Pith/arXiv arXiv 2007
[24]

and Whishaw, I

Kolb, B. and Whishaw, I. Q. (2007).Fundamentals of human neuropsychology. Worth Publishers, New York, NY , 6 edition

work page 2007
[25]

R., and Martin, S

Lacroix, M., Mahjoub, A. R., and Martin, S. (2011). Combinatorial optimization model and mip for- mulation for the structural analysis of conditional differential-algebraic systems.Computers & Industrial Engineering, 61(2):422–429

work page 2011
[26]

R., Martin, S., and Picouleau, C

Lacroix, M., Mahjoub, A. R., Martin, S., and Picouleau, C. (2012). On the np-completeness of the perfect matching free subgraph problem.Theoretical Computer Science, 423:25–29

work page 2012
[27]

F., and Jost, J

Leal, W., Restrepo, G., Stadler, P. F., and Jost, J. (2021). Forman-ricci curvature for hypergraphs. Advances in Complex Systems, 24(01):2150003

work page 2021
[28]

Maalouly, N. E. (2023). Exact Matching: Algorithms and Related Problems. In Berenbrink, P., Bouyer, P., Dawar, A., and Kant´e, M. M., editors,40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), volume 254 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:17, Dagstuhl, Germany. Schloss Dagstuhl – L...

work page 2023
[29]

V ., and Vazirani, V

Mulmuley, K., Vazirani, U. V ., and Vazirani, V . V . (1987). Matching is as easy as matrix inversion. Combinatorica, 7:105–113

work page 1987
[30]

Newman, M. E. J. (2010).Networks: An Introduction. Oxford University Press

work page 2010
[31]

A., Nguyen, L., Do, T

Nghiem, N. A., Nguyen, L., Do, T. K., Wei, T.-C., and Phan, T. V . (2025). Quantum algorithm for estimating ollivier-ricci curvature.arXiv preprint arXiv:2512.09822v1

work page arXiv 2025
[32]

Ollivier, Y . (2007). Ricci curvature of metric spaces.Comptes Rendus Mathematique, 345(11):643– 646

work page 2007
[33]

Ollivier, Y . (2009). Ricci curvature of markov chains on metric spaces.Journal of Functional Analysis, 256:810–864. 22

work page 2009
[34]

Ollivier, Y . (2010). A survey of ricci curvature for metric spaces and markov chains. In Kotani, M., Hino, M., and Kumagai, T., editors,Advanced Studies in Pure Mathematics, volume 57, pages 343–381. Mathematical Society of Japan

work page 2010
[35]

Ollivier, Y . (2013). A visual introduction to Riemannian curvatures and some discrete generalizations. In Dafni, G., McCann, R. J., and Stancu, A., editors,Analysis and Geometry of Metric Measure Spaces: Lecture Notes of the 50th S ´eminaire de Math´ematiques Sup´erieures (SMS), Montr´eal, 2011, volume 56, pages 197–219. American Mathematical Society, Pr...

work page 2013
[36]

and Villani, C

Ollivier, Y . and Villani, C. (2012). A curved brunn–minkowski inequality on the discrete hypercube, or: What is the ricci curvature of the discrete hypercube?SIAM Journal on Discrete Mathematics, 26(3):983–996

work page 2012
[37]

Papadimitriou, C. H. and Steiglitz, K. (1982).Combinatorial optimization: algorithms and complexity. Prentice-Hall, Inc., NJ, USA

work page 1982
[38]

Sengupta, P., Azarhooshang, N., Albert, R., and DasGupta, B. (2025). Finding influential cores via normalized ricci flows in directed and undirected hypergraphs with applications.Physical Review E, 111:044316

work page 2025
[39]

Sia, J., Jonckheere, E., and Bogdan, P. (2019). Ollivier-ricci curvature-based method to community detection in complex networks.Scientific Reports, 9:9800

work page 2019
[40]

K., Carpenter, K

Simhal, A. K., Carpenter, K. L. H., Nadeem, S., Kurtzberg, J., Song, A., Tannenbaum, A., Sapiro, G., and Dawson, G. (2020). Measuring robustness of brain networks in autism spectrum disorder with Ricci curvature.Scientific Reports, 10:10819

work page 2020
[41]

P., Mohanraj, K., Jost, J., Saucan, E., and Samal, A

Sreejith, R. P., Mohanraj, K., Jost, J., Saucan, E., and Samal, A. (2016). Forman curvature for complex networks.Journal of Statistical Mechanics: Theory and Experiment, 2016(6):063206

work page 2016
[42]

Tian, Y ., Ma, J., Yang, Y ., and Zhao, L. (2025). Community detection of undirected hypergraphs by ricci flow.Physical Review E, 112:044311

work page 2025
[43]

Tononi, G., Sporns, O., and Edelman, G. M. (1999). Measures of degeneracy and redundancy in biological networks.Proceedings of the National Academy of Sciences, 96(6):3257–3262

work page 1999
[44]

Weber, M., Saucan, E., and Jost, J. (2017). Characterizing complex networks with forman-ricci curva- ture and associated geometric flows.Journal of Complex Networks, 5(4):527–550

work page 2017
[45]

Yadav, Y ., Elumalai, P., Williams, N., Jost, J., and Samal, A. (2023a). Discrete ricci curvatures capture age-related changes in human brain functional connectivity networks.Frontier in Aging Neuroscience, 15:1120846

work page
[46]

Yadav, Y ., Elumalai, P., Williams, N., Jost, J., and Samal, A. (2023b). Discrete ricci curvatures capture age-related changes in human brain functional connectivity networks.Frontiers in Aging Neuroscience, 15

work page
[47]

S., Ma, T., Gao, J., and Chen, C

Ye, Z., Liu, K. S., Ma, T., Gao, J., and Chen, C. (2020). Curvature graph network. InInternational Conference on Learning Representations

work page 2020
[48]

Yuster, R. (2012). Almost exact matchings.Algorithmica, 63:39–50

work page 2012
[49]

Zenklusen, R., Ries, B., Picouleau, C., de Werra, D., Costa, M.-C., and Bentz, C. (2009). Blockers and transversals.Discrete Mathematics, 309(13):4306–4314. 23 A Proof of Theorem 1 (a)Given a valid solution⃗ z={z ui,vj |u i ∈L, v j ∈R}of value TRANSPORT-COST H(⃗ z, L, R,PL,P R) onH, we obtain a valid solution of same cost on bHby settingbz ui,k,vj,ℓ = zui...

work page 2009