<p>Let <span class="math-container">$G$</span> be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut <span class="math-container">$C\subseteq E(G)$</span>, such that <span class="math-container">$|C|$</span> is minimum.</p>

<p>Let us generalize it the following way: let <span class="math-container">$f$</span> be a polynomial time computable function on the subsets of the edge set, and we look for a cut <span class="math-container">$C$</span>, such that <span class="math-container">$f(C)$</span> is minimum. </p>

<p>Depending on the function, this problem can be easy or hard:</p>

<ol>
<li><p>If <span class="math-container">$f$</span> depends only on <span class="math-container">$|C|$</span>, and it is a monotone increasing function of <span class="math-container">$|C|$</span>, then <span class="math-container">$f(C)$</span> will still be minimized by a minimum cut, which can be found in polynomial time.</p></li>
<li><p>If <span class="math-container">$f$</span> depends only on <span class="math-container">$|C|$</span>, and it is a strictly monotone decreasing function of <span class="math-container">$|C|$</span>, then minimizing <span class="math-container">$f(C)$</span> is equivalent to finding a maximum cut, which is known to be NP-hard (or, regarding decision, rather than search, it is NP-complete).</p></li>
</ol>

<p><strong>Question:</strong> 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?</p>

<p>Furthermore, I would like to propose the following conjecture:</p>

<p><strong>Conjecture:</strong> 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). </p>

<p>Is anything known about this?</p>

CC BY-SA 4.0
2019-04-20T20:31:56.950Z
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
CC BY-SA 4.0
2019-04-22T13:06:41.837Z
@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.
Andras Farago
CC BY-SA 4.0
2019-04-22T18:46:48.513Z
But isn't the example I gave of that type?  In that construction, any $C$ (except the empty set, which you could easily work around) is a cut in the given graph.  Perhaps you have in mind $s$-$t$ cuts for given vertices $s, t$, but, if you do, the construction could easily be modified to be consistent with that restriction, if you like.
Neal Young
CC BY-SA 4.0
2019-04-22T20:01:58.220Z
@Neal Young: Yes, it seems, you are right. Regarding the conjecture, if one encodes an NP-intermediate problem according to your construction, then we get a generalized minimum cut problem in which deciding whether a cut $C$ exists with $f(C)=0$ has NP-intermediate complexity, thus disproving the dichotomy conjecture. Perhaps it may still be made meaningful, if we restrict the function in some way. For example, what happens if the function may only depend on the size $|C|$ of the cut?
Andras Farago
CC BY-SA 4.0
2019-04-23T14:36:47.143Z
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
CC BY-SA 4.0
2019-04-23T18:26:07.587Z
@Neal Young: It is interesting! It seems that even if $f(C)$ depends only on $|C|$, dichotomy is still unlikely to follow. However, both of your constructions involve highly disconnected graphs. What if the underlying graph is required to be a connected simple graph (no parallel edges)?
Andras Farago
CC BY-SA 4.0
2019-04-23T20:12:01.803Z
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
CC BY-SA 4.0
2019-04-24T15:07:43.917Z
@Neal Young: What I originally had in mind is this. Let $h$ be a _fixed_ function that maps integers to integers, and let $f(C)=h(|C|)$, for any edge set $C$, whether it is a cut or not. Note that this $f$ is independent of $G$, since $h$ is a _fixed_ function. Then the "generalized min cut" problem is this: find an edge set $C$, such that $C$ is a cut in $G$, and $f(C)$ is minimum. Could it be that this problem on connected simple graphs still has a dichotomy? (I guess, in view of your examples, the likely answer is no, but I am not sure.)
Andras Farago
CC BY-SA 4.0
2019-04-24T23:30:54.157Z
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
CC BY-SA 4.0
2019-04-25T02:33:46.057Z
@Neal Young: Great example! It seems to me now that apparently every NP-hard NP-optimization problem can be made NP-intermediate by changing the objective function in this way.
Andras Farago
<cc.complexity-theory><graph-theory><graph-algorithms><np-hardness>
Minimum cut with nonlinear objective function
Andras Farago
# Minimum cut with nonlinear objective function

(Asked by: username_0 on 2019-04-19)

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?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, np-hardness

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 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.  
> **username_1**: But isn't the example I gave of that type?  In that construction, any $C$ (except the empty set, which you could easily work around) is a cut in the given graph.  Perhaps you have in mind $s$-$t$ cuts for given vertices $s, t$, but, if you do, the construction could easily be modified to be consistent with that restriction, if you like.  
> **username_0**: @username_1: Yes, it seems, you are right. Regarding the conjecture, if one encodes an NP-intermediate problem according to your construction, then we get a generalized minimum cut problem in which deciding whether a cut $C$ exists with $f(C)=0$ has NP-intermediate complexity, thus disproving the dichotomy conjecture. Perhaps it may still be made meaningful, if we restrict the function in some way. For example, what happens if the function may only depend on the size $|C|$ of the cut?  
> **username_1**: 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.  
> **username_0**: @username_1: It is interesting! It seems that even if $f(C)$ depends only on $|C|$, dichotomy is still unlikely to follow. However, both of your constructions involve highly disconnected graphs. What if the underlying graph is required to be a connected simple graph (no parallel edges)?  
> **username_1**: 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$)?  
> **username_0**: @username_1: What I originally had in mind is this. Let $h$ be a _fixed_ function that maps integers to integers, and let $f(C)=h(|C|)$, for any edge set $C$, whether it is a cut or not. Note that this $f$ is independent of $G$, since $h$ is a _fixed_ function. Then the "generalized min cut" problem is this: find an edge set $C$, such that $C$ is a cut in $G$, and $f(C)$ is minimum. Could it be that this problem on connected simple graphs still has a dichotomy? (I guess, in view of your examples, the likely answer is no, but I am not sure.)  
> **username_1**: 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...  
> **username_0**: @username_1: Great example! It seems to me now that apparently every NP-hard NP-optimization problem can be made NP-intermediate by changing the objective function in this way.  

---

## 0 answers

