1
$\begingroup$

Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. There are directed edges from the $s$ to all vertices in partition $0$. There are directed edges from all vertices in partition $k$,, ie, the last partition to $t$. $G$ is layerwise complete that is, in addition to the above, there is a directed edge from all vertices in partition $i$ to all vertices in partition $i+1$, ie, adjacent partitions form complete bipartite graphs. An edge between any two nodes is labeled with a negative integer value or with $0$.

There could also be directed edges between nodes in partitions $m$ and $n$ where $1 \leq m, n \leq k, m \lt n, n \neq (m+1)$, and labeled with a negative value. This is depicted in the following figure where there are two edges between partition $1$ and partition $3$ indicated with dashed lines. Non adjacent partitions do not form complete bipartite graphs. They only comprise edges as indicated. In the figure, the edge labels are shown with negative values, wherever edges are not labeled with values, they are labeled with $0$ by default.

enter image description here

Consider all paths from $s$ to $t$. The length of this path would be calculated as the addition of all the integer labels of the nodes on this path and the addition of the edge labels if there is an edge between any pair of vertices in this path. For example, the length of the path taking the first vertex from each partition would thus be $0 + 50 + 30 + 50 + 0 -8$, where the negative value of $-8$ corresponds to the edge between nodes labeled with $50$ and $50$. Similarly, if we took the first vertex from partition $1$, the last vertex from partition $2$ and the first vertex from partition $3$, the length of this path would be $0 + 50 + 40 + 50 + 0 - 6$, where the $-6$ value corresponds to the edge between the first vertex in partition $1$ and partition $2$. The $0$ values correspond to the source and sink vertices.

Find the shortest path from $s$ to $t$ taking exactly one vertex from each $k$-partition where the length would be calculated as described.

Attempt : I converted the node weights for a pair $(a, b)$ into edge weights where each edge weight would be the sum of the node value of $b$ deducting the edge cost between $a$ and $b$. This works for edges between successive partitions and produces the correct shortest path in cases where the edges are only between such. However, if I use the same approach for edges between different non successive layers it doesn't work. What would be an algorithm to find the shortest path and the transformation?

Improve this question
$\endgroup$
3
  • $\begingroup$ What have you tried? Where did you get stuck? $\endgroup$
    – Yuval Filmus
    May 19, 2019 at 7:24
  • $\begingroup$ Are you aiming for an algorithm or a hardness proof? $\endgroup$
    – Yuval Filmus
    May 19, 2019 at 7:30
  • $\begingroup$ @YuvalFilmus I have updated what I have tried, I am looking for an algorithm if indeed this does not turn out to be a hard problem. If so, possible pointers towards an algorithm $\endgroup$
    – kauray
    May 19, 2019 at 8:14

1 Answer 1

Reset to default
2
$\begingroup$

Your problem is NP-hard, by reduction from clique. Given a graph $G=(V,E)$ and a number $k$, we construct a graph with $k$ internal layers, each containing $|V|$ vertices. All vertices in a layer are connected to all vertices in the following layer. The weight of an edge is $0$ if the corresponding edge is not in $G$, and $-1$ otherwise. We also add shortcut edges corresponding to edges in $G$ with weight $-1$. The graph $G$ has a $k$-clique iff the shortest path in the new graph has length $-k(k-1)/2$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Does the number $k$ represent the number of layers in the original graph? $\endgroup$
    – kauray
    May 30, 2019 at 9:58
  • $\begingroup$ It’s the size of the clique we’re trying to find in the original graph. $\endgroup$
    – Yuval Filmus
    May 30, 2019 at 9:59
  • $\begingroup$ Okay, I get it. I get the intuition behind clique, essentially the original graph in the problem can be viewed as complete, with all non displayed edges having edge weight $0$. How does the shortest path length come up to $-k(k-1)$? $\endgroup$
    – kauray
    Jun 1, 2019 at 5:37
  • $\begingroup$ That’s a question for you. $\endgroup$
    – Yuval Filmus
    Jun 1, 2019 at 5:38
  • $\begingroup$ I am getting $-k(k-1) / 2$ ? $\endgroup$
    – kauray
    Jun 2, 2019 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.