3
$\begingroup$

A maximal minimum cut is a minimum capacity cut with the largest number of edges.

$\endgroup$
1
$\begingroup$

This problem is NP-hard if 0 weight is allowed. We can reduce Not-All-Equal 3SAT to the decision version of this problem.

Given an instance of Not-All-Equal 3SAT with $n$ variables and $m$ clauses, for each variable $x_i$, we create two vertices $v_i$ and $v_i'$ with an edge between them for each variable. In addition, for each clause, for example, $x_1\vee x_2\vee \neg x_3$, we add three edges among $v_1,v_2,v_3'$ (thus they form a triangle). All edges have weight 0. Now we can see there is a minimum cut (in fact, every cut is a minimum cut) with at least $n+2m$ edges if and only if the Not-All-Equal 3SAT instance is satisfiable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.