How to determine if this problem is NP-HARD or NP-COMPLETE?

Question

Suppose that I have a pool with N nodes and I have to move the nodes one by one to another pool. For each move, consider a value on the edge linking the two pools. The goal is to find a order of nodes (for the N nodes) that minimizes the overall cut weights between the two pools.

Is this considered a scheduling problem? If so what kind of scheduling problem?

Is it NP-complete or NP-hard?

Here is a pictorial explanation of the problem:

Answer 1

If only a subset of nodes is to be transfered, and that the cardinality of this subset is undefined, then I agree with @LocalSolver. Otherwise (if all nodes have to be transfered $1$ by $1$), I believe the problem is not NP-hard (nor NP-complete):

Consider the following graph :

1. Create a first layer with the $n$ nodes.
2. Create a second layer with $n \times n$ nodes : $1.1, 1.2, ...,1.n,...,n.1,n.2, n.n$. Link node $i$ to $i.1,...,i.n$ forall $i=1,...,n$.
3. Create a third layer with $n$ nodes. Link nodes $i.j$ from layer $2$ to node $j$ from layer $3$, forall $i=1,...,n$, $j=1,...,n$.
4. Create a source node linked to layer $1$ and a sink node linked to layer $3$. Each of these edges have a flow that must equal exactly $1$.

The graph is illustrated bellow:

Now, a flow in this graph is a feasible solution of your problem (if my understanding is correct). Layer $2$ will give you the order of the transfers. For example, if edge $(1,1.3)$ is used, node $1$ will be transfered in 3rd position. The third layer ensures there is exactly $1$ node that is transfered per iteration.

To have the cheapest solution, add the cost of the cut on the edges linking layers $1$ and $2$.

Therefore your problem is not NP-complete, nor NP-hard, as flow problems can be solved in polynomial time.

Answer 2

As nicely mentioned above by @Kuifje, the problem can be reduced to a minimum-cost maximum flow problem if all the nodes have to be transferred.

If only a subset of the nodes has to be transferred then this is a graph partitioning problem known: partitioning the vertices of a graph into two subsets such that the weight of the cut between the two subsets is minimum. It was proved NP-hard; the proof is given in the famous Garey & Johnson's book on computational complexity theory.

Answer 3

As I did not see how one would have to choose the weights in @Kuifje answer I started thinking about the problem as well and I came to the conclusion that it is NP hard.

The proof uses reduction of graph partitioning and goes as follows.

Let $G = (V,E)$ with $n:=|V|$ even be the graph that we want to find the minimal graph partitioning of. Create an instance of the above problem by adding an extra node $r$ and edges $\{r,v\}$ for all $v\in V$. Let the weights of the edges be $c(e) = \begin{cases} 1 & \text{if } e\in E \\ n & \text{if } r\in e\end{cases}$. Thus all the original edges have weight $1$ and the newly added edges have weight $n$.

As we are minimising the maximum cut it is easy to see that $r$ has to be moved after exactly half of the nodes in $V$ were moved (if this is not clear I can elaborate on it). Let $V', V''$ be the partition of $V$ we get from this. The weight of the cut we have at this point is then $n^2/2 + C(V', V'')$, where $C(V', V'')$ is the number of edges between $V'$ and $V''$. As the solving the above problem would minimise this cost it would also minimise the graph partitioning problem.

Let me know if any of the steps were unclear or whether I did any mistakes.