Exponential Divide and Conquer

OPT(U,s,t) is the length of s and t, and you choose the cheapest.

You split the path into two halves in all possible ways. This is called Exponential Divide and Conquer.

m is an intermediate point.

｜S｜=｜｜U｜/2｜+1

T∪S=U

T∩S=m

n is nodes.

∴

ε>0

The exponential space is huge.