Back to : cs-adventure
Back to : advanced-algorithms
Contents

์ด๋ฒˆ์— ๊ณต๋ถ€ํ•ด๋ณผ ๋…ผ๋ฌธ์€ All Pairs Almost Shortest Path ์ž…๋‹ˆ๋‹ค.

D. Dor, S. Halperin and U. Zwick, โ€œAll pairs almost shortest paths,โ€ Proceedings of 37th Conference on Foundations of Computer Science, 1996, pp. 452-461, doi: 10.1109/SFCS.1996.548504.

1996๋…„๋„ ๋…ผ๋ฌธ์œผ๋กœ, ์ดํ›„์—๋„ ๋งŽ์€ ๋…ผ๋ฌธ๋“ค์ด ์ด ๋…ผ๋ฌธ์—์„œ ์ œ์‹œํ•œ bound๋ฅผ ๋” ๋‚ด๋ฆฌ๋Š” ๋“ฑ ๋” contribution์ด ์žˆ์ง€๋งŒ, ์•„์ด๋””์–ด๊ฐ€ ํฅ๋ฏธ๋กญ๊ณ  ์ดํ›„ ๋…ผ๋ฌธ๋“ค์˜ ๊ธฐ๋ฐ˜์ด ๋˜๋Š” ์—ฐ๊ตฌ์ž…๋‹ˆ๋‹ค.

์—ฐ๋„์— ๋Œ€ํ•ด ์–ธ๊ธ‰ํ•˜๋Š” ์ดํ›„๋Š” ์ดํ›„ 25๋…„๊ฐ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ถ„์•ผ์˜ ๋ฐœ์ „์œผ๋กœ ํ˜„์žฌ์—๋Š” ๋‹ค๋ฅธ ๋ฌธ์ œ๋“ค์˜ ๋ณต์žก๋„๊ฐ€ ์•ฝ๊ฐ„์”ฉ ๋‹ฌ๋ผ์กŒ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.

๊ทธ๋ž˜ํ”„ ๋ฌธ์ œ์—์„œ ํ”ํžˆ ๊ทธ๋ ‡๋“ฏ, $G = (V, E)$์— ๋Œ€ํ•ด $\abs{V} = n$, $\abs{E} = m$์œผ๋กœ ์“ฐ๋˜, $O(V)$ ์™€ ๊ฐ™์ด notation์„ abuseํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

Introduction

All Pairs Shortest Path (์ดํ•˜ APSP) ๋ž€, ๋‹จ์ˆœํ•˜๊ฒŒ ์–ด๋–ค ๊ทธ๋ž˜ํ”„ $G = (V, E)$ ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ฐ vertex์—์„œ ๋‹ค๋ฅธ vertex๋กœ ๊ฐ€๋Š” ์ตœ๋‹จ ๊ฒฝ๋กœ์˜ ๊ธธ์ด๋ฅผ ๋ชจ๋‘ ์•Œ์•„๋‚ด๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋‹น์—ฐํ•˜๊ฒŒ๋„, ์‹ค์šฉ์ ์œผ๋กœ ๋งŽ์€ ์“ฐ์ž„์ด ์žˆ์Šต๋‹ˆ๋‹ค.

์šฐ๋ฆฌ๋Š” ์šฐ์„  ๋…ผ๋ฌธ์„ ๋”ฐ๋ผ, Undirected์˜ ๊ฒฝ์šฐ๋งŒ ๊ณ ๋ คํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ๊ฒฝ๋กœ์˜ ๊ธธ์ด๋Š” ์ง€๋‚˜๊ฐ€๋Š” edge์˜ ๊ฐœ์ˆ˜๊ฐ€ ๋  ๊ฒƒ์ž…๋‹ˆ๋‹ค.

๋‹ค์Œ ์„ธ ๊ฐ€์ง€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๊ฐ€์žฅ ๋จผ์ € ๊ณ ๋ คํ•  ๋งŒ ํ•ฉ๋‹ˆ๋‹ค.

  • Floyd-Warshal Algorithm : $O(V^3)$ ์‹œ๊ฐ„์— APSP๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. ๊ตฌํ˜„์ด ๋งค์šฐ ์‰ฝ๊ณ , ๊ฐ„๋‹จํ•œ Dynamic programming์˜ ์›๋ฆฌ๋ฅผ ๋”ฐ๋ฅด๊ธฐ ๋•Œ๋ฌธ์— ์ดํ•ดํ•˜๊ธฐ ์‰ฝ์Šต๋‹ˆ๋‹ค.
  • Dijkstra (or any SSSP) : ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•œ ์ •์ ์œผ๋กœ๋ถ€ํ„ฐ ๋‹ค๋ฅธ ๋ชจ๋“  ์ •์ ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ๋Š” Single Source Shortest Path (์ดํ•˜ SSSP) ๋ฌธ์ œ๋ฅผ $O(E + V \log V)$ ๋˜๋Š” $O(E \log V)$ ์‹œ๊ฐ„์— ํ•ด๊ฒฐํ•ฉ๋‹ˆ๋‹ค. (Fibonacci heap์˜ ์‚ฌ์šฉ ์—ฌ๋ถ€์— ๋”ฐ๋ผ ๋‹ค๋ฆ„) ์ž๋ช…ํ•˜๊ฒŒ, ๋ชจ๋“  ์ •์ ์—์„œ ์ถœ๋ฐœํ•˜๋Š” ๊ฐ SSSP๋ฅผ ํ•ด๊ฒฐํ•˜๋ฉด ๋˜๊ธฐ ๋•Œ๋ฌธ์— ์šฐ๋ฆฌ๋Š” $O(VE + V^2 \log V)$ ์ •๋„ ์‹œ๊ฐ„์—๋Š” APSP๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์€ sparse graph์— ๋Œ€ํ•ด์„œ๋Š” ๋งค์šฐ ๋น ๋ฅด์ง€๋งŒ, dense graph์— ๋Œ€ํ•ด์„œ๋Š” $E = O(V^2)$ ๊นŒ์ง€ ๊ฐ€๋Šฅํ•˜๊ธฐ ๋•Œ๋ฌธ์— $O(V^3)$ ์ž…๋‹ˆ๋‹ค.
  • Matrix Multiplication : Floyd-Warshall์˜ inner loop์ด ํ–‰๋ ฌ๊ณฑ์…ˆ์ด๋ž‘ ๋น„์Šทํ•˜๊ฒŒ ์ƒ๊ฒผ์Œ์„ ํ™œ์šฉํ•ฉ๋‹ˆ๋‹ค. ํ–‰๋ ฌ๊ณฑ์…ˆ๊ณผ ๊ฑฐ์˜ ๋น„์Šทํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•˜๋ฉด, Adjacency matrix $A$๋ฅผ repeated squaringํ•˜์—ฌ ์ด ๋ฌธ์ œ๋ฅผ $O(V^3 \log V)$ ์— ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋” ๋Š๋ ค ๋ณด์ด๋Š” ์ด ๋ฐฉ๋ฒ•์„ ์–ธ๊ธ‰ํ•˜๋Š” ์ด์œ ๋Š”, ํ–‰๋ ฌ๊ณฑ์…ˆ์— ์“ฐ๋Š” ๋น ๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค ์ค‘ ์ผ๋ถ€๊ฐ€1 ์ด โ€˜์œ ์‚ฌ-ํ–‰๋ ฌ๊ณฑ์…ˆโ€™์—๋„ ๋˜‘๊ฐ™์ด ์ ์šฉ๊ฐ€๋Šฅํ•˜๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ์ŠคํŠธ๋ผ์„ผ์„ ์“ฐ๋ฉด $O(V^{2.807} \log V)$ ์ด ๋˜๊ณ  ์ด๋Š” ์œ„ ๋‘ ๋ฐฉ๋ฒ•๋ณด๋‹ค worst-case์— ๋” ๋น ๋ฆ…๋‹ˆ๋‹ค.

์ด ๋…ผ๋ฌธ์—์„œ๋Š”, โ€œ์•ฝ๊ฐ„์˜ ์˜ค์ฐจ๋ฅผ ํ—ˆ์šฉํ•˜๋ฉดโ€ ์ด๋ณด๋‹ค ๋น ๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์กด์žฌํ•จ์„ ๋ณด์ž…๋‹ˆ๋‹ค. ์ •ํ™•ํžˆ๋Š”, ๋ชจ๋“  ์ •์ ์Œ $(v_i, v_j)$์— ๋Œ€ํ•ด, $d(v_i, v_j) + 2$ ๋ฅผ ๋„˜์ง€ ์•Š๋Š” ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋…ผ์˜ํ•˜๊ณ , ์ด๋ฅผ ํ™•์žฅํ•˜์—ฌ $k$๋งŒํผ์˜ ์˜ค์ฐจ๋ฅผ ํ—ˆ์šฉํ•˜๋˜ ๊ทธ๋งŒํผ ๋นจ๋ผ์ง€๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋…ผ์˜ํ•ฉ๋‹ˆ๋‹ค.

Key ideas

At a glance

์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํฐ ์•„์ด๋””์–ด๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  1. Dijkstra ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ sparse graph์— ๋Œ€ํ•ด ๊ฝค ๋น ๋ฆ…๋‹ˆ๋‹ค.
  2. ๊ทธ๋ž˜ํ”„์˜ ์„ฑ์งˆ์„ ๊ฑฐ์˜ ๋ณด์กดํ•˜๋ฉด์„œ ์›๋ž˜์˜ ๊ทธ๋ž˜ํ”„๋ณด๋‹ค sparseํ•œ auxillary graph ์œ„์—์„œ Dijkstra๋ฅผ ๋Œ๋ฆฌ๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.
  3. Unweighted graph์— ๋Œ€ํ•ด์„œ๋Š” ํŠนํžˆ, dijkstra๋ฅผ ์ผ๋ฐ˜์ ์ธ BFS๋กœ ๋Œ€์ฒดํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Dominating Set

๊ทธ๋ž˜ํ”„ $(V, E)$์—์„œ, ์–ด๋–ค ์ •์ ์˜ ๋ถ€๋ถ„์ง‘ํ•ฉ $S$๊ฐ€ ๋‹ค๋ฅธ ๋ถ€๋ถ„์ง‘ํ•ฉ $T$๋ฅผ dominate ํ•œ๋‹ค๋Š” ๊ฒƒ์€, $T$์˜ ๋ชจ๋“  vertex๊ฐ€ $S$์˜ vertex์ค‘ ํ•˜๋‚˜ ์ด์ƒ๊ณผ edge๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๊ฒƒ์œผ๋กœ ์ •์˜ํ•ฉ๋‹ˆ๋‹ค. ์ฆ‰, ์•„๋ž˜ ๊ทธ๋ฆผ์—์„œ ๋นจ๊ฐ„์ƒ‰์œผ๋กœ ์ƒ‰์น ๋œ vertex๋Š” ๊ทธ๋ž˜ํ”„ ์ „์ฒด๋ฅผ dominateํ•ฉ๋‹ˆ๋‹ค.

image

์ผ๋ฐ˜์ ์ธ ๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•ด minimal dominating set์„ ์ฐพ๋Š” ๊ฒƒ์€ ๋งค์šฐ ์ž˜ ์•Œ๋ ค์ง„ NP-Hard ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜, ์šฐ๋ฆฌ๋Š” ์ข€ ํŠน์ˆ˜ํ•œ ๊ฒฝ์šฐ๋งŒ ๋…ผ์˜ํ•ฉ๋‹ˆ๋‹ค. ๊ตฌ์ฒด์ ์œผ๋กœ, ์–ด๋–ค parameter $s$์— ๋Œ€ํ•ด, ๋‹ค์Œ์„ ํ•ด๊ฒฐํ•ฉ๋‹ˆ๋‹ค.

Dominate(G, s) : $G$์—์„œ, degree๊ฐ€ $s$์ด์ƒ์ธ ์ •์ ๋“ค์„ ๋ชจ์€ ๋ถ€๋ถ„์ง‘ํ•ฉ์„ dominateํ•˜๋Š” ์ ๋‹นํžˆ ์ž‘์€ dominating set์„ ์ฐพ๋Š”๋‹ค.

์—ฌ๊ธฐ์„œ ์ ๋‹นํžˆ ์ž‘์€ ์ด๋ž€, $O\left(\frac{n \log n}{s}\right)$๋ฅผ ๋ชฉํ‘œ๋กœ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ์œ„ํ•ด ๋‹ค์Œ์˜ ๊ทธ๋ฆฌ๋””๊ฐ€ ์ž˜ ์•Œ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.

  • ๊ฐ vertex์— ๋Œ€ํ•ด neighbor set์„ ์ƒ๊ฐํ•˜๋ฉด, dominating set์„ ์ฐพ๋Š” ๊ฒƒ์€ set cover๋ฅผ ์ฐพ๋Š” ๊ฒƒ๊ณผ ๊ฐ™์€ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
  • ๊ฐ ์ง‘ํ•ฉ $S_i$์˜ ์›์†Œ๋Š” $\Set{1, \cdots, n}$ ๋ฒ”์œ„ ๋‚ด์— ์žˆ๊ณ , ์ „์ฒด ์›์†Œ์˜ ํ•ฉ์€ $2m$๊ฐœ ์ž…๋‹ˆ๋‹ค.
  • Greedy ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ๊ฐ ์Šคํ…๋งˆ๋‹ค, โ€˜ํ˜„์žฌ๊นŒ์ง€ cover๋˜์ง€ ์•Š์€ ๊ฐ€์žฅ ๋งŽ์€ element๋ฅผ ์ƒˆ๋กœ coverํ•˜๋Š”โ€™ ์ง‘ํ•ฉ์„ ํƒํ•ฉ๋‹ˆ๋‹ค.
  • ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ž˜ ์ƒ๊ฐํ•ด๋ณด๋ฉด $m$์— ๋Œ€ํ•ด ์„ ํ˜•์œผ๋กœ ๊ตฌํ˜„๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.
    • ๊ฐ $x \in \Set{1, \cdots, n}$์— ๋Œ€ํ•ด, $x$๋ฅผ ํฌํ•จํ•˜๋Š” ๋ชจ๋“  ์ง‘ํ•ฉ์˜ ๋ฆฌ์ŠคํŠธ $L$ ๋ฅผ ๊ด€๋ฆฌํ•˜๊ณ , ๋™์‹œ์— ํ˜„์žฌ ๋‚จ์€ covering power (ํ˜„์žฌ uncovered์ธ vertex ๊ฐœ์ˆ˜) ๊ฐ€ $i$์ธ ์ง‘ํ•ฉ์˜ ๋ฆฌ์ŠคํŠธ $A[i]$๋ฅผ ๊ด€๋ฆฌํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ๊ฐ ์›์†Œ์˜ remaining covering power๋ฅผ $P[i]$๋ผ๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.
    • ์‹์œผ๋กœ ์“ฐ๋ฉด ๋ณต์žกํ•ด์ง€๋ฏ€๋กœ, pseudocode๋ฅผ ์ด์šฉํ•ด์„œ ํ‘œํ˜„ํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.
      cur = maximum of |S| among sets
      while cur > 0:
          if A[cur] empty : cur -= 1, continue
          X = choose one with maximum P
          for t in X:
              if t is uncovered:
                  mark t as covered
                  for each Y containing t:
                      remove Y from A[P[Y]]
                      add Y to A[P[Y]-1]
      
  • ์‹œ๊ฐ„ ๋ณต์žก๋„ ์ฆ๋ช… (์œ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด $O(\sum \abs{S})$) ์ž„์„ ์ฆ๋ช…)
    • A๋ฅผ ๊ด€๋ฆฌํ•˜๋Š” - ์ฆ‰, Y๋ฅผ A[P[Y]]์—์„œ ๊บผ๋‚ด์„œ A[P[Y]-1] ๋กœ ์˜ฎ๊ธฐ๋Š” decrease ์—ฐ์‚ฐ์ด $O(1)$์— ์‹œํ–‰๊ฐ€๋Šฅํ•˜๋‹ค๋ฉด, ๊ฐ ์ง‘ํ•ฉ์ด ๋ชจ๋‘ ๊ทธ ํฌ๊ธฐ๋งŒํผ decrease๋˜์–ด์•ผ ํ•˜๋ฏ€๋กœ ์ „์ฒด ๋ณต์žก๋„๋Š” ๊ฐ ์ง‘ํ•ฉ์˜ ์›์†Œ์˜ ๊ฐœ์ˆ˜์˜ ํ•ฉ์ž…๋‹ˆ๋‹ค. Bucket Queue ๊ฐ™์€ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ด์šฉํ•˜๋ฉด ์ด๊ฒŒ ๊ฐ€๋Šฅํ•จ์ด ์•Œ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. (CLRS, 35-2-3).
    • ๊ทธ๋Ÿฐ๋ฐ, ๊ฐ vertex์˜ neighbor ๊ฐœ์ˆ˜์˜ ํ•ฉ์€ ๊ฒฐ๊ตญ edge๋ฅผ ๋‘๋ฒˆ์”ฉ ์„ผ ๊ฒƒ์ด๋ฏ€๋กœ $2m$ ์ž…๋‹ˆ๋‹ค.
  • $\log$ approximation
    • ๋จผ์ € ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์–ผ๋งˆ๋‚˜ ์ข‹์€ approximation์„ ์ œ๊ณตํ•˜๋Š”์ง€ ์ƒ๊ฐํ•ด ๋ด…๋‹ˆ๋‹ค. Optimal solution์ด $k$๊ฐœ์˜ ๋ถ€๋ถ„์ง‘ํ•ฉ์„ ์‚ฌ์šฉํ•œ๋‹ค๊ณ  ๊ฐ€์ •ํ•ฉ๋‹ˆ๋‹ค. ์ „์ฒด coverํ•  ์›์†Œ๊ฐ€ $n = n_0$๊ฐœ์ด๊ณ , ์ง‘ํ•ฉ์„ ํ•˜๋‚˜์”ฉ ํƒํ•œํ›„ ๊ฐ step์—์„œ โ€œ๋‚จ์€ coverํ•ด์•ผํ•  ์›์†Œ์˜ ์ˆ˜โ€ ๋ฅผ $n_i$๋ผ ํ•ฉ์‹œ๋‹ค.
    • ๋น„๋‘˜๊ธฐ์ง‘์˜ ์›๋ฆฌ์— ๋”ฐ๋ผ, ์–ด๋–ค ์ง‘ํ•ฉ์€ $n / k$๊ฐœ๋ณด๋‹ค ๋งŽ์€ ์›์†Œ๋ฅผ coverํ•ด์•ผ๋งŒ ํ•ฉ๋‹ˆ๋‹ค. WLOG, ์ด๋ฅผ $S_1$๋กœ ํƒํ•˜๋ฉด $n_1 \leq (n - n/k) = n\left(1-\frac{1}{k}\right)$ ์ž…๋‹ˆ๋‹ค.
    • ๋‹ค์‹œ ๋น„๋‘˜๊ธฐ์ง‘์˜ ์›๋ฆฌ์— ๋”ฐ๋ผ, $n_1/(k-1)$ ๊ฐœ๋ณด๋‹ค ๋งŽ์€ ์›์†Œ๋ฅผ coverํ•˜๋Š” ์ง‘ํ•ฉ์ด ์กด์žฌํ•ด์•ผ ํ•˜๊ณ , \(n_2 \leq n_1\left(1-\frac{1}{k}\right)\left(1-\frac{1}{k-1}\right)\leq n\left(1-\frac{1}{k}\right)^2\)
    • Greedy set cover์˜ ๊ฒฐ๊ณผ๊ฐ€ $u$๊ฐœ์˜ ์ง‘ํ•ฉ์„ ์“ด๋‹ค๋ฉด, $u$๋ฒˆ์„ ๋ฐ˜๋ณตํ•˜์—ฌ, $n_u \leq n\left(1-\frac{1}{k}\right)^u < 1$ ์ด๋ฅผ ๋‹ค์‹œ ์ •๋ฆฌํ•˜์—ฌ ๋‹ค์Œ์„ ์–ป์Šต๋‹ˆ๋‹ค. \(\left(1-\frac{1}{k}\right)^{k \cdot u/k} < \frac{1}{n}\) $(1-x)^{1/x} \leq 1/e$ ์ด๋ฏ€๋กœ, ์ด๋ฅผ ์ž˜ ์ •๋ฆฌํ•˜๋ฉด $u < k \log n$์„ ์–ป์Šต๋‹ˆ๋‹ค.
    • ์ฆ‰, Greedy set cover์˜ ๊ฒฐ๊ณผ๋Š” optimal๊ฒฐ๊ณผ๋ณด๋‹ค $\log n$๋ฐฐ ์ด์ƒ ๋‚˜์˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค!
  • ๋‹ค๋งŒ ์œ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ „์ฒด graph์˜ dominating set์„ ์ œ๊ณตํ•ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ, dummy vertex $s$๊ฐœ๋ฅผ ์ƒ์„ฑํ•œ ๋‹ค์Œ degree๊ฐ€ $s$ ๋ฏธ๋งŒ์ธ ๋ชจ๋“  vertex๋“ค์— ๋Œ€ํ•ด ์ด๋“ค์„ dummy vertex์— ์—ฐ๊ฒฐํ•ด ๋ฒ„๋ฆฌ๋ฉด ์ „์ฒด edge๋Š” ์ตœ๋Œ€ $ns$๊ฐœ ์ฆ๊ฐ€ํ•˜๊ณ , ๋ชจ๋“  vertex๊ฐ€ $s$์ด์ƒ์˜ degree๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค. dummy vertex๋“ค์€ ์–ด์ฐจํ”ผ high-degree vertex์™€๋Š” ์—ฐ๊ฒฐ๋˜์ง€ ์•Š์œผ๋ฏ€๋กœ, dominating set์—์„œ ์ด๋ฅผ ๋งˆ์ง€๋ง‰์— ์ œ๊ฑฐํ•ด๋„ ๋ฉ๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ํ•˜๋ฉดโ€ฆ
  • Dominate(G, s) ์˜ ๊ฒฐ๊ณผ๊ฐ’์€ $O\left(\frac{n \log n}{s}\right)$๊ฐœ ์ดํ•˜์˜ dominating set์„ ์ฐพ์•„์ฃผ๊ณ , ๊ทธ ์ˆ˜ํ–‰์‹œ๊ฐ„์€ $O(m + ns)$ ์ž…๋‹ˆ๋‹ค.

$O(n^{3/2}m^{1/2} \log n)$ complexity, 2-error

์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ Aingworth et al. 2 ์—์„œ ์ œ์‹œ๋œ, $\tilde{O}(n^{5/2})$ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์•ฝ๊ฐ„ ๊ฐœ์„ ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค.

  • $s = (m / n)^{1/2}$ ๋ผ ํ•˜๊ณ , degree๊ฐ€ $s$ ์ด์ƒ์ธ vertex ์ง‘ํ•ฉ $V_1$ ๊ณผ ๋ฏธ๋งŒ์ธ ์ง‘ํ•ฉ $V_2$๋กœ $V$๋ฅผ ๋‚˜๋ˆ•๋‹ˆ๋‹ค.
  • Low-degree vertex๋ฅผ touchํ•˜๋Š” edge์˜ ์ง‘ํ•ฉ์„ $E_2$๋ผ ํ•ฉ์‹œ๋‹ค. ์ด๋•Œ, ์ด๋“ค์˜ ๊ฐœ์ˆ˜๋Š” $ns$๊ฐœ ์ดํ•˜์ž…๋‹ˆ๋‹ค. (Low degree์ธ ์ •์  ์ตœ๋Œ€ $V$๊ฐœ, ๊ฐ๊ฐ์˜ degree ์ตœ๋Œ€ $s$)
  • Dominate(G, s) ๋ฅผ ๋Œ๋ฆฝ๋‹ˆ๋‹ค. ์ด ์ง‘ํ•ฉ์€ $O((n \log n) / s)$ ๊ฐœ ์ดํ•˜์ด๋ฏ€๋กœ, $O((n^{3/2} \log n) / m^{1/2})$ ๊ฐœ ์ดํ•˜์˜ ์ •์ ์œผ๋กœ ๊ตฌ์„ฑ๋œ ์ง‘ํ•ฉ์ž…๋‹ˆ๋‹ค. ๋˜ํ•œ, dominating set $D$๋ฅผ ์ฐพ๋Š” ๊ณผ์ •์—์„œ, $V_1$๊ฐœ์˜ edge๋ฅผ ์ด์šฉํ•˜์—ฌ $V_1$์˜ ๊ฐ ์ •์ ์„ $D$์˜ ์ •์ ์— ๋งค๋‹ฌ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด $V_1$๊ฐœ์˜ edge์ง‘ํ•ฉ (ํŽธ์˜์ƒ, dominating edge๋ผ ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค) $E^*$์„ ์ฐพ์Šต๋‹ˆ๋‹ค.
  • ์ด์ œ, $u \in D$์— ๋Œ€ํ•ด, BFS๋ฅผ ์ด์šฉํ•ด ์ตœ๋‹จ๊ฒฝ๋กœ๋ฅผ ๊ทธ๋ƒฅ ์ฐพ์Šต๋‹ˆ๋‹ค. BFS๋Š” ํ•œ๋ฒˆ์— $O(m)$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ๋ฏ€๋กœ (connected graph์ด๋ฏ€๋กœ $m \geq n$), ์ด๋ถ€๋ถ„์˜ ์ˆ˜ํ–‰์‹œ๊ฐ„์€ $O(\abs{D}m) = O(m^{1/2}n^{3/2}\log n)$ ์ž…๋‹ˆ๋‹ค.
  • $u \in V-D$ ์— ๋Œ€ํ•ด, ๋‹ค์Œ๊ณผ ๊ฐ™์ด weighted graph๋ฅผ ๋งŒ๋“ค์–ด ๋‹ค์ต์ŠคํŠธ๋ผ๋ฅผ ๋Œ๋ฆฝ๋‹ˆ๋‹ค.
    • ๊ฐ $u$์— ๋Œ€ํ•ด, $G_2(u)$๋ฅผ ๋งŒ๋“ญ๋‹ˆ๋‹ค. ์ด๋•Œ, $G_2(u)$์˜ ์ •์ ์€ $V$์ด๊ณ , edge๋Š” $E^*$ ์™€ $E_2$์— ์žˆ๋Š” edge๋“ค์„ ๋ชจ๋‘ ์ทจํ•œ ๋‹ค์Œ, ๊ฐ $v \in D$์— ๋Œ€ํ•ด $(u, v)$ edge๊ฐ€ $\delta(u, v)$ weight์„ ๊ฐ–๋„๋ก ๋งŒ๋“ญ๋‹ˆ๋‹ค.
    • $\delta(u, v)$๋Š” ์•ž์„  BFS, ๊ตฌ์ฒด์ ์œผ๋กœ BFS(v)์—์„œ ๊ตฌํ•œ ๊ฐ’์ด๋ฏ€๋กœ ์ •ํ™•ํ•œ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๊ฐ’ ์ž…๋‹ˆ๋‹ค.
    • ์ด๋•Œ, $\abs{E^*} = V_1 = O(n)$, $\abs{E_2} = O(ns) = O(n^{1/2}m^{1/2})$, $\abs{\Set{u} \times D} = \abs{D} = O((n^{3/2} \log n) / m^{1/2})$ ์ž…๋‹ˆ๋‹ค.
    • ์ด ๊ทธ๋ž˜ํ”„ ์œ„์—์„œ, ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰์‹œ๊ฐ„์€ $O(n + n^{1/2}m^{1/2} + (n^{3/2} \log n) / m^{1/2})$ ๊ฐœ์˜ ๊ฐ„์„ ์„ ๊ฐ€์ง„ ๊ทธ๋ž˜ํ”„์—์„œ ๋Œ๋ฆฌ๋Š” ๋‹ค์ต์ŠคํŠธ๋ผ์ž…๋‹ˆ๋‹ค. ์ด Edge set์˜ ํฌ๊ธฐ๋Š” $O(m^{1/2}n^{1/2} \log n)$ ์ดํ•˜์ž…๋‹ˆ๋‹ค. ๋‹ค์‹œ, ๋‹ค์ต์ŠคํŠธ๋ผ๋Š” ์ตœ๋Œ€ $\abs{V-D} \leq n$ ๋ฒˆ ์‹œํ–‰๋˜๋ฏ€๋กœ ๋ชจ๋‘ ํ•ฉํ•˜๋ฉด ์ด์ชฝ๋„ $O(m^{1/2}n^{3/2} \log n)$ ์ด ๋  ๊ฒƒ์ž…๋‹ˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ ์ „์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ $O(m^{1/2}n^{3/2} \log n)$ ์ž…๋‹ˆ๋‹ค.

์ด์ œ, ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ตœ๋Œ€ 2 ์ดํ•˜์˜ ์˜ค์ฐจ๋ฅผ ๊ฐ€์ง์„ ๋ณด์ž…๋‹ˆ๋‹ค.

  • ์ •์ ์Œ $(u, v)$์— ๋Œ€ํ•ด $u \to v$์˜ ์ตœ๋‹จ๊ฒฝ๋กœ๊ฐ€ ์ ์–ด๋„ ํ•˜๋‚˜ ์ด์ƒ์˜ High-degree ์ •์ ์„ ์ง€๋‚œ๋‹ค๋ฉด:
    • ๋งˆ์ง€๋ง‰์œผ๋กœ ์ง€๋‚˜๋Š” high-์ ์„ $w$๋ผ ํ•ฉ์‹œ๋‹ค. ์ด์ œ, $w \to v$์˜ ์ตœ๋‹จ๊ฒฝ๋กœ๋Š” ๋ชจ๋‘ low-degree ์ •์ ๋งŒ์œผ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๊ณ , ์ด๋Š” ๋‹ค์‹œ $G_2(u)$ ์— ํ†ต์งธ๋กœ ๋“ค์–ด๊ฐ‘๋‹ˆ๋‹ค. ์ด๋Š” $G_2(u)$๋ฅผ ๋งŒ๋“ค๋•Œ, low-degree ์ •์ ์„ ํ•œ๋ฒˆ์ด๋ผ๋„ ํ„ฐ์น˜ํ•˜๋Š” ๋ชจ๋“  ๊ฐ„์„ ๋“ค์„ ๋•Œ๋ ค๋„ฃ์—ˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
    • $wโ€™$ ๋ฅผ $w$๋ฅผ dominateํ•˜๋Š” $D$์˜ ์ •์ ์ด๋ผ๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. $(w, wโ€™)$ ๊ฐ„์„  ๋˜ํ•œ $G_2(u)$ ์— ๋“ค์–ด๊ฐ‘๋‹ˆ๋‹ค.
    • $wโ€™ \in D$ ์ด๋ฏ€๋กœ, $(u, wโ€™) \in G_2(u)$์ด๊ณ , ์ด ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜ $\delta(u, wโ€™)$๋Š” BFS(w')์—์„œ ๊ตฌํ•œ ๊ฐ’์ด๋ฏ€๋กœ ์ •ํ™•ํ•ฉ๋‹ˆ๋‹ค.
    • Dominating์€ ๋ฐ”๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค๋Š” ๋œป์ด๋ฏ€๋กœ, $\delta(u, wโ€™) \leq \delta(u, w) + 1$ ์ž…๋‹ˆ๋‹ค.
    • ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์˜ํ•ด ๊ตฌํ•ด์ง€๋Š” ๊ฑฐ๋ฆฌ๋ฅผ $\hat{\delta}$ ์ด๋ผ ํ•˜๋ฉด, $\hat{\delta}(u, v)$ ๋Š” ๋‹ค์Œ์„ ๋งŒ์กฑํ•ฉ๋‹ˆ๋‹ค. \(\hat{\delta}(u, w') + \hat{\delta}(w', w) + \hat{\delta}(w, v)\)
    • ๊ทธ๋Ÿฐ๋ฐโ€ฆ$\hat{\delta}(u, wโ€™)$ ์€ BFS์—์„œ ๊ตฌํ•œ weight๊ฐ€ ๋„˜์–ด์˜ค๋ฏ€๋กœ ์ •ํ™•ํ•˜๊ณ , ์ด๋Š” ๋‹ค์‹œ $\delta(u, w) + 1$ ์ดํ•˜์ž…๋‹ˆ๋‹ค.
    • $\hat{\delta}(wโ€™, w)$๋Š” ์–ด์ฐจํ”ผ 1์ž…๋‹ˆ๋‹ค.
    • $\hat{\delta}(w, v)$ ๋Š” ๋‹ค์‹œ ์‹ค์ œ ์ตœ๋‹จ๊ฒฝ๋กœ๊ฐ€ $G_2(u)$์— ๋“ค์–ด์žˆ์œผ๋ฏ€๋กœ ์ •ํ™•ํ•ฉ๋‹ˆ๋‹ค.
    • ๊ทธ๋Ÿฌ๋ฉด, ๋‹ค์Œ ๋ถ€๋“ฑ์‹์ด ์„ฑ๋ฆฝํ•ฉ๋‹ˆ๋‹ค. \(\hat{\delta}(u, v) \leq \delta(u, w) + 1 + 1 + \delta(w, v) \leq \delta(u, v)\)
    • ๋”ฐ๋ผ์„œ, ์ด๋ ‡๊ฒŒ ๊ตฌํ•œ ์ตœ๋‹จ๊ฒฝ๋กœ๋Š” ์ตœ๋Œ€ 2๋งŒํผ์˜ ์˜ค์ฐจ๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค.
  • ์ •์ ์Œ $(u, v)$์— ๋Œ€ํ•ด $u \to v$์˜ ์ตœ๋‹จ๊ฒฝ๋กœ๊ฐ€ High-degree ์ •์ ์„ ์ง€๋‚˜์ง€ ์•Š๋Š”๋‹ค๋ฉด, ์ตœ๋‹จ๊ฒฝ๋กœ๊ฐ€ ํ†ต์งธ๋กœ $E_2$์— ๋“ค์–ด์žˆ๊ณ , ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ •ํ™•ํ•œ ๊ฒฝ๋กœ๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.

$O(n^{7/3} \log^2 n)$ complexity, 2-error

์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž์ฒด๋Š” ๊ฑฐ์˜ ๋˜‘๊ฐ™์ง€๋งŒ, ์ด๋ฒˆ์—๋Š” ์„ธ์กฐ๊ฐ์œผ๋กœ ๋‚˜๋ˆ•๋‹ˆ๋‹ค. degree๊ฐ€ $n^{1/3}$ ์ด์ƒ, $n^{2/3}$ ์ด์ƒ์ธ ์ ์„ ๊ฐ๊ฐ MID, HIGH๋ผ ํ•˜๊ณ , MID์™€ HIGH์˜ dominating set์„ ์ฐพ์Šต๋‹ˆ๋‹ค. (์ด๋ ‡๊ฒŒ ํ‘œํ˜„ํ•˜๊ธฐ๋Š” ํ–ˆ์ง€๋งŒ, MID๋Š” HIGH๋ฅผ ํฌํ•จ ํ•ฉ๋‹ˆ๋‹ค. MID์ด์ƒ, HIGH์ด์ƒ์ด๋ผ๊ณ  ์ƒ๊ฐํ•ด์ฃผ์„ธ์š”!)

  • MID์˜ dominating set $D_M$ ์€ $O(n^{2/3} \log n)$ ํฌ๊ธฐ์ด๊ณ , ๊ตฌํ•˜๋Š”๋ฐ๋Š” $O(m + n^{4/3})$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฝ๋‹ˆ๋‹ค.
  • HIGH์˜ dominating set $D_H$ ๋Š” $O(n^{1/3} \log n)$ ํฌ๊ธฐ์ด๊ณ , ๊ตฌํ•˜๋Š”๋ฐ๋Š” $O(m + n^{5/3})$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฝ๋‹ˆ๋‹ค.
  • ์œ„์—์„œ์™€ ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ, MID์— ํฌํ•จ๋˜์ง€ ์•Š๋Š” ์ •์  (์ฆ‰ degree๊ฐ€ โ€œ์ž‘์€โ€ ์ •์ ) ์„ ํ•˜๋‚˜๋ผ๋„ ํ„ฐ์น˜ํ•˜๋Š” edge์˜ ์ง‘ํ•ฉ์„ $E_M$, HIGH์— ํฌํ•จ๋˜์ง€ ์•Š๋Š” ์ •์  (degree๊ฐ€ โ€œํฌ์ง€ ์•Š์€โ€ ์ •์ ) ์„ ํ•˜๋‚˜๋ผ๋„ ํ„ฐ์น˜ํ•˜๋Š” edge์˜ ์ง‘ํ•ฉ์„ $E_H$๋ผ ํ•ฉ๋‹ˆ๋‹ค. $E_M$์˜ ํฌ๊ธฐ๋Š” $O(n^{4/3})$, $E_H$์˜ ํฌ๊ธฐ๋Š” $O(n^{5/3})$ ์ž…๋‹ˆ๋‹ค.
  • $D_H$ ์—์„œ BFS๋ฅผ ๋Œ๋ฆฝ๋‹ˆ๋‹ค. ์ด๋Š” $O(mn^{1/3}\log n)$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฝ๋‹ˆ๋‹ค.
  • $D_M$ ์—์„œ BFS๋ฅผ ๋Œ๋ฆฌ๋˜, ์ด๋ฒˆ์—๋Š” ๋ชจ๋“  ๊ฐ„์„ ์„ ์“ฐ๋Š” ๋Œ€์‹  $E_H$์— ์†ํ•˜๋Š” ๊ฐ„์„ ๋งŒ ์”๋‹ˆ๋‹ค. ์ด๋Š” $O(n^{2/3}n^{5/3}\log n) = O(n^{7/3} \log n)$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฝ๋‹ˆ๋‹ค.
  • ๋งˆ์ง€๋ง‰์œผ๋กœ, ๋‚˜๋จธ์ง€ ์ ๋“ค์—์„œ๋Š” Dijkstra๋ฅผ ๋Œ๋ฆฝ๋‹ˆ๋‹ค. ์ด๋•Œ, ๊ฐ„์„ ์€ $E_M$์— ์†ํ•˜๋Š” ๊ฐ„์„ ๋“ค, dominate์— ์“ฐ์ธ ๊ฐ„์„ ๋“ค, $(D_H \times V)$ ์— ์†ํ•˜๋Š” ๊ฐ„์„ ๋“ค, $(D_M \times D_M)$ ์— ์†ํ•˜๋Š” ๊ฐ„์„ ๋“ค, $(\Set{u} \times D_M)$ ์ด๋ ‡๊ฒŒ๋งŒ ๊ณ ๋ฆ…๋‹ˆ๋‹ค.
    • $E_M$์ด $O(n^{4/3})$, dominate์—๋Š” $n$๊ฐœ๊ฐ€ ์“ฐ์ด๊ณ ,
    • $(D_H \times V)$ ๊ฐ€ ๋˜ $O(n^{4/3} \log n)$๊ฐœ, $D_M \times D_M$ ์ด $O(n^{4/3} \log^2 n)$ ๊ฐœ, $(\Set{u} \times D_M)$์ด $O(n^{2/3} \log n)$ ๊ฐœ์ž…๋‹ˆ๋‹ค.
  • ์ด edge๊ฐ€ $O(n^{4/3} \log^2 n)$ ๊ฐœ์ด๊ณ , ๋Œ๋ฆฌ๋Š” ํšŸ์ˆ˜๊ฐ€ $n$๋ฒˆ ์ดํ•˜์ด๋ฏ€๋กœ $O(n^{7/3} \log^2 n)$ ์‹œ๊ฐ„์— ์ˆ˜ํ–‰๋ฉ๋‹ˆ๋‹ค.

๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ 2-error๋ฅผ ๋ณด์ž…๋‹ˆ๋‹ค.

  • ๋งŒ์•ฝ ์ตœ๋‹จ๊ฒฝ๋กœ๊ฐ€ HIGH์˜ ์ •์ ์„ ํ•˜๋‚˜๋ผ๋„ ์ง€๋‚œ๋‹ค๋ฉด, ๊ทธ์ค‘ ๋งˆ์ง€๋ง‰์„ $w$๋ผ ํ•˜๊ณ  $D_H$์—์„œ $w$๋ฅผ dominateํ•˜๋Š” $wโ€™$๋ฅผ ๊ณ ๋ฆ…๋‹ˆ๋‹ค.
    • $\delta(u, wโ€™)$ ๋Š” $wโ€™ \in D_H$ ์ด๋ฏ€๋กœ BFS(w')์— ์˜ํ•œ ์ •ํ™•ํ•œ ๊ฑฐ๋ฆฌ๋ฅผ ์••๋‹ˆ๋‹ค. ์ด๋Š” $\delta(u, w) + 1$ ๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์Šต๋‹ˆ๋‹ค.
    • $\delta(wโ€™, v)$ ๋Š” ์—ญ์‹œ BFS(w')์— ์˜ํ•ด ์ •ํ™•ํ•œ ๊ฑฐ๋ฆฌ๋ฅผ ์•Œ๊ณ , $\delta(w, v) + 1$ ๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์Šต๋‹ˆ๋‹ค.
    • ๋”ฐ๋ผ์„œ, ์ด๋ฅผ ๊ฐ’์€ $\delta(u, w) + 2 + \delta(w, v)$ ๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์Šต๋‹ˆ๋‹ค.
  • ๋งŒ์•ฝ ์ตœ๋‹จ๊ฒฝ๋กœ๊ฐ€ HIGH๋Š” ์•„์˜ˆ ์•ˆ ์ง€๋‚˜์ง€๋งŒ, MID๋ฅผ ์ง€๋‚œ๋‹ค๋ฉด, ๊ทธ์ค‘ ๋งˆ์ง€๋ง‰์„ $w$๋ผ ํ•˜๊ณ  $D_M$์—์„œ $w$๋ฅผ dominateํ•˜๋Š” $wโ€™$๋ฅผ ๊ณ ๋ฆ…๋‹ˆ๋‹ค.
    • $\delta(u, wโ€™)$ ์— ๋Œ€ํ•œ ๊ทผ์‚ฌ๊ฐ’์€ $D_M$์—์„œ์˜ BFS(๋‘๋ฒˆ์งธ BFS) ๋„์ค‘์— ๋น„์Šทํ•˜๊ฒŒ ์ฐพ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜, ์ด๋ฒˆ์—๋Š” $D_M$์ด ์ „์ฒด ๊ทธ๋ž˜ํ”„์— ๋Œ€๊ณ  BFS๋ฅผ ํ•œ ๊ฒฐ๊ณผ๊ฐ€ ์•„๋‹ˆ๊ธฐ ๋•Œ๋ฌธ์— ์ด๊ฒŒ ์ •ํ™•ํ•˜๋‹ค๋Š” ๋ณด์žฅ์ด ์—†์–ด์„œ, $\delta_2(u, wโ€™)$๋ผ๊ณ  ์“ฐ๊ฒ ์Šต๋‹ˆ๋‹ค. HIGH๋ฅผ ์•„์˜ˆ ์•ˆ ์ง€๋‚˜๋Š” ๊ฒฝ๋กœ๊ฐ€ ์ตœ๋‹จ์ž„์„ ๊ฐ€์ •์—์„œ ๋ณด์žฅํ–ˆ์œผ๋ฏ€๋กœ $\delta_2(u, w) = \delta(u, w)$ ์ด๊ณ , ๊ฒฐ๊ณผ์ ์œผ๋กœ $\delta_2(u, wโ€™)$ ๊ฐ’์€ $1 + \delta(w, u)$ ์ดํ•˜์ž…๋‹ˆ๋‹ค.
    • $\delta(wโ€™, w)$ ๋Š” 1์ด๊ณ 
    • $\delta(w, v)$ ๋Š” ๋ชจ๋‘ low-touching ์ž„์ด ๋ณด์žฅ๋˜๋ฏ€๋กœ ๋‹ค์ต์ŠคํŠธ๋ผ์˜ ๊ฒฐ๊ณผ๋กœ ์ •ํ™•ํ•œ ๊ฐ’์„ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋”ฐ๋ผ์„œ, ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ $O(n^{7/3} \log^2 n)$ ์‹œ๊ฐ„์— 2-error approximation์„ ๋ณด์žฅํ•ฉ๋‹ˆ๋‹ค.

Further : Time-Accuracy Tradeoff

์ด๋ฅผ ์ด์šฉํ•˜์—ฌ, 2์กฐ๊ฐ์ด๋‚˜ 3์กฐ๊ฐ์ด ์•„๋‹Œ ๋” ๋งŽ์€ ์กฐ๊ฐ์œผ๋กœ ์ž๋ฅด๋ฉด ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ ๋” ๋‚ฎ์•„์ง€๋Š” ๋Œ€์‹  ์—๋Ÿฌ๋ฅผ ๋” ํ—ˆ์šฉํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๊ตฌ์ฒด์ ์œผ๋กœ,

  • ์ฒซ๋ฒˆ์งธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ™•์žฅ, $s_i = (m / n)^{1-i/k}$์„ ์ด์šฉํ•˜์—ฌ ๊ณ„์‚ฐํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ $\tilde{O}(n^{2-1/k}m^{1/k})$ ์‹œ๊ฐ„์— $2(k-1)$ ์—๋Ÿฌ๋ฅผ ํ—ˆ์šฉํ•˜๊ณ ,
  • ๋‘๋ฒˆ์งธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ™•์žฅ, $s_i = n^{1-i/k}$๋ฅผ ์ด์šฉํ•˜์—ฌ $D_{j} \times D_{jโ€™}$ ๊ฐ™์€ ๊ฐ„์„ ๋“ค์„ ์ถ”๊ฐ€ํ•ด์„œ ๋‹ค์ต์ŠคํŠธ๋ผ๋ฅผ ์“ฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ $\tilde{O}(n^{2+1/k})$ ์‹œ๊ฐ„์— ์ž‘๋™ํ•˜๋Š” ๋Œ€์‹  $2(\floor{k/3} + 1)$ ์—๋Ÿฌ๋ฅผ ํ—ˆ์šฉํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

์ด๋ฅผ ํ•ฉ์ณ์„œ, $u$๋งŒํผ์˜ ์—๋Ÿฌ ๋ฐ”์šด๋“œ๋ฅผ ๊ณ ์ •ํ•˜๊ณ  ์‹ถ์œผ๋ฉด, ์ฒซ๋ฒˆ์งธ ๊ฒฝ์šฐ์˜ $k = u/2 + 1$ ๋˜๋Š” ๋‘๋ฒˆ์งธ ๊ฒฝ์šฐ์—์„œ $k = 3u - 2$๋ฅผ ์‚ฌ์šฉ, \(\min(\tilde{O}(n^{2-\frac{2}{u+2}}m^{\frac{2}{u+2}}), \tilde{O}(n^{2+\frac{2}{3u-2}}))\) ์ด์ •๋„ ์‹œ๊ฐ„๋ณต์žก๋„์— ์ตœ๋Œ€ $u$๋งŒํผ์˜ ์—๋Ÿฌ๋ฅผ ํ—ˆ์šฉํ•˜๋Š” APSP๋ฅผ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Thoughts

  1. ์ง€๋‚˜์น˜๊ฒŒ ๋‚œํ•ดํ•˜์ง€ ์•Š์€ ์•„์ด๋””์–ด (๊ทธ๋ž˜ํ”„์˜ edge๋ฅผ HIGH-LOW๋กœ ๋‚˜๋ˆˆ ๋‹ค์Œ, ์ด ์œ„์—์„œ ๊ฒฝ์šฐ์— ๋”ฐ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋ฐ”๊ฟ”๋ผ์›€์œผ๋กœ์จ ๋ณต์žก๋„ ๊ฐœ์„ ํ•˜๋Š” ์•„์ด๋””์–ด๋Š” ์˜์™ธ๋กœ ๋งŽ์ด ๋ณด์ž…๋‹ˆ๋‹ค) ๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ณต์žก๋„๋ฅผ ๋‚ด๋ฆฌ๋Š” ๋ถ€๋ถ„์ด ์ธ์ƒ์ ์ด์—ˆ์Šต๋‹ˆ๋‹ค.
  2. ๊ทธ๋ž˜ํ”„๊ฐ€ denseํ•˜๋‹ค๋ฉด ์ตœ๋‹จ๊ฒฝ๋กœ๊ฐ€ ์ƒ๊ฐ๋ณด๋‹ค ์งง๊ณ , ๊ทธ๋ž˜ํ”„๊ฐ€ sparseํ•˜๋‹ค๋ฉด $n$๋ฒˆ์˜ ๋‹ค์ต์ŠคํŠธ๋ผ๊ฐ€ $O(nm)$์œผ๋กœ ๋น ๋ฅด๊ธฐ ๋•Œ๋ฌธ์— ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์‹ค์šฉ์ ์œผ๋กœ ์“ฐ์ด๋ ค๋ฉด $m$์ด ํŠน์ •ํ•œ ๋ฒ”์œ„์— ์žˆ๊ณ , ๊ทธ๋ž˜ํ”„๊ฐ€ ๊ฝค ์ปค์•ผ ํ•  ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ด๋ก ์ ์ธ ๋ณต์žก๋„ ๋ถ„์„ ์ธก๋ฉด์—์„œ ๋ณด๋‹ค ํฐ ์˜๋ฏธ๊ฐ€ ์žˆ๋Š” ๋“ฏ ํ•ฉ๋‹ˆ๋‹ค.
  3. ์ด ๋…ผ๋ฌธ์˜ Journal full version์—๋Š” weighted graph์—์„œ ์ตœ๋‹จ๊ฒฝ๋กœ์˜ 3๋ฐฐ ์ดํ•˜๋ฅผ estimateํ•˜๋Š” spanner์— ๋Œ€ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ถ”๊ฐ€๋กœ ๋…ผ์˜๋˜๋Š”๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. weighted graph๋Š” ์ด์ƒํ•œ ์ผ€์ด์Šค๋ฅผ ๋งŒ๋“ค๊ธฐ๊ฐ€ ์‰ฝ๊ธฐ ๋–„๋ฌธ์— ์ด๋ถ€๋ถ„๋„ ์ƒ๋‹นํžˆ ์žฌ๋ฐŒ์„๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  1. ์ด๋ก ์ ์œผ๋กœ ๊ฐ€์žฅ ๋น ๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (Coppersmith-Winograd), ์‹ค์šฉ์ ์œผ๋กœ ๋น ๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (Strassen)์ด ์ด min-plus-mm์—๋„ ์ ์šฉ๊ฐ€๋Šฅํ•จ์ด ์•Œ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.ย โ†ฉ

  2. D. Aingworth, C. Chekuri, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SODA 1996ย โ†ฉ