VC-SNDP:spider decomposition
This page describes spider decompositions and the approach of Chuzhoy Khanna and Chekuri and Korula in tackling the single-source k sndp.
ให้กราฟ เซตของ terminals T และจำนวนเต็มบวก เรียกโหนดใน T ว่าเป็น black vertices, นอกจากนั้นเป็น white vertices.
Spider คือ tree ที่มีโหนดที่มีดีกรีมากกว่าสองไม่เกิน 1 จุดยอด ถ้ามี vertex ดังกล่าว จะเรียกว่าเป็น head ถ้าไม่มี spider จะเป็น path และจะสามารถเรียกโหนดใดเป็น head ก็ได้; เรียกจุดยอดที่ไม่ใช่ leaf และ head ว่า intermediate vertex, เรียก leaf ว่า foot, เรียก path จาก head ไป leaf ว่า leg
เนื้อหา
Decomposition
Chuzhoy และ Khanna ได้ใช้ spider decomposition ในการพิสูจน์ approximation algorithm สำหรับ ss-k-sndp อย่างไรก็ตามในที่นี้เราจะใช้ decomposition ที่ weak กว่าของ Chekuri และ Korula
Chekuri-Korula [Theorem 4.4] แสดงว่า ให้กราฟ G ที่ทุก ๆ คู่ของจุดยอดสีดำ k-element connected, มีสับกราฟ H ของ G ที่สามารถ partition เป็น spiders ที่
- ทุก ๆ leaf เป็น black vertex และ ทุก ๆ intermediate vertex เป็น white vertex (สังเกตว่า head เป็น black vertex ได้)
- ทุก ๆ black vertex เป็น foot ของ k spiders พอดี, และ ทุก ๆ white vertex อยู่ใน 1 spider เท่านั้น
- สำหรับกรณีที่ spider มี white vertex เป็น head จะต้องมี leg อย่างน้อย 2 legs
ด้านล่างแสดงตัวอย่างของ spiders
spider decomposition กับ set ของ paths
พิจารณา spider แต่ละตัว เราจะพบว่าเราสามารถหาเซตของ path จากแต่ละ foot หนึ่ง ๆ ไปยังอีก foot ใด ๆ ได้ โดยที่ค่าใช้จ่ายรวมไม่เกิน 2 เท่าของ cost ของ spider (ดูรูป)
ดังนั้น ถ้าเรามี spider decomposition เราจะได้ว่าเราสามารถหา, สำหรับทุก ๆ terminal $t$, set of $k$ internally vertex disjoint paths $P_t$ ที่ $\sum_{t\in T}cost(P_t)\leq \sum_{\mbox{spider} S} cost(S)$
บทพิสูจน์: มี spider decomposition
โดย induction บนจำนวน edge ระหว่าง white vertices ใน G ใน base case ให้กราฟ G ไม่มี edge ดังกล่าวเลย จะได้ว่า G เป็น bipartite. ( edge ระหว่าง black vertices ก็ไม่มีด้วย) เนื่องจากแต่ละคู่ของ black vertices เป็น k-element connected แสดงว่าแต่ละ black vertex จะต้องมีอย่างน้อย k white vertices ที่ติดกับมัน
เราจะสร้าง set of spiders โดยให้แต่ละโหนด b
