6 Interpretation
There are two ways of looking at this lemma:
-
The rigorous way: SScSSoBQC is NP-hard, despite that fact
that it sounds easier than the original quotient cut problem.
-
The optimistic way: perhaps SScSSoBQC typically is
easier in practice, and we can exploit that fact to
obtain a useful heuristic partitioning method.