I am interested in the following problem.
Node Multiway Cut on Planar Graphs with terminals on the outer face
- Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals which are all incident on the outer face of G.
- Question: Is there a set of vertices $X \subseteq V(G)$ of size at most $k$ such that all vertices of $S \setminus X$ belong to different connected components of $G - X$?
Informally, the problem asks whether all terminals can be separated with k vertex deletions, knowing that all terminals lie on the outer face. If we replace vertex deletions by edge deletions, then this is known to be possible in polynomial time by considering multiway cuts in the planar dual, and relating them to certain kind of Steiner trees ( Efficient Algorithms for k-Terminal Cuts on Planar Graphs, http://www.springerlink.com/content/2b0lxbc4ytqgxj0k/ ). Since the edge-deletion version reduces to the vertex-deletion version, the edge-deletion version seems easier; no reduction in the reverse direction is known.
The question is: is Node Multiway Cut on Planar Graphs with terminals on the outer face NP-complete? The reason I am interested in this problem is that it would provide me with a starting point for another complexity lower bound if this is indeed NP-complete.