17

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

Glorfindel
  • 359
  • 1
  • 4
  • 10
Bart Jansen
  • 5,265
  • 21
  • 39
  • I think that this is equivalent to solving vertex weighted Steiner tree where all terminals on the outer face. The very loose idea would be something like: consider the boundary path between every pair of consecutive terminals you want to separate; connect all the vertices on that path to a new vertex, which becomes a terminal for the Steiner tree problem. Now all these Steiner terminals will all lie on the same face. This should be solvable in polynomial time using the algorithm of Erickson et al. (http://www.jstor.org/pss/3689922). – zotachidil Nov 15 '11 at 02:26
  • I know for sure that the algorithm I mentioned works for edge weighted Steiner tree, but one should be able to adapt it to work for vertices. – zotachidil Nov 15 '11 at 02:28

0 Answers0