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 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.

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.

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.

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 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.