# Partition a graph such that each subgraph fits the machine constraint

Lets assume there is no upper limit on number of machines.

Here are the goals of partition:

1. Each node in the graph has a weight. There is an upper limit on total weight stored on a machine. All the nodes are not fitting on one machine, hence we are starting with partition.

2. When we store an edge on a machine, then the weight of both nodes is being placed on that machine.

3. All machines are same and have a capacity c

4. Each node should have all its edges on a single machine. If sum of weights of all neighbors of a node is greater than c, only then its data should be split on more than one machine. In which case, minimize the number of machines to which data is split.

5. Edge data can be repeated across machines. This relaxation is necessary to satisfy the condition that each node of the graph should have all its neighbors information co-located on a single machine in the network. (unless not possible)

6. Minimize the total number of machines used.

Corollary: If each node's edges data can be fitted on one machine, then to access any node's edges information we will only have to access one machine on the network.

• You haven't yet completely described an objective function to minimise or maximise, though it sounds like you want to minimise the total number of machines used. Is that right? In that case, this is NP-hard, since Partition can be reduced to it: make a single edge for each number, and set the machine capacity to half the total weight; then it's possible to use just 2 machines if and only if the numbers can be partitioned into equal-sum sets, otherwise at least 3 machines are needed. – j_random_hacker Feb 28 '18 at 7:08
• @j_random_hacker you are right about the objective function. I have rephrased the question. Can you explain more how this problem maps to NP-Hard? Thanks – Asad Iqbal Feb 28 '18 at 16:14
• Thanks for the update, though I'd suggest keeping just sentence 1 of point 4, since the rest seems either in conflict with, or subsumed by, your overall goal in point 6. The hardness proof sketch I gave shows how instances of another problem (here, Partition) can be mapped to instances of your problem: the idea here is that, if an efficient algorithm existed to solve all instances of your problem, then it could also be used to efficiently solve instances of Partition by using this mapping -- but since we believe Partition to be hard to solve, your problem must be at least as hard. – j_random_hacker Feb 28 '18 at 17:05