Let $G$ be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut $C\subseteq E(G)$, such that $|C|$ is minimum.
Let us generalize it the following way: let $f$ be a polynomial time computable function on the subsets of the edge set, and we look for a cut $C$, such that $f(C)$ is minimum.
Depending on the function, this problem can be easy or hard:
If $f$ depends only on $|C|$, and it is a monotone increasing function of $|C|$, then $f(C)$ will still be minimized by a minimum cut, which can be found in polynomial time.
If $f$ depends only on $|C|$, and it is a strictly monotone decreasing function of $|C|$, then minimizing $f(C)$ is equivalent to finding a maximum cut, which is known to be NP-hard (or, regarding decision, rather than search, it is NP-complete).
Question: In general, how does the complexity of the problem depend on the choice of the function? Which are some (non-trivial) cases, other than case 1 above, when it is solvable in polynomial time?
Furthermore, I would like to propose the following conjecture:
Conjecture: There is a dichotomy here, that is, for every function the problem is either solvable in polynomial time, or else it is NP-hard (assuming we do not restrict the graph to some special graph class).
Is anything known about this?