### Question

shortest_path
spring17_a

נתונים גרף מכוון $G = (V,E)$, שני צמתים $s,t \in V$ וקבוצת צמתים $U \subseteq V$. הציעו אלגוריתם המכריע האם קיים מסלול קצר ביותר מ-$s$ ל-$t$ שעובר דרך כל צמתי $U$.

2

An answer in it's possible for a s-t path to include all $u\in U$ without demanding sequential appearance of $U$'s vertices (For example a path of the form $s-u_1-w^1-w^2-u_2-t$ when $d(s,t)=5$ , $w^1,w^2\notin U$ and $u_1,u_2\in U$.

The principle is creating a new graph in which paths which don't use $U$'s vertices will become longer.

Let us define the graph $G' = (V',E')$ such that $V\cup(V\setminus U)'$ (means we create tagged versions of each $v\in V\setminus U)$ and $E' = \{(v,v') : v\in V\setminus U\} \cup \{(v',w): (v,w)\in E \} \cup \{ (u,v) : u\in U , (u,v)\in E \}$. This results in increasing paths which does not use $u\in U$, a simple example: $v_1 - u -v_2$ , $v_1 - x - v_2$ are two paths between $v_1, v_2$ when $u\in U , x\notin U$ in the new graph the corresponding paths are $v_1-v_1'-u-v_2-v_2'$ and $v_1-v_1'-x-x'-v_2-v_2'$.

• Before we are getting started, in order to avoid the "$+1$" phenomenon which occurs when dealing with number of vertices and number of edged ($k$ edges $\Rightarrow$ $k+1$ 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 $t\in U$, $t$ appears in $G'$ as $t$, otherwise it appears in $G'$ as $t'$. Just to make things more clear I assume $t\notin U$, in case $t\in U$ one can flip every appearance of $t'$ in the next propositions with $t$.
1. Denote $\delta$ the number of vertices in a shortest $s-t$ path in $G$.
2. We may make the assumption that $\delta \ge |U|$ otherwise there is no shortest path which includes all $U$'s vertices.
3. proposition 1 - Each pair of corresponding $\gamma, \gamma'$ paths in $G,G'$ respectively includes the same number of vertices from $U$.
• Due to $G'$ definition $U$'s vertices are not duplicated, thus a vertex in $U\cap \gamma$ appears only once in $\gamma'$ and vice versa a vertex in $U\cap gamma'$ appears only once in $\gamma$ which induces from shrinking back any $(v,v')$ edge to the vertex $v$.
4. proposition 2 - There is a shortest $s-t$ path which includes all $U$'s vertices in $G$ $\Leftrightarrow$ There is a $s-t'$ path in $G'$ with $2\delta - |U|$ vertices.
• proof:
• $\Rightarrow$ : let $\gamma(s,t)$ a shortest path in $G$ which includes all $U$'s vertices. Then $\gamma(s,t)$ induces a path $\gamma'(s,t')$ which has $|\gamma(s,t) \cap U| + 2(|\gamma(s,t)| - |\gamma(s,t)\setminus U|) = |\gamma(s,t) \cap U | + 2(|\gamma(s,t)| - |\gamma(s,t) \cap U| )$ vertices. From the assumption $\gamma(s,t)\cap U = U$ and |\gamma(s,t)|=\delta (shortest path in $G$) we get: $|\gamma(s,t) \cap U | + 2(|\gamma(s,t)| - |\gamma(s,t) \cap U| ) = |U|+2(\delta -|U|) = 2\delta -|U|$ as needed.
• $\Leftarrow$ Denote $\gamma'(s,t')$ a path with $2\delta -|U|$ vertices the induced $\gamma(s,t)$ in $G$ includes $|\gamma'(s,t') \cap U| + \frac{|\gamma'(s,t')|- |\gamma'(s,t')\cap U|}{2}$ from proposition 1 we know that $gamma(s,t)$ and $\gamma'(s,t')$ has the same number of vertices from $U$. So let us assume that $\gamma'(s,t')$ includes $k < |U|$ vertices from $U$ so $\gamma(s,t)$ total number of vertices is: $|\gamma'(s,t')\cap U| + \frac{|\gamma'(s,t')|- |\gamma'(s,t')\cap U|}{2} = k +\frac{2\delta -|U| -k}{2} = +\frac{2\delta -|U| + k}{2} <_1 \frac{2\delta}{2} = \delta$
• $<_1$ $-|U| +k < 0$ which can't be true becasue delta is the minimal number of vertices in $s-t$ path in $\gamma$.

Algorithm:

1. Run DFS from $s$ in $G$, define $\delta = d_s(t) +1$. (+1 for the number of vertices)
2. In case $|U| > |\delta|$ finish with negative return value.
3. Create $G'$ as mentioned.
4. Run $DFS$ from $s$ in $G'$ if $d_{s}(t) = 2 \delta -|U| -1$ (-1 cause DFS returns the number of edges and we sorked with number of vertices and already added 1 to $d_s(t)$ in $G$ to define $\delta$ ) return positive value, otherwise return negative value.

Complexity - Creating $G'$ and DFS runs takes $O(E+V)$ each therefore $O(E+V)$ in total.

Correctness - from proposition $2$.

I don't think this proposition is needed, but if one asks why the second $DFS$ run over $G'$ can't result in a $\gamma'(s,t')$ with less then $2\delta - |U|$ vertices:

1. Proposition 3 - There is no $\gamma'(s,t')$ path in $G'$ such that $|\gamma_1(s,t)| < 2\delta -|U|$ (Reminder, we are measuring vertices number, not edges number).
• proof: Let us assume there is such a $\gamma'(s,t')$. Thus the number of vertices in $\gamma'(s,t')$ is $|\gamma'(s,t')\cap U| + |\gamma'(s,t') \cap U^c_{V' complement!!!}| \equiv |\gamma'(s,t')\cap U| + (|\gamma'(s,t')|-|\gamma'(s,t')\cap U|)$ , so we may conclude that the induced path $\gamma(s,t)$ in $G$ has $|\gamma'(s,t')\cap U|+\frac{(|\gamma'(s,t')|-|\gamma'(s,t')\cap U|)}{2}$ vertices because each vertex which is not in $U$ appeared twise in $\gamma'(s,t')$. So we leran that:$|\gamma(s,t)| =|\gamma'(s,t')\cap U|+\frac{(|\gamma'(s,t')|-|\gamma'(s,t')\cap U|)}{2} = \frac{(|\gamma'(s,t')|+|\gamma'(s,t')\cap U|)}{2} \le_1 \frac{|\gamma'(s,t')| + |U|}{2} <_2 \frac{(2\delta -|U|)+|U|}{2} =\delta$ which contradicts the assumption that a shortest path in $G$ has $\delta$ vertices.
• ${\le_1}$ $\gamma'(s,t')\cap U \subseteq U \Rightarrow |\gamma'(s,t')\cap U|\le |U|$
• $<_2$ $|\gamma_1(s,t)| < 2\delta -|U|$
3

נסדר את הצמתים ב-$U$ בסדר לא יורד של המרחק שלהם מ-$s$: $U = \{u_1, \ldots, u_k\}$.

טענה: קיים מסלול כנדרש אמ"מ:

1. $d(u_k) = d(u_1) + k - 1$
2. $(u_i, u_{i+1}) \in E,\; 1 \leq i \leq k - 1$
3. $d(t) = d(u_k) + d(u_k, t)$

הוכחה: אם התנאים מתקיימים אז קיים המסלול הבא:

$s \rightsquigarrow u_1 \to \ldots \to u_k \rightsquigarrow t$

מסלול זה הוא קל ביותר לפי טענות 1. ו-2.

מצד שני, אם קיים מסלול קצר ביותר מ-$s$ ל-$t$ שעובר בכל צמתי $U$ אז נסמן ב-$u_1,\ldots,u_k$ את הצמתים ב-$U$ לפי הסדר שהמסלול מבקרן בהם וקל לראות שתכונות 1. 2. ו-3. מתקיימות.

האלגוריתם:

1. מצא עץ מרחקים קלים ביותר מ-$s$
2. בדוק אם תכונות 1. 2. ו-3. מתקיימות.

נכונות: נובע ישירות מהטענה.

סיבוכיות:

1. מציאת עץ מרחקים קלים - $O(n\log n)$
2. בדיקת התכונות - $O(n + m)$

ובסך הכל - $O(n\log n)$

-2
Feedback