arxiv: 2605.07265 · v1 · submitted 2026-05-08 · 💻 cs.DS · cs.DM· math.CO

Recognition: 1 theorem link

· Lean Theorem

EPTAS for Hard Graph Cut Problems for Dense Graphs

Hiroaki Mori, Kaisei Deguchi, Ken-ichi Kawarabayashi

Authors on Pith no claims yet

Pith reviewed 2026-05-11 01:37 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.CO

keywords EPTASdense graphsgraph cutsConstrainedMinCutMinQuotientCutProductSparsestCutweak regularity lemmaapproximation algorithms

0 comments

The pith

Everywhere-δ-dense graphs admit the first EPTAS for ConstrainedMinCut and several related hard cut problems.

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

The paper seeks to establish that NP-hard graph cut problems become efficiently approximable on everywhere-δ-dense graphs, where every vertex has degree at least δn for constant δ>0. A sympathetic reader would care because such density appears in many real networks, turning intractable problems into ones solvable with running time f(1/ε) n to a small power. The central result is an EPTAS for ConstrainedMinCut under global vertex-weight constraints, which directly captures BalancedSeparator and SmallSetExpansion. The same technique yields EPTAS for MinQuotientCut and ProductSparsestCut on graphs with integer dense weights, covering UniformSparsestCut, EdgeExpansion, Conductance, and NormalizedCut. The method relies on the weak regularity lemma plus sampling and estimation, sidestepping heavier tools such as the Lasserre hierarchy.

Core claim

The central claim is that ConstrainedMinCut under a global constraint on vertex weights admits an EPTAS running in time f(1/ε) n^{O(1)} on everywhere-δ-dense graphs, and that this algorithm serves as a subroutine for the first EPTAS for MinQuotientCut and ProductSparsestCut on the same graphs when vertex weights are integer-valued and dense. The EPTAS is obtained by applying the weak regularity lemma to partition the graph into a small number of clusters, then using sampling and estimation to identify a near-optimal cut that satisfies the weight constraint.

What carries the argument

The weak regularity lemma applied to dense graphs, together with sampling and estimation techniques that locate a near-optimal constrained cut.

If this is right

BalancedSeparator and SmallSetExpansion admit EPTAS on everywhere-δ-dense graphs.
MinQuotientCut and ProductSparsestCut admit EPTAS on everywhere-δ-dense graphs with integer dense vertex weights, thereby covering UniformSparsestCut, EdgeExpansion, Conductance, and NormalizedCut.
All listed problems now have approximation schemes whose dependence on 1/ε is independent of n.
The unified reduction allows the single ConstrainedMinCut algorithm to solve the entire family without invoking Lasserre hierarchies or specialized integer programs.

Where Pith is reading between the lines

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

If many real-world networks satisfy the everywhere-dense condition, the algorithms could be implemented directly for large instances where exact solutions remain impossible.
The sampling and estimation steps may extend to other optimization tasks on dense graphs once a suitable regularity partition is available.
Density assumptions appear to bypass the hardness barriers that hold for the same problems on sparse graphs.
A direct empirical check would generate random δ-dense graphs, run the sampling procedure, and verify whether the observed approximation ratio matches the predicted (1+ε) bound.

Load-bearing premise

The input graphs must be everywhere-δ-dense for some fixed constant δ>0, and vertex weights must be integer-valued and dense for the quotient and product variants.

What would settle it

A concrete counterexample would be an infinite family of everywhere-δ-dense graphs on which no algorithm running in f(1/ε) n^{O(1)} time can produce a (1+ε)-approximation to ConstrainedMinCut for arbitrarily small ε>0.

Figures

Figures reproduced from arXiv: 2605.07265 by Hiroaki Mori, Kaisei Deguchi, Ken-ichi Kawarabayashi.

read the original abstract

Everywhere-$\delta$-dense graphs are defined as graphs on $n$ vertices in which every vertex has degree at least $\delta n$ for some constant $\delta > 0$. Approximation schemes are vital for handling NP-hard optimization problems, but for many graph cut problems, existing PTAS algorithms often suffer from running times of $n^{f(1/\varepsilon)}$. In this paper, we bring PTASs down to EPTASs for several fundamental minimization problems on everywhere-$\Omega(1)$-dense graphs. Specifically, we present the first Efficient Polynomial-Time Approximation Scheme (EPTAS), running in time $f(1/\varepsilon)n^{O(1)}$, for the ConstrainedMinCut problem under a global constraint on vertex weights, a problem that captures BalancedSeparator and SmallSetExpansion. Moreover, we give the first EPTASs for MinQuotientCut and ProductSparsestCut on everywhere-$\delta$-dense graphs with integer-valued dense vertex weights; these problems generalize the four well-known problems UniformSparsestCut, EdgeExpansion, Conductance, and NormalizedCut. Our main technical contribution is an EPTAS for ConstrainedMinCut, based on the weak regularity lemma and sampling and estimation techniques. We then obtain EPTASs for MinQuotientCut and ProductSparsestCut via a unified reduction that invokes this algorithm as a subroutine. In contrast, previous works giving PTASs for these problems on everywhere-$\delta$-dense graphs typically rely on powerful tools such as the Lasserre hierarchy or specific integer programming technique, which we avoid.

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 gives the first EPTAS for ConstrainedMinCut on everywhere-dense graphs via weak regularity and sampling, then reduces the quotient and product cut problems to it.

read the letter

The main thing to know is that they convert prior PTAS results for these cut problems into EPTASes on everywhere-δ-dense graphs, with running time f(1/ε) n^O(1) instead of n^{f(1/ε)}. The core is an EPTAS for ConstrainedMinCut that handles a global vertex-weight constraint, and the other two problems follow from a single reduction that calls it as a black box. This avoids Lasserre hierarchies and custom IP methods used before, which is a genuine improvement in simplicity and runtime dependence on ε. The weak regularity lemma plus sampling and estimation arguments are standard tools applied cleanly here, and the abstract indicates the error bounds and sampling sizes are worked out in the body. That part looks solid on its own terms. The reductions for MinQuotientCut and ProductSparsestCut are the softer spot. They need to preserve both the everywhere-δ-density and the integer-dense weight condition so the subroutine still applies with the claimed time bound. The abstract claims a unified reduction that keeps the properties, but without seeing the explicit construction it is hard to confirm the auxiliary instances stay dense for arbitrary inputs. If that step has a gap, the EPTAS claim for the two derived problems weakens. This is aimed at people working on approximation schemes for graph partitioning and clustering on dense instances. Readers who care about elementary techniques over heavy hierarchies will find the approach useful. It deserves a serious referee because the main algorithmic route is new and internally consistent, even if the reduction details need extra scrutiny. I would send it to peer review with a request to verify the density preservation in the reductions.

Referee Report

1 major / 1 minor

Summary. The paper claims the first EPTAS (f(1/ε)n^{O(1)} time) for ConstrainedMinCut on everywhere-δ-dense graphs (capturing BalancedSeparator and SmallSetExpansion), obtained via the weak regularity lemma plus sampling/estimation. It further claims EPTASs for MinQuotientCut and ProductSparsestCut on the same graphs (with integer-valued dense weights) by a unified reduction that treats the ConstrainedMinCut algorithm as a black-box subroutine; these generalize UniformSparsestCut, EdgeExpansion, Conductance, and NormalizedCut. The approach avoids Lasserre hierarchies or heavy IP techniques used in prior PTASs.

Significance. If the claims hold, the results improve approximation schemes for these cut problems from n^{f(1/ε)} PTASs to true EPTASs on dense graphs, using only standard tools (weak regularity lemma and sampling). This is a meaningful technical advance for the dense-graph regime, with the elementary toolkit and unified reduction as strengths. The generalization to multiple well-known problems adds breadth.

major comments (1)

[unified reduction (abstract and main technical contribution)] The unified reduction from MinQuotientCut/ProductSparsestCut to ConstrainedMinCut (invoked as a black box per the abstract) must preserve everywhere-δ-density (min-degree ≥ δn) and, for the quotient/product cases, integer-valued dense vertex weights. No explicit construction or argument is exhibited in the high-level description showing that the auxiliary instances satisfy these properties for arbitrary input dense graphs; if density drops below a positive constant fraction of the new vertex count, the main EPTAS subroutine cannot be applied while retaining the f(1/ε)n^{O(1)} guarantee. This is load-bearing for the claims on MinQuotientCut and ProductSparsestCut.

minor comments (1)

[EPTAS for ConstrainedMinCut] Clarify the precise sampling sizes and error bounds in the estimation arguments that accompany the weak regularity lemma application; these are referenced but not numerically instantiated in the abstract-level description.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation of the significance of our results and for the constructive feedback on the unified reduction. We address the major comment below and will incorporate the requested clarifications in the revised manuscript.

read point-by-point responses

Referee: [unified reduction (abstract and main technical contribution)] The unified reduction from MinQuotientCut/ProductSparsestCut to ConstrainedMinCut (invoked as a black box per the abstract) must preserve everywhere-δ-density (min-degree ≥ δn) and, for the quotient/product cases, integer-valued dense vertex weights. No explicit construction or argument is exhibited in the high-level description showing that the auxiliary instances satisfy these properties for arbitrary input dense graphs; if density drops below a positive constant fraction of the new vertex count, the main EPTAS subroutine cannot be applied while retaining the f(1/ε)n^{O(1)} guarantee. This is load-bearing for the claims on MinQuotientCut and ProductSparsestCut.

Authors: We agree that preservation of everywhere-δ-density and integer-valued dense vertex weights in the auxiliary instances is essential for applying the ConstrainedMinCut EPTAS as a black box while retaining the overall f(1/ε)n^{O(1)} runtime. The manuscript describes the reduction at a high level in the abstract and introduction and provides the construction in the body, but does not include an explicit lemma verifying the density and weight properties for arbitrary inputs. In the revision we will add a dedicated lemma (with proof) showing that the auxiliary graphs remain everywhere-δ'-dense for a positive constant δ' depending only on the original δ, and that the vertex weights remain positive integers satisfying the density condition. This will confirm that the subroutine applies directly without loss of the EPTAS guarantee. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation relies on independent regularity and sampling tools

full rationale

The paper derives its EPTAS for ConstrainedMinCut directly from the weak regularity lemma plus sampling/estimation techniques that pre-exist the target cut problems and do not reference the final approximation guarantees. Reductions to MinQuotientCut and ProductSparsestCut are described only as black-box invocations of that subroutine; the abstract supplies no equations or definitions in which the output of the subroutine is fed back to define its own inputs or density assumptions. No self-citations, fitted parameters renamed as predictions, or ansatzes imported via prior work appear in the provided text. The everywhere-δ-dense premise is stated as an external input condition rather than derived from the algorithm itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on the weak regularity lemma and standard sampling concentration bounds; no new free parameters, invented entities, or ad-hoc axioms are introduced beyond the density assumption already stated in the problem definition.

axioms (1)

standard math Weak regularity lemma for graphs
Invoked as the main technical tool to obtain a partition with uniform edge densities.

pith-pipeline@v0.9.0 · 5605 in / 1194 out tokens · 38859 ms · 2026-05-11T01:37:56.340347+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/RealityFromDistinction.lean reality_from_one_distinction unclear
Our main technical contribution is an EPTAS for ConstrainedMinCut, based on the weak regularity lemma and sampling and estimation techniques. We then obtain EPTASs for MinQuotientCut and ProductSparsestCut via a unified reduction...

Reference graph

Works this paper leans on

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

[1]

Explicit expanders of every degree and size

Noga Alon. Explicit expanders of every degree and size. Combinatorica, 41(4):447–463, 2021

work page 2021
[2]

Polynomial time approximation schemes for dense instances of np-hard problems

Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of np-hard problems. Journal of Computer and System Sci- ences, 58(1):193–210, 1999

work page 1999
[3]

Proof verification and the hardness of approximation problems

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM) , 45(3):501–555, 1998

work page 1998
[4]

Inapproximability of treewidth, one-shot peb- bling, and related layout problems

Per Austrin, Toniann Pitassi, and Yu Wu. Inapproximability of treewidth, one-shot peb- bling, and related layout problems. In International Workshop on Approximation Algo- rithms for Combinatorial Optimization , pages 13–24. Springer, 2012

work page 2012
[5]

Approximability of dense instances of nearest codeword problem

Cristina Bazgan, W Fernandez de la Vega, and Marek Karpinski. Approximability of dense instances of nearest codeword problem. In Scandinavian Workshop on Algorithm Theory , pages 298–307. Springer, 2002

work page 2002
[6]

Polynomial time approxi- mation schemes for dense instances of minimum constraint satisfaction

Cristina Bazgan, W Fernandez de La Vega, and Marek Karpinski. Polynomial time approxi- mation schemes for dense instances of minimum constraint satisfaction. Random Structures & Algorithms , 23(1):73–91, 2003

work page 2003
[7]

Polynomial time approximation of dense weighted instances of MAX-CUT

Wenceslas Fernandez de la Vega and Marek Karpinski. Polynomial time approximation of dense weighted instances of MAX-CUT . Inst. für Informatik, 2000

work page 2000
[8]

A fast new algorithm for weak graph regularity

Jacob Fox, László Miklós Lovász, and Yufei Zhao. A fast new algorithm for weak graph regularity. Combinatorics, Probability and Computing , 28(5):777–790, 2019. 28

work page 2019
[9]

The regularity lemma and approximation schemes for dense problems

Alan Frieze and Ravi Kannan. The regularity lemma and approximation schemes for dense problems. In Proceedings of 37th conference on foundations of computer science , pages 12–20. IEEE, 1996

work page 1996
[10]

Quick approximation to matrices and applications

Alan Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combi- natorica, 19(2):175–220, 1999

work page 1999
[11]

On set expansion problems and the small set expansion conjecture

Rajiv Gandhi and Guy Kortsarz. On set expansion problems and the small set expansion conjecture. In International Workshop on Graph-Theoretic Concepts in Computer Science , pages 189–200. Springer, 2014

work page 2014
[12]

A chernoff bound for random walks on expander graphs

David Gillman. A chernoff bound for random walks on expander graphs. SIAM Journal on Computing , 27(4):1203–1220, 1998

work page 1998
[13]

Correlation clustering with a fixed number of clusters

Ioannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number of clusters. arXiv preprint cs/0504023 , 2005

work page internal anchor Pith review arXiv 2005
[14]

Property testing and its connection to learning and approximation

Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM) , 45(4):653–750, 1998

work page 1998
[15]

Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives

Venkatesan Guruswami and Ali Kemal Sinop. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages 482–491. IEEE, 2011

work page 2011
[16]

Polynomial time approximation schemes for some dense instances of np-hard optimization problems

Marek Karpinski. Polynomial time approximation schemes for some dense instances of np-hard optimization problems. Algorithmica, 30(3):386–397, 2001

work page 2001
[17]

Linear time approximation schemes for the gale- berlekamp game and related minimization problems

Marek Karpinski and Warren Schudy. Linear time approximation schemes for the gale- berlekamp game and related minimization problems. In Proceedings of the forty-first annual ACM symposium on Theory of computing , pages 313–322, 2009

work page 2009
[18]

Optimal inapprox- imability results for max-cut and other 2-variable csps? SIAM Journal on Computing , 37(1):319–357, 2007

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapprox- imability results for max-cut and other 2-variable csps? SIAM Journal on Computing , 37(1):319–357, 2007

work page 2007
[19]

Vertex cover might be hard to approximate to within 2- ε

Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2- ε. Journal of Computer and System Sciences , 74(3):335–349, 2008

work page 2008
[20]

Explicit expanders and the ra- manujan conjectures

Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Explicit expanders and the ra- manujan conjectures. In Proceedings of the eighteenth annual ACM symposium on Theory of computing , pages 240–246, 1986

work page 1986
[21]

Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis

Pasin Manurangsi. Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis. Algorithms, 11(1):10, 2018

work page 2018
[22]

Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators

Grigorii Aleksandrovich Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problemy peredachi informatsii, 24(1):51–60, 1988

work page 1988
[23]

Yet another algorithm for dense max cut: go greedy

Claire Mathieu and Warren Schudy. Yet another algorithm for dense max cut: go greedy. In SODA, volume 8, pages 176–182, 2008

work page 2008
[24]

Existence and explicit constructions of q+ 1 regular ramanujan graphs for every prime power q

Moshe Morgenstern. Existence and explicit constructions of q+ 1 regular ramanujan graphs for every prime power q. Journal of Combinatorial Theory, Series B , 62(1):44–62, 1994. 29

work page 1994
[25]

A new regularity lemma and faster approximation algorithms for low threshold rank graphs

Shayan Oveis Gharan and Luca Trevisan. A new regularity lemma and faster approximation algorithms for low threshold rank graphs. In International Workshop on Approximation Algorithms for Combinatorial Optimization , pages 303–316. Springer, 2013

work page 2013
[26]

Optimal algorithms and inapproximability results for every csp? In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 245–254, 2008

Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 245–254, 2008

work page 2008
[27]

Graph expansion and the unique games conjec- ture

Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjec- ture. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 755–764, 2010

work page 2010
[28]

Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems

Yuichi Yoshida and Yuan Zhou. Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems. In Proceedings of the 5th conference on Innovations in theoretical computer science , pages 423–438, 2014. 30

work page 2014