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 can 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$. A set of edges $E_{ab}$ between the two sets is defined as $(u,v) \in E_{ab}: (u \in V_a, v \in V_b) \lor (u \in V_b, v \in V_a)$
The cost function $C$ is described 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)}$$
We can also define the cost $C_P$ of a path $P : v_1, v_2, \dots, v_n$ using the same rules:
$$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})}$$
Now, thanks to the user saisandeep, 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 with the shortest and longest possible path (or at least I hope that I did): 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 graph $G'$ is still a DAG, so both shortest and longest path can be found in polynomial time.
But what happens if I want to minimize the cost $C$ and at the same time restrict that the cost $C_P$ of the longest path must be below some maximal acceptable cost $c_{max}$?
Or the other way around: minimize the cost $C_P$ of the longest path, but keep the overall cost $C$ below $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 longest path).
Thanks in advance for any help.
