# Minimum cut with nonlinear objective function

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:

1. 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.

2. 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).

• But can't you formulate almost any problem in NP this way? E.g., given an instance $X$ of a problem in NP with verifier $V$, construct a bipartite graph $G$ formed by $n$ independent edges $(u_i, w_i)$, and define $f(C)$ to be 0 if $V(X, C)$ accepts, and 1 otherwise. (Here $C$ is interpreted as an n-bit binary string, whose $i$th bit is 1 if $C$ contains $(u_i, w_i)$.) Or, if you like, you can make $G$ have $2n$ independent edges, then interpret $C$ as encoding two $n$-bit binary strings $A, B$, and make $f(C)$ equal 0 only if $A$ encodes $X$ and the verifier $V(A, B)$ accepts. – Neal Young Apr 20 at 20:31
• What about padding? Given graph $G=(V,E)$, define $f(C)$ s.t. if $G$ contains a component of size $n$ plus $2^{n^{1/c}}-n$ isolated vertices, then $f(C) = -|C|$, else $f(C)=0$. Max Cut on inputs of size $n$ is equivalent to minimizing $f$ on inputs of size $N = 2^{n^{1/c}}$. If that problem has an $N^{O(1)}$-time algorithm, then Max Cut has a $2^{O(n^{1/c})}$-time algorithm, which is unlikely. If this problem is NP-hard, then Max Cut on instances of size $N$ reduces to Max-Cut on instances of size $O(\log^{c} N)$, which (applying the reduction twice) one can show implies P=NP. – Neal Young Apr 23 at 14:36
• I guess one can work around that too. E.g., define $f(C)$ to be zero unless $G$ consists of a very long path $p$ connected at one end to a much smaller connected subgraph $G'$. In that case define $f(C)$ to be $-|C|$. Generally, maybe one needs to define more precisely what you mean by "$f$ depends only on $|C|$". In these "bad" examples, $f(C)$ depends on $|C|$ and $G$. Maybe a careful definition could require that $f$ is also, in some sense, independent of $G$ (except that $C$ must be the edge set of some cut in $G$)? – Neal Young Apr 23 at 20:12
• Okay, consider $f$ s.t.~$f(C)$ is zero unless $|C|$ is between $k$ and $k^3$ for some $k$ that is a tower of twos, e.g., in the sequence $$2, 2^2, 2^{2^2},\ldots$$ in which case $f(C) = -|C|$. Essentially, this problem is hard (equivalent to Max Cut) for inputs with size close to a tower of twos. It surely (?) won't be in P because for those inputs it is hard, but it won't be NP-hard because the input sizes for which it is hard are quite sparse... Or something like that should work, anyway... – Neal Young Apr 24 at 23:30