Combinatorial persistency criteria for multicut and max-cut

Jan-Hendrik Lange, Bjoern Andres, Paul Swoboda

In combinatorial optimization, partial variable assignments are called persistent if they agree with some optimal solution. We propose persistency criteria for the multicut and max…