My question is this: why is it the case that the uniform cost version of the Sparsest Cut problem has eluded hardness of approximation results whereas the non-uniform version has not; my intuition is that the non-uniform case should subsume the uniform case. In the paper of Khot and Vishnoi and that of Chawla et al, the authors note that their hardness results (assuming some form of UGC, Sparsest Cut is APX-hard) hold only for the non-uniform sparsest cut. Why is this the case?

To summarize, the non-uniform case of the Sparsest Cut problem is APX-hard if UGC is true, and the uniform case is known to have no PTAS if $NP\not\subset\bigcap_{\epsilon>0}BPTIME\left(2^{n^\epsilon}\right)$ [see this paper].

  • $\begingroup$ The non-uniform case is a more general problem so it makes sense that it is easier to prove hardness for it. The phrasing in your question is unclear. $\endgroup$ Commented Jun 28, 2023 at 13:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.