On the hardness of approximating MULTICUT and SPARSEST-CUT

We show that the MULTICUT, SPARSEST-CUT, and MIN2CNF equivalent to DELETION problems are NP-hard to approximate within every constant factor, assuming the Unique Games Conjecture of Khot (2002). A quantitatively stronger version of the conjecture implies an inapproximability factor of Omega (root log log n).