Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We want to divide vertices in two subsets $V_a$ and $V_b$, such that $V_a \cap V_b = \emptyset$ and $V_a \cup V_b = V$. The set of edges $E_{ab}$ between the two sets is defined as$$E_{ab} = \{ (u,v) : (u \in V_a, v \in V_b) \lor (u \in V_b, v \in V_a)\}.$$A cost function $C$ is defined as follows:$$C = \sum_{v \in V_a}{w_a(v)} + \sum_{v \in V_b}{w_b(v)} + \sum_{(u,v) \in E_{ab}}{t(u,v)}$$Define the cost $C_P$ of a path $P$ traversing vertices $v_1, v_2, \dots, v_n$ to be:$$C_P = \sum_{v \in V_a \land v \in P}{w_a(v)} + \sum_{v \in V_b \land v \in P}{w_b(v)} + \sum_{(v_i, v_{i+1}) \in E_{ab} \land v_i \in P \land v_{i+1} \in P}{t(v_i,v_{i+1})}$$I know that the problem of finding the subsets $V_a$ and $V_b$ such that the $C$ function is minimized can be reduced to minimum cut, so it's in P.I've also managed to come up with the solution to find the subsets $V_A,V_B$ with the path with highest possible cost: we can transform the graph $G$ to graph $G'$ in such a way that for every vertex $v$ we create two vertices $v_a$ and $v_b$ with appropriate weights (from $w_a$ and $w_b$ functions respectively), and for every edge $(u,v)$ we create two edges with weight $0$: $(u_a,v_a)$, $(u_b,v_b)$; and two edges with weight $t(u,v)$: $(u_a,v_b)$, $(u_b,v_a)$. In other words, we're creating graph $G'$ that covers every possible path for every division of $V$.The problem can be reduced to finding the longest path in a graph. The graph $G'$ is still a DAG, so the longest path can be found in polynomial time.Now, the multi-objective problem that I'm trying to solve is to find subsets $V_a$ and $V_b$ that minimize the cost $C$ but with a constraint that the cost $C_P$ of every possible path is not greater than maximal acceptable cost $c_{max}$. Graph $G = (V, E)$ and all weight functions are given as an input and fixed.Or the other way around: minimize the maximum cost $C_P$ of every possible paths, but constrain the overall cost $C$ to be not greater than $c_{max}$.How should I approach this problem? Are there any generic ways to prove complexity of such multi-objective problems?The best answer that I've found in literature is that multi-objective optimization problems are generally hard which is not very helpful.My real-life application of this problem is to allocate software components on two heterogenous machines (hence two weight functions) connected via network (hence edge weights) and minimize both energy use (the $C$ function is basically the CPU time + transfer time) and the computation time (the path with the highest cost).Thanks in advance for any help.
Graph optimization problem with multiple objectives/constraints
graph theory;optimization;np hard;partitions