สำหรับข้อนี้ จะเป็นการถามหา shortest path ระหว่างคู่จุด หลาย ๆ คู่ โดยรับประกันว่าถามระหว่างคู่ที่จุดเริ่มต้นอยู่ในเซต $S$ และจุดสิ้นสุดอยู่ในเซต $T$ บนกราฟที่มีเงื่อนไขพิเศษ คือระหว่างจุดเริ่มต้นใด ๆ ไปยังจุดสิ้นสุดใด ๆ จะผ่านจุดยอดอื่น ๆ อย่างน้อย $1\,000$ จุดยอดเสมอ กล่าวคือ $\forall s \in S, \forall t \in T, [udist(s,t) \geq 1\,001]$ และกราฟเป็นกราฟมีน้ำหนัก ไม่ระบุทิศทาง และเชื่อมต่อกัน

สำหรับสัญลักษณ์ในเฉลย กำหนดให้

• $dist(u, v)$ แทนระยะห่างจากจุดยอด $u$ ไปยังจุดยอด $v$ บนกราฟระบุทิศทางที่โจทย์กำหนดมาให้
• $udist(u, v)$ แทนระยะห่างจากจุดยอด $u$ ไปยังจุดยอด $v$ โดยไม่นับน้ำหนัก (กล่าวคือ จำนวนเส้นเชื่อมที่น้อยที่สุดที่เป็นไปได้ของ path จาก $u$ ไป $v$ สำหรับแต่ละ path ใด ๆ)

Observation 1

สังเกตว่า สำหรับกราฟเชื่อมต่อไม่ระบุทิศทางใด ๆ สมมติ $p$ เป็น articulation point ที่แบ่งกราฟออกเป็นหลาย connected component และ $u$ กับ $v$ อยู่คนละ component หลังจากการแบ่งกราฟแล้ว จะได้ว่า path ใด ๆ ที่เชื่อมต่อระหว่าง $u$ กับ $v$ จะต้องผ่าน $p$

หมายเหตุ เราจะกล่าวว่า $p$ เป็น articulation point ของกราฟต่อเนื่องไม่ระบุทิศทาง $G = (V,E)$ ก็ต่อเมื่อ หากนิยาม $E' = \{v \in V | \{p, v\} \in E\}$ (นั่นคือ $E'$ เป็นเซตของเส้นเชื่อมที่ติดกับ $p$) แล้ว $G' = (V, E \setminus E')$ จะเป็นกราฟใหม่ที่ไม่ต่อเนื่อง กล่าวคือ $p$ จะเป็น articulation point ก็ต่อเมื่อ การลบ $p$ ออกจากกราฟทำให้กราฟขาด

ยกตัวอย่างเช่นภาพด้านล่าง

หากพิจารณาทุก path จาก $s$ ไปหา $t$ จะจำเป็นต้องผ่าน $p_1$ แน่ ๆ เพราะเมื่อนำ $p_1$ ออกจากกราฟจะแบ่งกราฟออกเป็นหลายส่วน และทำให้ $s$ กับ $t$ อยู่คนละส่วนกัน

Observation 2

สังเกตว่า สำหรับกราฟ $G = (V,E)$ ที่เป็นกราฟเชื่อมต่อไม่ระบุทิศทางใด ๆ สมมติมีเซต $S \subseteq V$ และ $T \subseteq V$ ที่ $S \cap T = \emptyset$ ถ้า เรารับประกันได้ว่า มี เซต $P \subseteq V$ ที่มีสมบัติ เมื่อนำจุดยอดภายในเซต $P$ ออกจนหมดแล้วทำให้ไม่มี path ใด ๆ เลยที่เชื่อมระหว่าง $s \in S$ ใด ๆ กับ $t \in T$ ใด ๆ (กล่าวคือ $P$ เป็น s-t cut ของกราฟ $G$) แล้ว shortest path จาก $s \in S$ ใด ๆ ไปหา $t \in T$ ใด ๆ จะผ่านอย่างน้อยหนึ่งจุดยอดใน $P$

ยกตัวอย่างเช่นภาพด้านล่าง

หากกำหนดให้ $S = \{s_1, s_2\}$ และ $T = \{t_1, t_2, t_3\}$ และ $P = \{p_1, p_2, p_3\}$ (จะเห็นได้ว่ามีสมบัติข้างต้น คือเมื่อตัด $P$ ออกจากกราฟไปแล้วทำให้ $S$ ไม่สามารถไปหา $T$ ได้เลย) แล้วจะสังเกตได้ว่า shortest path จาก $s \in S$ ใด ๆ ไปยัง $t \in T$ ใด ๆ จะต้องผ่านอย่างน้อยหนึ่งจุดยอดใน $P$

ข้อสังเกตดังกล่าว สามารถคิดต่อได้จากข้อสังเกตแรก หากเราสามารถหาเซต $P$ ที่แบ่งแยกส่วน $S$ ออกจาก $T$ ได้เราก็จะได้ว่ายังไง $P$ ก็เป็นส่วนจำเป็นที่จะต้องใช้ผ่านทาง ระหว่าง $S$ ไปหา $T$

Observation 3

สังเกตว่า สำหรับกราฟใด ๆ สำหรับจุดยอด $s, t$ ที่ $s \ne t$ ใด ๆ ในกราฟ หากสามารถรับประกันได้ว่ามี shortest path อย่างน้อย 1 วิธีที่ผ่านจุดยอด $p$ แน่ๆ เราจะทราบว่า $dist(s, t) = dist(s, p) + dist(p, t)$

ข้อสังเกตนี้ เป็นข้อสังเกตที่สังเกตได้ไม่ยาก แต่มีประโยชน์ต่อข้อนี้มาก

Randomized Solution

เมื่อเราทราบข้อสังเกตทั้ง 3 ข้อแล้ว และพบว่ากราฟนั้นมีระยะห่าง (ไม่นับน้ำหนัก) ระหว่าง $s \in S$ ใดๆ กับ $t \in T$ ใดๆ มาก เราจึงได้ข้อสังเกตเพิ่มเติมว่า น่าจะมีเซต $P$ จาก Observation 2 ที่มีขนาดเล็ก เพราะเส้นทางน่าจะซ้ำกันเยอะ เราจึงทำการสุ่มหา $P$ ที่สอดคล้องกับเงื่อนไขของ Observation 2 ที่มีขนาดเล็กเพียงพอ (หากโชคดีพอจะได้ประมาณ $100$ ถึง $200$ จุดยอด ซึ่งเพียงพอต่อเวลา หรืออีกวิธีคือสุ่มมั่วจำกัดแค่ $100$ จุดยอดโดยไม่สนใจว่าสอดคล้องเงื่อนไขหรือไม่) หลังจากนั้น ทำ Dijkstra's Algorithm โดยหา single source shortest path จาก $p \in P$ แต่ละ $p$ ไปหาทุกจุดยอด เมื่อมีคำถามแต่ละคำถามในรูปแบบ $(s, t)$ เมื่อ $s \in S$ และ $t \in T$ แล้วจะได้ว่า $\min\limits_{p \in P}{dist(p, s) + dist(p, t)}$ เป็นคำตอบ (วิธีการจาก Observation 3)

จะได้ว่าใช้เวลาการทำงานรวมเป็น $\mathcal{O}(|P|M \log N)$ แต่วิธีการนี้ยังไม่ใช่วิธีการที่ผู้เขียนต้องการให้ผ่าน

Min-cut Solution

ปัญหาต่อมาคือเราต้องการหาเซต $P$ ที่มีขนาดเล็ก ๆ และสอดคล้องกับ Observation 2 แน่ ๆ ปัญหานี้มีชื่อเรียกว่า Minimum s-t cut ซึ่งก็จะมี Randomized Solution ในการแก้อีกเช่นกัน (เช่นการประยุกต์ใช้ของ Karger's Algorithm) แต่จากการทดลองพยายามหา Minimum s-t cut แล้วจะใช้เวลาเกินเป็นส่วนใหญ่ และยังไม่สามารถทำให้ผ่านได้จริง

คำถามต่อมาคือ เราจำเป็นต้องหาเซต $P$ ที่เล็กที่สุดหรือไม่ ซึ่งแท้ที่จริงแล้วเราไม่จำเป็นต้องหาเซต $P$ ที่เล็กที่สุด แต่เพียงแค่หาเซตที่เล็กเพียงพอก็สามารถทำได้แล้ว

Lemma 4

สำหรับกราฟ $G = (V,E)$ ที่เป็นกราฟเชื่อมต่อไม่ระบุทิศทางใด ๆ ที่มีจำนวนจุดยอดไม่เกิน $50\,000$ สมมติมีเซต $S \subseteq V$ และ $T \subseteq V$ ที่ $S \cap T = \emptyset$ และ $\forall s \in S, \forall t \in T, [udist(s,t) \geq 1\,001]$ จะได้ว่า มีเซต $P \subseteq V$ (ที่มีสมบัติคือ เมื่อนำจุดยอดภายในเซต $P$ ออกจนหมดแล้วทำให้ไม่มี path ใด ๆ เลยที่เชื่อมระหว่าง $s \in S$ ใด ๆ กับ $t \in T$ ใด ๆ ) ที่ $|P| \leq 50$

Proof

ในการพิสูจน์ จะแบ่งออกเป็นสองส่วน ส่วนแรกคือการพิสูจน์ว่า จะมี $1 \leq d \leq 1\,001$ ที่ $P = \{u \in V | \exists s \in S, udist(s, u) = d\}$ มีขนาดไม่เกิน $50$ ส่วนที่สองคือการพิสูจน์ว่า $P$ ที่ได้จากส่วนแรกนั้น เป็น s-t cut ของ $G$

เราเริ่มด้วยการหา multiple source shortest path จาก $S$ ไปยังทุกจุดยอดที่เหลือใน $G$

หากสำหรับจุดยอด $u$ ที่เหลือใน $G$ มี $d = \min\limits_{s \in S}{udist(s,u)}$ เราจะเขียนแทนด้วย $udist_S(u) = d$

เมื่อเราทำการแบ่งแยกจุดยอดต่าง ๆ ออกเป็นชั้นสมมูลตามค่า $udist_S(u)$ ของแต่ละ $u$ (กล่าวคือ กำหนดให้ $[d] = \{u \in V | udist_S(u) = d\}$)

Part 1

ต่อมาจะพิสูจน์ว่า $\exists d, 1 \leq d \leq 1\,001, |[d]| \leq 50$ โดยการพิสูจน์โดยข้อขัดแย้ง ดังนี้

สมมติให้ $\forall d, 1 \leq d \leq 1\,001, |[d]| > 50$ จะได้ว่าเซต $[d]$ แต่ละเซตขนาดมากกว่า 50 แต่เนื่องจากมีเซตเหล่านี้อยู่ $1\,001$ เซต และไม่มีสองเซตใดที่ซ้อนทับกันอยู่เลย จึงได้ว่า $\left|\bigcup\limits_{i=1}^{1\,001}{[i]}\right| > 50 \cdot 1001 = 50\,050$ ขัดแย้งกับที่กำหนดว่ามีจุดยอดไม่เกิน $50\,000$ จุด

Part 2

ต่อมาจะแสดงว่า สำหรับ $1 \leq d \leq 1\,001$ ใด ๆ, $[d]$ เป็น s-t cut ของ $G$ โดยการพิสูจน์โดยข้อขัดแย้ง ดังนี้

สมมติให้ $1 \leq d \leq 1\,001$ ที่ $[d]$ ไม่เป็น s-t cut ของ $G$ จะได้ว่าหลังลบทุกจุดยอด $u$ ที่ $udist_S(u) = d$ ออกไปจากกราฟแล้วยังทำให้สามารถเดินทางจากบาง $s \in S$ ไปยังบาง $t \in T$ ได้อยู่ เนื่องจากว่าใน path ระหว่าง $s \in S$ กับ $t \in T$ ใด ๆ เราทราบว่าจุดยอดที่ติดกันใน path จะมี $udist_S$ ต่างกันไม่เกิน $1$ แน่นอน (สมมติว่าจุดยอดทั้งสองนั้นคือ $a, b$ โดยไม่เสียนัยทั่วไปหาก $udist_S(a) > udist_S(b)+1$ เราสามารถเปลี่ยนค่า $udist_S(a)$ เป็น $udist_S(b)+1$ ได้เลย โดยการเปลี่ยนจากเส้นทางเดิมเป็นเดินจาก $b$ ไปยัง $a$) เมื่อทราบว่า $udist_S$ ต่างกันไม่เกิน $1$ แน่นอน แสดงว่า $udist_S(t) < d$ เพราะหาก $udist_S(t) \geq d$ จะได้ว่า มี $a$ ใน path จาก $s$ ไป $t$ ที่ $udist_S(a) = d$ จาก Intermediate Value Theorem (discrete version) ขัดแย้งกับที่สมมติไว้ว่า $udist_S(t) \geq 1\,001$

ในจุดนี้ จึงสามารถสรุป Lemma 4 ได้

Solution

จาก proof ของ Lemma 4 นั้น เราอาศัย multiple source shortest path ในการกำหนดค่า $udist_S(u)$ สำหรับแต่ละ $u \in V$ แล้วเราพบว่าการกระทำดังกล่าวจะมี $1 \leq d \leq 1\,001$ ที่ $|[d]| \leq 50$ แน่ ๆ เราจึงใช้ข้อสังเกตนี้ทำการหา $d$ ดังกล่าว และกำหนด $P := [d]$ เป็น s-t cut ที่นำมาใช้พิจารณา จะได้ว่าต้องทำการหา shortest path ไม่เกิน $50$ ครั้ง

จะได้ว่าใช้เวลาการทำงานรวมเป็น $\mathcal{O}(|P|M \log N)$ เหมือนเดิม แต่รับประกันว่า $|P| \leq 50$