Pith. sign in

REVIEW 1 cited by

A Note on Isolating Cut Lemma for Submodular Function Minimization

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2103.15724 v1 pith:TWCJOLZA submitted 2021-03-29 cs.DS

Sagnik Mukhopadhyay , Danupon Nanongkai This is my paper · ORCID
classification cs.DS
keywords functionisolatinglemmanotesubmodularalgorithmsbeencontains
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

It has been observed independently by many researchers that the isolating cut lemma of Li and Panigrahi [FOCS 2020] can be easily extended to obtain new algorithms for finding the non-trivial minimizer of a symmetric submodular function and solving the hypergraph minimum cut problem. This note contains these observations.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut

    cs.DS 2025-06 accept novelty 8.0 of 10

    A randomized algorithm computes the weighted global minimum vertex-cut in O(min{mn^{0.99+o(1)}, m^{1.5+o(1)}}) time, breaking the long-standing O~(mn) barrier.

Pith tools