An answer in it's possible for a s-t path to include all without demanding sequential appearance of 's vertices (For example a path of the form when , and .
The principle is creating a new graph in which paths which don't use 's vertices will become longer.
Let us define the graph such that (means we create tagged versions of each and . This results in increasing paths which does not use , a simple example: , are two paths between when in the new graph the corresponding paths are and .
- Before we are getting started, in order to avoid the "" phenomenon which occurs when dealing with number of vertices and number of edged ( edges vertices) we will relate to the number of vertices instead of the number of edges, this is possible because the edges are not weighted).
- Another notation issue, in case , appears in as , otherwise it appears in as . Just to make things more clear I assume , in case one can flip every appearance of in the next propositions with .
- Denote the number of vertices in a shortest path in .
- We may make the assumption that otherwise there is no shortest path which includes all 's vertices.
- proposition 1 - Each pair of corresponding paths in respectively includes the same number of vertices from .
proposition 2 - There is a shortest path which includes all 's vertices in There is a path in with vertices.
- Due to definition 's vertices are not duplicated, thus a vertex in appears only once in and vice versa a vertex in appears only once in which induces from shrinking back any edge to the vertex .
- : let a shortest path in which includes all 's vertices. Then induces a path which has vertices. From the assumption and |\gamma(s,t)|=\delta (shortest path in ) we get: as needed.
- Denote a path with vertices the induced in includes from proposition 1 we know that and has the same number of vertices from . So let us assume that includes vertices from so total number of vertices is:
- which can't be true becasue delta is the minimal number of vertices in path in .
- Run DFS from in , define . (+1 for the number of vertices)
- In case finish with negative return value.
- Create as mentioned.
- Run from in if (-1 cause DFS returns the number of edges and we sorked with number of vertices and already added 1 to in to define ) return positive value, otherwise return negative value.
Complexity - Creating and DFS runs takes each therefore in total.
Correctness - from proposition .
I don't think this proposition is needed, but if one asks why the second run over can't result in a with less then vertices:
- Proposition 3 - There is no path in such that (Reminder, we are measuring vertices number, not edges number).
- proof: Let us assume there is such a . Thus the number of vertices in is , so we may conclude that the induced path in has vertices because each vertex which is not in appeared twise in . So we leran that: which contradicts the assumption that a shortest path in has vertices.