Back to : advanced-algorithms
Contents

์ฐธ๊ณ  : Stanford CS267 lecture note

Subgraph Isomorphism

๊ทธ๋ž˜ํ”„ $G(V_G, E_G)$์™€, ๋‹ค๋ฅธ ๊ทธ๋ž˜ํ”„ $H = (V_H, E_H)$ ์— ๋Œ€ํ•ด, subgraph isomorphism $f : V_H \to V_G$ ๋Š” $(u, v) \in E_H$ ์ด๋ฉด $(f(u), f(v)) \in E_G$ ์ธ vertex mappint $f$๋กœ ์ •์˜ํ•œ๋‹ค. ์ผ๋ฐ˜์ ์ธ ๊ทธ๋ž˜ํ”„ $G$์—์„œ $H$๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ๋Š” NP-Hard์ด๊ณ , ๋‚˜ํ•œํ…Œ๋Š” ์ฒซ ๋žฉ ์ธํ„ด ์ฃผ์ œ๊ธฐ๋„ ํ•œ ๋งค์šฐ ์žฌ๋ฏธ์žˆ๋Š” ๋ฌธ์ œ์ธ๋ฐ, ์ด ํฌ์ŠคํŒ…์—์„œ๋Š” ํŠน์ˆ˜ํ•œ ์ผ€์ด์Šค๋“ค๋งŒ ๋‹ค๋ฃฐ ์˜ˆ์ •์ด๋‹ค.

์ผ๋ฐ˜์ ์œผ๋กœ, ์ด๋Ÿฌํ•œ ๋ฌธ์ œ๋ฅผ ์ ‘๊ทผํ•˜๋Š” ๊ฒฝ๋กœ๋Š” ํฌ๊ฒŒ ๋‘๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค. TSP, Vertex cover, Ham-path ๋“ฑ๋“ฑ๋„ ๋‹ค ๋น„์Šทํ•œ ๋Š๋‚Œ์ธ๋“ฏ ํ•˜๋‹ค.

  • Heuristicํ•˜๊ฒŒ, ์ผ๋ฐ˜์ ์ธ ๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•ด ๋น ๋ฅด๊ฒŒ (์‚ฌ์‹ค์€ ๋œ ๋Š๋ฆฌ๊ฒŒ ๋ผ๋Š” ๋ง์ด ๋งž์„ ์ง€๋„โ€ฆ) ํ‘ธ๋Š” ๋ฐฉ๋ฒ•์„ ์ฐพ์œผ๋ ค๋Š” ๋…ธ๋ ฅ. ๋‹คํ•ญ ์‹œ๊ฐ„์„ ๋ชฉํ‘œ๋กœ ํ•˜์ง€๋Š” ์•Š๋Š”๋‹ค.
  • ํŠน์ •ํ•œ ํ˜•ํƒœ์˜ ๊ทธ๋ž˜ํ”„ (ํ‰๋ฉด ๊ทธ๋ž˜ํ”„, $k$-cycle, bipartite graph, โ€ฆ.) ๋“ฑ๋“ฑ์— ๋Œ€ํ•ด ๋‹คํ•ญ ์‹œ๊ฐ„ ๋˜๋Š” ์ด์— ๊ทผ์ ‘ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์—ฐ๊ตฌํ•˜๋Š” ๊ฒฝ์šฐ. ์ข€๋” classicํ•œ ๋Š๋‚Œ๋„ ์žˆ๊ณ โ€ฆ์•„๋ฌดํŠผ ๊ทธ๋ ‡๋‹ค. ๊ทธ๋ž˜ํ”„์˜ classification๊ณผ๋„ ๋งค์šฐ ๊นŠ์€ ์—ฐ๊ด€์ด ์žˆ๊ณ , ๋ฌด์Šจ 3-colorable graph์— ๋Œ€ํ•ด์„œ๋งŒ ์„ฑ๋ฆฝํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐ™์€ ์‹ ๊ธฐํ•œ ๊ฒƒ๋“ค์„ ์—ฐ๊ตฌํ•˜๋Š”๋“ฏ ํ•˜๋‹ค.

์ž๋ช…ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€, $V_G$์—์„œ ๋ชจ๋“  ๊ฐ€๋Šฅํ•œ $V_H$๊ฐœ๋ฅผ ์กฐํ•ฉํ•ด์„œ, ์ผ์ผํžˆ ๊ฐ€๋Šฅํ•œ์ง€ ํ™•์ธํ•˜๋Š” ๊ฒƒ์œผ๋กœ, $V_G$ ๋ฅผ $N$, $E_G$์˜ ํฌ๊ธฐ๋ฅผ $M$, $V_H$์˜ ํฌ๊ธฐ๋ฅผ $n$์ด๋ผ ํ•  ๋•Œ $O(MN^n)$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฐ๋‹ค. ์ฐพ์•„์•ผ ํ•  ๊ทธ๋ž˜ํ”„๊ฐ€ ์ •ํ•ด์ ธ ์žˆ๋‹ค๋ฉด $M$์„ ์‹œ๊ฐ„๋ณต์žก๋„ ๊ณ„์‚ฐ์—์„œ๋Š” ์ œ๊ปด๋„ ๋˜๊ณ , ๊ทธ๋ž˜๋„ $O(N^n)$ ์‹œ๊ฐ„์ธ ๊ฒƒ์€ ๋ณ€ํ•จ์ด ์—†๋‹ค.

Finding Triangles

$n$๊ฐœ์˜ ์ •์ ๊ณผ $m$๊ฐœ์˜ ๊ฐ„์„ ์ด ์žˆ๋Š” ๊ทธ๋ž˜ํ”„์—์„œ ์‚ผ๊ฐํ˜•์„ ์ฐพ์œผ๋ ค๊ณ  ํ•  ๋•Œ, ์œ„ ์ž๋ช…ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ $O(n^3)$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฐ๋‹ค. ์ด๋ณด๋‹ค ๋‚˜์€ ๋ฐฉ๋ฒ•์ด ์žˆ๋Š”์ง€ ์ƒ๊ฐํ•ด ๋ณด์ž.

๋ฌธ์ œ๋ฅผ ๋ช…ํ™•ํžˆ ์ •์˜ํ•˜๊ธฐ ์œ„ํ•ด, ๋ฌธ์ œ์˜ ๋‹ต์„ True / False ๋กœ ๋‹ตํ•˜๊ธฐ๋กœ ํ•˜์ž. ์ฆ‰, ์‚ผ๊ฐํ˜•์ด ์žˆ๋Š”์ง€ ์œ ๋ฌด๋งŒ ํŒ์ •ํ•˜๊ณ , (์‹œ๊ฐ„์  ์†ํ•ด๊ฐ€ ์—†๋‹ค๋ฉด ์‚ผ๊ฐํ˜•์„ ๋Œ๋ ค์ค„ ์ˆ˜ ์žˆ๊ฒ ์ง€๋งŒ)

$O(mn)$ ์•Œ๊ณ ๋ฆฌ์ฆ˜

๋‹ค์Œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ƒ๊ฐํ•˜๊ธฐ ๋ณ„๋กœ ์–ด๋ ต์ง€ ์•Š๊ณ , $O(mn)$ ์ธ ๊ฒƒ๋„ ๊ฑฐ์˜ ์ž๋ช…ํ•˜๋‹ค.

pseudocode
for v in V: 
  for s, t in N(v):
    if (s, t) in E:
      return (v, s, t)

์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์†Œ์š” ์‹œ๊ฐ„์€ ๊ฒฐ๊ตญ $\sum_v d_v^2$ ์ธ๋ฐ, \(\sum_v d_v^2 \leq n \sum_v d_v \leq 2mn\) ์ด๋ฏ€๋กœ, ์ด๋Š” $O(mn)$ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.
์‰ฝ๊ฒŒ ์ƒ๊ฐ๋‚˜๋Š” ์•„์ด๋””์–ด๊ฐ€ ๋Š˜ ๊ทธ๋ ‡๋“ฏ, ํฐ ์˜๋ฏธ๊ฐ€ ์žˆ์ง€๋Š” ์•Š๋‹ค. dense graph์—์„œ $m = O(n^2)$ ์ด๋ผ์„œ ์ตœ์•…์˜ ๊ฒฝ์šฐ ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ ์ „ํ˜€ ๊ฐœ์„ ๋˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. (๋ฌผ๋ก  ์‹ค์ œ๋กœ๋Š” ์กฐ๊ธˆ ๋น ๋ฅด๊ฒ ์ง€๋งŒ).

$O(n^w)$ ์•Œ๊ณ ๋ฆฌ์ฆ˜

ํ–‰๋ ฌ์„ ์ด์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค. ๋จผ์ €, ๊ทธ๋ž˜ํ”„์˜ adjacency matrix $A$๋ฅผ ์ƒ๊ฐํ•˜์ž. ์ด๋•Œ, $A[i, j]$ ๋Š” (i, j) edge๊ฐ€ ์žˆ๋Š”์ง€ ์—ฌ๋ถ€์ด๊ณ , $A^2[i, j] > 0$ ์€ $A[i, k] = 1, A[k, j] = 1$ ์ธ $k$๊ฐ€ ์žˆ๋Š”์ง€ ์—ฌ๋ถ€๋ฅผ ์•Œ๋ ค์ค€๋‹ค. ๋”ฐ๋ผ์„œ, $A^2$ ์„ ๊ณ„์‚ฐํ•œ ํ›„, $A^2[i, j]$ ๊ฐ€ 1์ด๊ณ  $A[i, j]$ ๊ฐ€ 1์ด๋ฉด (์‹ค์ œ๋กœ ์ฐพ์ง€๋Š” ๋ชปํ•˜์ง€๋งŒ) ์‚ผ๊ฐํ˜•์ด ์กด์žฌํ•œ๋‹ค๋Š” ์‚ฌ์‹ค์€ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ์šฐ๋ฆฌ๋Š” ์•ž์„œ ์ด๊ฑธ ๋ชฉํ‘œ๋กœ ํ–ˆ์œผ๋ฏ€๋กœ, ํ–‰๋ ฌ ๊ณฑ์…ˆ ํ•˜๋Š” ์‹œ๊ฐ„ + $O(n^2)$ ์— ์‚ผ๊ฐํ˜• ์ฐพ๊ธฐ๊ฐ€ ๊ฐ€๋Šฅํ•จ์„ ๋ณด์˜€๋‹ค.

ํ˜„์žฌ ์•Œ๋ ค์ง„ ํ–‰๋ ฌ ๊ณฑ์…ˆ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘ ๊ฐ€์žฅ ๋น ๋ฅธ Coppersmith-winograd ๋ฐ ๊ทธ ๊ฐœ์„ ๋œ ๋ฒ„์ „๋“ค (Le Gall, Williams ๋“ฑ) ์ด $O(n^{2.37})$ ์ •๋„์ด๊ณ , ์ด ๋ถ€๋ถ„์ด ๋” ๋นจ๋ผ์งˆ์ง€ ์–ด๋–จ์ง€๋Š” ์•Œ ์ˆ˜ ์—†์ง€๋งŒ $O(n^2)$ ๋ณด๋‹ค๋Š” ๋Š๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์— ํ–‰๋ ฌ ๊ณฑ์…ˆ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ $O(n^w)$ ๋ผ ์“ฐ๊ณ , ๋Œ€์ถฉ ํ˜„์žฌ๋กœ์จ๋Š” 2.37 ์ •๋„์ž„์„ ๊ธฐ์–ตํ•˜์ž.

๋‹ค๋งŒ $w = 2.37$ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ˜„์žฌ๋กœ์„œ๋Š” ์‹ค์šฉ์ ์œผ๋กœ ์‚ฌ์šฉํ•˜๊ธฐ ์–ด๋ ต๋‹ค. ํ˜„์‹ค์ ์œผ๋กœ ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋„ˆ๋ฌด ํฐ ์ƒ์ˆ˜๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์–ด ์‹ค์ œ๋กœ ๋‹ค๋ฃฐ ์ˆ˜ ์žˆ๋Š” ํฌ๊ธฐ์˜ ํ–‰๋ ฌ์— ๋Œ€ํ•ด์„œ ์ „ํ˜€ ๋น ๋ฅด์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์‹œ๊ฐ„ ๋ณต์žก๋„ ์ฆ๋ช…์— ์˜์˜๊ฐ€ ์žˆ๋‹ค. ์‹ค์šฉ์ ์œผ๋กœ ๋น ๋ฅธ ๋ฐฉ๋ฒ•์€ Strassen์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ, $w = \log_2 7 \approx 2.81$ ์ด์ง€๋งŒ ์‹ค์ œ๋กœ๋Š” ๋” ๋น ๋ฅด๋‹ค.

๊ต‰์žฅํžˆ ์žฌ๋ฐŒ๋Š” ์‚ฌ์‹ค ์ค‘ ํ•˜๋‚˜๋กœ, ๋‹ค์Œ ๋ช…์ œ๊ฐ€ ์žˆ๋‹ค. ์ฆ๋ช…์€ trace๋ฅผ ํ•ฉ์œผ๋กœ ์“ฐ๊ณ  ๋‚˜์„œ ์กฐ๊ฑด์„ ์ž˜ ์ƒ๊ฐํ•ด ๋ณด๋ฉด ๊ทธ๋ ‡๊ฒŒ ์–ด๋ ต์ง€ ์•Š์€๋ฐ, ํžŒํŠธ๋ฅผ ์กฐ๊ธˆ ์ œ์‹œํ•˜์ž๋ฉด 6์€ $i, j, k$ ์˜ ์‚ผ๊ฐํ˜•์ด ์ˆœ์„œ๊ฐ€ ์—†์œผ๋ฏ€๋กœ $3!$์„ ๋‚˜๋ˆ„์–ด ์ค€ ๊ฒƒ์ด๋‹ค.

\[\text{Tr}(A^3) = \text{number of triangles of graph A}\]

์–ด์ฐจํ”ผ $A^3$์˜ trace ์—ฐ์‚ฐ์„ ํ–‰๋ ฌ ๊ณฑ์…ˆ๋ณด๋‹ค ๋น ๋ฅด๊ฒŒ ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์—ฐ๊ตฌ๋˜์ง€ ์•Š์•˜๊ธฐ ๋•Œ๋ฌธ์— ์šฐ๋ฆฌ์˜ ํฐ ๊ด€์‹ฌ์‚ฌ๋Š” ์•„๋‹ˆ๋‹ค.

$O(m^{(w + 1)/2})$ ์•Œ๊ณ ๋ฆฌ์ฆ˜

์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์œ„ ๋‘ ์•„์ด๋””์–ด๋ฅผ ์ ๋‹นํžˆ ์„ž์–ด๋‚ด๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.

์–ด๋–ค parameter $t$๋ฅผ ์žก์•„์„œ, degree๊ฐ€ $t$ ์ดํ•˜์ธ ์ •์ ๊ณผ ์ด์ƒ์ธ ์ •์ ์œผ๋กœ ๋‚˜๋ˆ„์ž. ์ดํ•˜์ธ ์ •์ ๋“ค (low-degree) ์ •์ ์— ๋Œ€ํ•ด์„œ, $O(mn)$ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋น„์Šทํ•œ ๊ฒƒ์„ ๋Œ๋ฆฐ๋‹ค. ์ด๋Ÿฌ๋ฉด, low-degree ์ •์ ์„ ํ•˜๋‚˜๋ผ๋„ ํฌํ•จํ•˜๋Š” ๋ชจ๋“  ์‚ผ๊ฐํ˜•์„ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค. ์ด์ œ low-degree ์ •์ ์€ ๋ชจ๋‘ ์ƒ๊ด€ ์—†์œผ๋ฏ€๋กœ ์‚ญ์ œํ•œ๋‹ค.

๋‚จ์€ ์ •์ ๋“ค์€ ๋ชจ๋‘ high-degree์ž„์ด ๋ณด์žฅ๋œ๋‹ค. ๋‚จ์€ ์ •์ ๋“ค์— ๋Œ€ํ•ด์„œ๋Š” ์œ„์˜ ํ–‰๋ ฌ ๊ณฑ์…ˆ์„ ๋Œ๋ฆฌ์ž. ์ด์ œ, ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ฆ๋ช…ํ•ด ๋ณด๋ฉด,

๋ชจ๋“  ์ •์ ์˜ degree์˜ ํ•ฉ์ด $2m$ ์ด๋ฏ€๋กœ, ์ตœ๋Œ€ $2m/t$ ๋งŒ high-degree vertex๊ฐ€ ์กด์žฌํ•  ์ˆ˜ ์žˆ๋‹ค. ๋˜ํ•œ, low-degree ์ •์ ์— ๋Œ€ํ•ด์„œ๋Š”, ๊ฐ๊ฐ์˜ degree๊ฐ€ $t$ ์ดํ•˜์ด๊ณ , degree์˜ ์ดํ•ฉ์ด $2m$ ์ดํ•˜์ด๋ฏ€๋กœ, degree์˜ ์ œ๊ณฑ์˜ ํ•ฉ์€ $2mt$๋ฅผ ๋„˜์ง€ ์•Š๋Š”๋‹ค. Asymptotically, ์ด๋ ‡๊ฒŒ ๊ตฌ์„ฑ๋œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š”

\(O((m / t)^w + mt)\) ์ด๋ฉฐ, ์ด๋ฅผ ์ตœ์†Œํ™”ํ•˜๋Š” $t$๋ฅผ ์ง์ ‘ ์ฐพ์œผ๋ฉด $t^{w+1} = m^{w-1}$์ผ ๋•Œ์ž„์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ์šฐ๋ฆฌ๊ฐ€ ์•„๋Š” ์ตœ์„ ์˜ $w = 2.37$ ์„ ์“ฐ๋ฉด ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $O(m^{1.41})$ ์ด ๋œ๋‹ค.

Why triangles?

์™œ ์‚ผ๊ฐํ˜•์„ ์ฐพ๋Š” ๋ฌธ์ œ๊ฐ€ ์ค‘์š”ํ•œ๊ฐ€? ๋‹น์—ฐํžˆ, ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ž๋ช…ํ•˜์ง€ ์•Š์€ ๊ฐ€์žฅ ์‰ฌ์šด ๊ทธ๋ž˜ํ”„์ด๊ธฐ๋„ ํ•˜์ง€๋งŒ, ๋‹ค์Œ์˜ ์ •๋ฆฌ ๋•Œ๋ฌธ์ด๊ธฐ๋„ ํ•˜๋‹ค.

Theorem (Nesetril, Poljak) $n$๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ–๋Š” ๊ทธ๋ž˜ํ”„์—์„œ $O(n^t)$์‹œ๊ฐ„์— ์‚ผ๊ฐํ˜•์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์กด์žฌํ•œ๋‹ค๋ฉด, $3k$๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ–๋Š” fixed subgraph $H$๋ฅผ $O(n^{tk})$ ์‹œ๊ฐ„์— ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค.

๊ฐ„๋‹จํžˆ ๋งํ•ด์„œ, ์‚ผ๊ฐํ˜•์„ ์ฐพ๋Š” ๋ฌธ์ œ๋Š” ๋ชจ๋“  $k$๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ–๋Š” graph isomorphism์œผ๋กœ ํ™•์žฅํ•  ์ˆ˜ ์žˆ์Œ์„ ์˜๋ฏธํ•œ๋‹ค. ์‚ผ๊ฐํ˜•์„ $O(n^{2.5})$์— ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค๋ฉด, 9๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ–๋Š” subgraph๋Š” $O(n^{7.5})$ ์— ์ฐพ์„ ์ˆ˜ ์žˆ๋Š” ์‹์ด๋‹ค. ๋ฌผ๋ก  ๋”์ฐํ•˜์ง€๋งŒ, brute-force๋ณด๋‹ค๋Š” ํ›จ์”ฌ ๋น ๋ฅด๋‹ค!

Nesetril-Poljak Subgraph isomorphism

์œ„ ์ •๋ฆฌ์˜ ์ฆ๋ช…์€ ์‚ฌ์‹ค Nesetril๊ณผ Poljak์ด 1985๋…„์— ์ œ์‹œํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. $3k$๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ–๋Š” subgraph๋ฅผ $H$๋ผ ํ•˜๊ณ , ์ด๋ฅผ ์•„๋ฌด๋ ‡๊ฒŒ๋‚˜ $k$๊ฐœ์˜ ๋…ธ๋“œ์”ฉ ๋Š์–ด์„œ $H_1, H_2, H_3$์„ ๋งŒ๋“ค์ž. ๊ฐ $i = 1, 2, 3$ ์— ๋Œ€ํ•ด, $h_{j}^{i}$ ๋ฅผ $H_i$์˜ $j$๋ฒˆ์งธ ์ •์ ์ด๋ผ๊ณ  ํ•˜์ž.

$Gโ€™$ ์„ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ํ•œ๋‹ค. $G$์—์„œ ์ •์ ์„ $k$๊ฐœ (์ˆœ์„œ๋ฅผ ๊ฐ€์ง€๊ณ ) ๋ฝ‘์€, $n^k$ ๊ฐœ์˜ tuple์— ๋Œ€ํ•ด์„œ, ์ด tuple์ด (์ •์ ์˜ ์ˆœ์„œ๋ฅผ ์ง€ํ‚ค๋ฉด์„œ) $H_1, H_2, H_3$๊ณผ isomorphicํ•œ์ง€ ํ™•์ธํ•ด์„œ, $H_i$์™€ isomorphicํ•˜๋‹ค๋ฉด $(i, [tuple])$ ์„ ํ†ต์งธ๋กœ ํ•˜๋‚˜์˜ ์ •์ ์œผ๋กœ ์‚ผ๋Š”๋‹ค. ์ฆ‰, ๋ฌด๋ ค ์ตœ๋Œ€ $3n^k$๊ฐœ์˜ ์ •์ ์„ ๊ฐ–๋Š” ๊ฑฐ๋Œ€ํ•œ ๊ทธ๋ž˜ํ”„๋ฅผ ๋งŒ๋“ ๋‹ค.

์ด์ œ, $(i, tuple_1)$์™€ $(j, tuple_2)$ ๋ฅผ $Gโ€™$์˜ ์ •์  2๊ฐœ๋กœ ์žก๊ณ , $(tuple_1 \cup tuple_2)$๊ฐ€ $H_i \cup H_j$ ์™€ isomorphicํ•˜๋ฉด $(i, tuple_1)$ node์™€ $(j, tuple_2)$ node ์‚ฌ์ด์˜ edge๋ฅผ ์ž‡๋Š”๋‹ค. (๋‹จ, tuple ๋‘๊ฐœ๊ฐ€ disjointํ•ด์•ผ๋งŒ ํ•œ๋‹ค)

์–ด๋ ต์ง€ ์•Š๊ฒŒ, $H$๊ฐ€ $G$์— subgraph๋กœ ๋“ค์–ด ์žˆ๋‹ค๋ฉด, $Gโ€™$์— ์‚ผ๊ฐํ˜•์ด ์žˆ์Œ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ $Gโ€™$์— ์‚ผ๊ฐํ˜•์ด ์žˆ์œผ๋ฉด ๊ทธ๊ฑธ ์ž˜ ์ด์šฉํ•ด์„œ $H$๋ฅผ ์—ญ์œผ๋กœ constructํ•  ์ˆ˜๋„ ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ, ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ •๋‹น์„ฑ์€ ์‰ฝ๊ฒŒ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„๋Š”, ์ด $O(n^k)$๊ฐœ์˜ ๋…ธ๋“œ๋“ค ์‚ฌ์ด์— ๋ชจ๋‘ edge ์—ฌ๋ถ€๋ฅผ ํ™•์ธํ•ด์•ผ ํ•˜๋ฏ€๋กœ $O(k^2 n^{2k})$ ์‹œ๊ฐ„์— ๊ฑธ์ณ graph construction์„ ํ•ด์•ผ ํ•˜๊ณ , $O(n^{k})$๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ–๋Š” ๊ทธ๋ž˜ํ”„์— $O(N^t)$ ์‚ผ๊ฐํ˜• ์ฐพ๊ธฐ๋ฅผ ํ•ด์•ผ ํ•˜๋ฏ€๋กœ $O(n^{tk})$ ์‹œ๊ฐ„์ด ๋“ ๋‹ค. $k$๋ฅผ ์ƒ์ˆ˜๋กœ ์ƒ๊ฐํ•˜๊ธฐ๋กœ ํ–ˆ์œผ๋ฏ€๋กœ ์ „๋ถ€ $O(n^{tk})$์ž„์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

์ฐธ๊ณ ๋กœ, ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์กฐ๊ธˆ๋งŒ ์ž˜ ๋ณ€ํ˜•ํ•˜๋ฉด $O(n^{tk + q})$ ์‹œ๊ฐ„์— $3k + q$ ($q = 1, 2$) ์— ๋Œ€ํ•œ ๊ฒฝ์šฐ๋„ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. ๋˜ํ•œ, ์šฐ๋ฆฌ๋Š” $t \geq 2$ ์ž„์„ ์•Œ๊ณ  ์žˆ๋Š”๋ฐ, ์ผ๋‹จ ๊ทธ๋ž˜ํ”„๋ฅผ ๋‹ค ๋ฐ›๊ธฐ๋Š” ํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ(โ€ฆ). ๊ทธ๋Ÿฌ๋ฏ€๋กœ ์ด ๋ฐฉ๋ฒ•์œผ๋กœ ์šฐ๋ฆฌ๊ฐ€ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ํ•œ์€ $O(n^{2k})$ ์‹œ๊ฐ„์— $3k$์งœ๋ฆฌ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๊ฒƒ์ด๋‹ค. (Naive๋Š” $O(n^{3k})$ ์ด๋ฏ€๋กœ, ์–ด์จŒ๋“  ์ƒ๋‹นํ•œ ๋ฐœ์ „์ด๋‹ค).