  While the ground-state problem for the random-field Ising model is
polynomial, and can be solved using a number of well-known algorithms for
maximum flow or graph cut, the analogue random-field Potts model corresponds to
a multi-terminal flow problem that is known to be NP hard. Hence an efficient
exact algorithm is very unlikely to exist. As we show here, it is nevertheless
possible to use an embedding of binary degrees of freedom into the Potts spins
in combination with graph-cut methods to solve the corresponding ground-state
problem approximately in polynomial time. We benchmark this heuristic algorithm
using a set of quasi-exact ground states found for small systems from long
parallel tempering runs. For not too large number $q$ of Potts states, the
method based on graph cuts finds the same solutions in a fraction of the time.
We employ the new technique to analyze the breakup length of the random-field
Potts model in two dimensions.
