MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 fixed tex. Hope I used the right symbol.

This is not a direct answer to Daniel's question, but it could be potentially useful.

Suppose we replace the unlink in the question by a split link $L$ whose components $K_1, \ldots, K_n$ are prime, non-trivial knots. Then, the $K_i$ are separated by a collection of essential two-spheres $S_j$, but these spheres can of course look extremely complicated in a given diagram of $L$. The analogue of Daniel's question in this context is:

Does there exist a fast geometric algorithm that will identify the essential two-spheres in the prime decomposition of $S^3 \setminus L$?

Now, there is a paper of Marc Lackenby that provides some insight into this question: 

http://arxiv.org/abs/0805.4706

Starting from an arbitrary diagram of the connected sum $K_1 # \sharp \ldots # \sharp K_n$, he cuts it into a distant union (split link) $L = K_1 \cup \ldots \cup K_n$, and proves that the essential two-spheres separating these components have to look (relatively) simple in this handle structure. I am very far from an expert on algorithms, but it seems that knowing the essential two-spheres are not too complicated ought to guide a way to "pull them apart", which is what you're after.
show/hide this revision's text 2 added 12 characters in body

This is not a direct answer to Daniel's question, but it could be potentially useful.

Suppose we replace the unlink in the question by a split link $L$ whose components $K_1, \ldots, K_n$ are prime, non-trivial knots. Then, the $K_i$ are separated by a collection of essential two-spheres $S_j$, but these spheres can of course look extremely complicated in a given diagram of $L$. The analogue of Daniel's question in this context is:

Does there exist a fast geometric algorithm that will identify the essential two-spheres in the prime decomposition of $S^3 \setminus L$?

Now, there is a paper of Marc Lackenby that provides some insight into this question: 

http://arxiv.org/abs/0805.4706

Starting from an arbitrary diagram of the connected sum $K_1 # \ldots # K_n$, he cuts it into a disjoint distant union (split link) $L = K_1 \cup \ldots \cup K_n$, and proves that the essential two-spheres separating these components have to look (relatively) simple in this handle structure. I am very far from an expert on algorithms, but it seems that knowing the essential two-spheres are not too complicated ought to guide a way to "pull them apart", which is what you're after.
show/hide this revision's text 1

This is not a direct answer to Daniel's question, but it could be potentially useful.

Suppose we replace the unlink in the question by a split link $L$ whose components $K_1, \ldots, K_n$ are prime, non-trivial knots. Then, the $K_i$ are separated by a collection of essential two-spheres $S_j$, but these spheres can of course look extremely complicated in a given diagram of $L$. The analogue of Daniel's question in this context is:

Does there exist a fast geometric algorithm that will identify the essential two-spheres in the prime decomposition of $S^3 \setminus L$?

Now, there is a paper of Marc Lackenby that provides some insight into this question: 

http://arxiv.org/abs/0805.4706

Starting from an arbitrary diagram of the connected sum $K_1 # \ldots # K_n$, he cuts it into a disjoint union $L = K_1 \cup \ldots \cup K_n$, and proves that the essential two-spheres separating these components have to look (relatively) simple in this handle structure. I am very far from an expert on algorithms, but it seems that knowing the essential two-spheres are not too complicated ought to guide a way to "pull them apart", which is what you're after.