4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, graph and weights are fixed, the problem is to find subsets $V_a$ and $V_b$. I've edited the question, should be clearer now. I assume that "the longest path" = the path with the highest cost. $\endgroup$ – marszall87 Feb 16 '17 at 18:26
  • $\begingroup$ OK, thanks, that helped. Now I'm a bit confused about the relationship between cost and length of a path. What does "longest path" mean? It means "the path whose cost is the highest"? Are there some restrictions, e.g., the path has to start at some vertex in $V_A$ and end at some vertex in $V_B$, or is this taken over all possible paths? What does "find the subsets $V_A,V_B$ with the shortest possible path" mean? Does it mean find subsets $V_A,V_B$ such that the minimum of $C_P$ over all paths $P$, is the smallest possible? $\endgroup$ – D.W. Feb 16 '17 at 18:36
  • $\begingroup$ Yes "longest path" means "the path whose cost is the highest". So actually the problem is to find a subsets $V_A, V_B$ such that the maximum of $C_P$ over all paths $P$ is the smallest possible. $\endgroup$ – marszall87 Feb 22 '17 at 21:07
  • $\begingroup$ I suggest editing the question to make that clearer: e.g., replace "longest" with "highest-cost", and explicitly clarify that your constraint is that all possible paths have cost at most $c_\max$ (or that your objective function is the maximum cost, taken over all paths). $\endgroup$ – D.W. Feb 22 '17 at 21:14

Your Answer

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

Browse other questions tagged or ask your own question.