Given a graph $G$, I want to find $2$ (or $k$) node-disjoint paths with minimum total cost (or minimum maximum cost). The problem is a classical problem, but I have the following non-trivial setting. The topology is not fixed. Each node $v$ can establish $\le k_i$ edges to a set of nodes (the cost of each potential edge is given as parameters). Only the established edges can be used. Therefore, I need to jointly decide which edges to establish and search the optimum node-disjoint paths over these edges. How to solve this variant?
3
-
$\begingroup$ Taking as implicit that every vertex should be in one of the two paths, you can only have a maximum of 4 vertices for which $k_i = 1$, because such vertices must be end-points of their paths. Therefore you add at worst a factor of $n^4$ to the asymptotic cost of the classic problem by adding an outer loop which iterates over each possible edge assignment to these obligate end-points. $\endgroup$– Peter TaylorCommented Dec 1, 2021 at 10:07
-
$\begingroup$ thankyou Peter, but why every node should be in one of the two paths? $\endgroup$– lchenCommented Dec 1, 2021 at 11:47
-
$\begingroup$ It must be an interesting problem, or you wouldn't ask about it, and that was the least unreasonable assumption to make it interesting. The next would be that edges can have negative costs. If neither of those hold, a path of zero edges has cost 0... $\endgroup$– Peter TaylorCommented Dec 1, 2021 at 12:04
Add a comment
|