  Given a (multi)graph $G$ which contains a bipartite subgraph with $\rho$
edges, what is the largest triangle-free subgraph of $G$ that can be found
efficiently? We present an SDP-based algorithm that finds one with at least
$0.8823 \rho$ edges, thus improving on the subgraph with $0.878 \rho$ edges
obtained by the classic Max-Cut algorithm of Goemans and Williamson. On the
other hand, by a reduction from Hastad's 3-bit PCP we show that it is NP-hard
to find a triangle-free subgraph with $(25 / 26 + \epsilon) \rho \approx (0.961
+ \epsilon) \rho$ edges.
  As an application, we classify the Maximum Promise Constraint Satisfaction
Problem MaxPCSP($G$,$H$) for all bipartite $G$: Given an input (multi)graph $X$
which admits a $G$-colouring satisfying $\rho$ edges, find an $H$-colouring of
$X$ that satisfies $\rho$ edges. This problem is solvable in polynomial time,
apart from trivial cases, if $H$ contains a triangle, and is NP-hard otherwise.
