1
$\begingroup$

I'm stuck on Part 1, I can't find it inductively. The distance from $$[k, k + 1]$$ is going to be a non-zero positive value with a vertex. Therefore, there is going to be a positive edge weight from $$w(uv)$$ that goes from $$[k, k + 1].$$ Therefore, there exists a v on the set of V such at $$A[u, k + 1] = A[v, k] + w(uv).$$

The Problem

Given an undirected graph $G = (V, E)$ with positive edge weights $w(e)$ for each edge $e \in E$, we want to find a dynamic programming algorithm to compute the longest path in $G$ from a given source $s$ that contains at most $n$ edges.

To do this first define $A[v, k]$ as the weight for the longest path from node $s$ to node $v$ of at most $k$ edges.

  1. First we need to prove an optimal sub-structure by induction. Show that if $A[v, k]$ is the weight of the longest path, then for all $u \in V$, there exists a $v \in V$ such that $A[u, k + 1] = A[v, k] + w(uv)$.
  2. Describe a dynamic programming algorithm that finds the optimal length using part 1. Specifically: describe (1) the OPT recurrence (2) the running time of the iterative solution for computing the OPT table.
$\endgroup$
3
  • $\begingroup$ Do u understand what the entries of the matrix mean? $\endgroup$ Commented Nov 4, 2021 at 17:55
  • $\begingroup$ Matrix, I believe it's a graph and not a matrix? $\endgroup$ Commented Nov 4, 2021 at 17:56
  • $\begingroup$ $A$ is a matrix, $G$ is a graph. $\endgroup$ Commented Nov 4, 2021 at 18:13

1 Answer 1

0
$\begingroup$

We would like to know what is the maximum weight path of length at MOST $k+1$ from source $s$ to vertex $u$. Obviously such a path must exist (assuming connected).

Now, assume such a path EXIST (we know nothing more!!), and we can describe the path by the sequence of vertices it goes through, that is, path $p_1:=\{s,v_0,...,v\}$. Note that we don't actually know the sequence of vertices, just that if such a path exist then it must have a sequence of vertices that describe the path.

Now, consider the last vertex on said sequence before $v$. Call it $u$. Of course, the path (up to $u$) can have a length of AT MOST $k$. Note that from the sequence, edge($u$,$v$) is in the maximum weight path to $v$ (that has length at most $k+1$).

I'm going to show why the weight of the path $p_1$ minus the edge($u$,$v$) is also the entry of $A[u,k]$. That is, the path $p_1$ minus the edge($u$,$v$) (let's call this $p_2$) is the maximum weight path from the source $s$ to vertex $u$ of length at most $k$.

Suppose $p_2$ is not the maximum weight path from $s$ to $u$. That is, there exist path $p_3$ that has a larger weight, and it has at most $k$ edges. But then $p_3$ added with edge($u$,$v$) has larger weight than $p_1$ (our maximum weight path from $s$ to $v$ with length at most k+1). Thus we have a contradiction.

To recap: we have proved that the weight of the path $p_2$ must be the entry of $A[u,k]$. But what is the weight of path $p_2$? Remember that we get $p_2$ by deleting edge($u$,$v$) from path $p_1$. Of course, it means that the weight of $p_2$ is weight of $p_1$ minus the weight of edge($u$,$v$).

$$ A[v,k+1] - w(uv) = A[u,k], \implies A[v,k+1] = A[u,k] + w(uv) $$

$\endgroup$
8
  • $\begingroup$ Feel free to ask further questions $\endgroup$ Commented Nov 4, 2021 at 18:25
  • $\begingroup$ Well but we have to be careful here though. What if $p_3$ contains the vertex $v$? Your argument carries through if we replace 'path', where repeating vertices are not allowed, with 'walk', where repeating vertices are allowed. $\endgroup$
    – Mike
    Commented Nov 4, 2021 at 19:42
  • $\begingroup$ Meanwhile, unless P=NP, there is no algorithm to find the longest path with at most $k$ edges in a weighted graph starting from a vertex $s$; if so, then there would be an algorithm that would find a Hamiltonian path starting from a vertex $s$. Indeed, ask for the longest path starting from $s$ that has at most $|V(G)|$ vertices, where the weight of each edge in $G$ is exactly $1$. $\endgroup$
    – Mike
    Commented Nov 4, 2021 at 19:47
  • $\begingroup$ @Mike I.. considered a directed simple graph. I will try to correct the answer $\endgroup$ Commented Nov 4, 2021 at 20:17
  • $\begingroup$ @Mike is the question correct? The first part is the same as asking "show that for any vertex $v$, that has a maximum weight path $p_v$ of length at most $k+1$, at least one of it's neighbours $u$ must have the same path $p_v$ minus one edge($u$,$v$) as it's maximum weight path of length at most $k$". If that re-wording is correct, I can draw a graph where that statement is not true. $\endgroup$ Commented Nov 4, 2021 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .