Question

shortest_path
spring17_a

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

2

Answers

An answer in it's possible for a s-t path to include all uUu\in U without demanding sequential appearance of UU's vertices (For example a path of the form su1w1w2u2ts-u_1-w^1-w^2-u_2-t when d(s,t)=5d(s,t)=5 , w1,w2/Uw^1,w^2\notin U and u1,u2Uu_1,u_2\in U.

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

Let us define the graph G=(V,E)G' = (V',E') such that V(VU)V\cup(V\setminus U)' (means we create tagged versions of each vVU)v\in V\setminus U) and E={(v,v):vVU}{(v,w):(v,w)E}{(u,v):uU,(u,v)E}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 uUu\in U, a simple example: v1uv2v_1 - u -v_2 , v1xv2v_1 - x - v_2 are two paths between v1,v2v_1, v_2 when uU,x/Uu\in U , x\notin U in the new graph the corresponding paths are v1v1uv2v2v_1-v_1'-u-v_2-v_2' and v1v1xxv2v2v_1-v_1'-x-x'-v_2-v_2'.

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

Algorithm:

  1. Run DFS from ss in GG, define δ=ds(t)+1\delta = d_s(t) +1. (+1 for the number of vertices)
  2. In case U>δ|U| > |\delta| finish with negative return value.
  3. Create GG' as mentioned.
  4. Run DFSDFS from ss in GG' if ds(t)=2δU1d_{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 ds(t)d_s(t) in GG to define δ\delta ) return positive value, otherwise return negative value.

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

Correctness - from proposition 22.

Comments:

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

  1. Proposition 3 - There is no γ(s,t)\gamma'(s,t') path in GG' such that γ1(s,t)<2δU|\gamma_1(s,t)| < 2\delta -|U| (Reminder, we are measuring vertices number, not edges number).
    • proof: Let us assume there is such a γ(s,t)\gamma'(s,t'). Thus the number of vertices in γ(s,t)\gamma'(s,t') is γ(s,t)U+γ(s,t)UVcomplement!!!cγ(s,t)U+(γ(s,t)γ(s,t)U)|\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 γ(s,t)\gamma(s,t) in GG has γ(s,t)U+(γ(s,t)γ(s,t)U)2|\gamma'(s,t')\cap U|+\frac{(|\gamma'(s,t')|-|\gamma'(s,t')\cap U|)}{2} vertices because each vertex which is not in UU appeared twise in γ(s,t)\gamma'(s,t'). So we leran that:γ(s,t)=γ(s,t)U+(γ(s,t)γ(s,t)U)2=(γ(s,t)+γ(s,t)U)21γ(s,t)+U2<2(2δU)+U2=δ|\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 GG has δ\delta vertices.
      • 1{\le_1} γ(s,t)UUγ(s,t)UU\gamma'(s,t')\cap U \subseteq U \Rightarrow |\gamma'(s,t')\cap U|\le |U|
      • <2<_2 γ1(s,t)<2δU|\gamma_1(s,t)| < 2\delta -|U|
3

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

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

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

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

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

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

מצד שני, אם קיים מסלול קצר ביותר מ-ss ל-tt שעובר בכל צמתי UU אז נסמן ב-u1,,uku_1,\ldots,u_k את הצמתים ב-UU לפי הסדר שהמסלול מבקרן בהם וקל לראות שתכונות 1. 2. ו-3. מתקיימות.

האלגוריתם:

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

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

סיבוכיות:

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

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

-2
Feedback