5
$\begingroup$

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:

enter image description here

Improve this question
$\endgroup$
3
  • $\begingroup$ How does the order matter ? $\endgroup$ – Kuifje Oct 26 '20 at 8:52
  • $\begingroup$ Sorry but i focus on mimimizing the maximum cut weight while moving, the nodes in each pool are linked. ie if i have moved( 1 and 3 )and 2 and 4 remains in the original pool will not have the same link weight as i have moved( 2 and 3 ) for example. $\endgroup$ – fathese Oct 26 '20 at 8:58
  • $\begingroup$ I added an image in my question to explain my problem. please refer to it $\endgroup$ – fathese Oct 26 '20 at 9:56
5
$\begingroup$

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:

enter image description here

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Maybe I am overseeing something obvious, but how exactly do I choose the weights for the edges in order to minimize the maximal occurring cut? $\endgroup$ – SimonT Nov 24 '20 at 11:16
  • $\begingroup$ I may have misunderstood, but OP states that "for each move, consider a given value on the edge linking the two pools." So the weights are given (?). Also, it we want to know if it is NP-complete, we can leave out the weights as we are only interested in the decision version of the problem. $\endgroup$ – Kuifje Nov 24 '20 at 13:02
  • $\begingroup$ From my understanding the image in the OP question states that we are want to find find the order in which to move the nodes such that the maximal cut occurring between the two pools is minimized. $\endgroup$ – SimonT Nov 24 '20 at 13:07
  • $\begingroup$ For NP-completeness, minimization is not relevant. And for the weights, I believe they are given. Maybe OP can clarify, because the problem is exclusively NP-hard, or not... $\endgroup$ – Kuifje Nov 24 '20 at 13:10
  • $\begingroup$ In order to be able to say whether it is NP complete or not it needs to be in NP and thus a decision problem. The way it is stated by OP it is a minimisation problem. For me the logical corresponding problem in NP would be the one: Is there a solution such that the maximal cut is smaller than $k$ for a given $k$. $\endgroup$ – SimonT Nov 24 '20 at 13:15
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The question is not $100\%$ clear, but it seems all nodes have to be transfered one by one. In this case I don't think it is a parititioning problem. Otherwise I agree with you! $\endgroup$ – Kuifje Oct 26 '20 at 9:44
  • $\begingroup$ I added an image in my question to explain my problem. please refer to it $\endgroup$ – fathese Oct 26 '20 at 9:57
  • $\begingroup$ the objective is to find a vertices order so i think it is a scheduling problem rather than graph partitioning problem $\endgroup$ – fathese Oct 26 '20 at 11:03
  • 1
    $\begingroup$ Thank you very much for your comment, Kuifje and fathese. The problem is now clear to all of us. If all the nodes have to be transferred, then Kuifje gives an elegant, efficient solution approach, that you can solve as an LP or by using a maximum flow algorithm. Will change our answer accordingly. $\endgroup$ – LocalSolver Oct 26 '20 at 12:36
  • $\begingroup$ So, in conclusion. it s a scheduling problem ? how to determine NP hard or not? $\endgroup$ – fathese Oct 26 '20 at 18:43
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.