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

Is anything known about this?

  • 1
    $\begingroup$ 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. $\endgroup$ – Neal Young Apr 20 at 20:31
  • $\begingroup$ @Neal Young It is indeed true that almost any problem in NP can be generalized this way. The conjecture, however, does not claim that dichotomy applies to all of them. It deals only with the case based on graph cuts, which has much more structure than a generic NP-problem. $\endgroup$ – Andras Farago Apr 22 at 13:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Neal Young Apr 23 at 14:36
  • 1
    $\begingroup$ 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$)? $\endgroup$ – Neal Young Apr 23 at 20:12
  • 1
    $\begingroup$ 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... $\endgroup$ – Neal Young Apr 24 at 23:30

Your Answer

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

Browse other questions tagged or ask your own question.