Constant-factor hardness of Min-UnCut
For every fixed integer , there is a deterministic polynomial-time many-one reduction mapping a 3SAT formula to a pair , where is an explicit finite simple undirected unweighted graph and is a binary-encoded integer, such that satisfiable and unsatisfiable ; consequently, approximating Min-UnCut within any fixed factor is NP-hard.
The proof is complete and self-contained: all parameter dependencies are ordered effectively, the rational discretization error is bounded by , and the path-gadget reduction preserves the exact optimum without an additive baseline.
“For every fixed integer K ≥ 2, there is a deterministic polynomial-time many-one reduction mapping a 3SAT formula φ to a pair (G, k), where G is an explicit finite simple undirected unweighted graph and k ≥ 1 is a binary-encoded integer, such that φ satisfiable =⇒ OPTuncut(G) ≤ k, φ unsatisfiable =⇒ OPTuncut(G) > Kk.” · Show in paper