The Node Multiway Cut problem on planar graphs with all terminals incident on the outer face is not NP-complete; it can be solved in polynomial time.

Key Reasoning:

1. Problem Definition: We need to determine if there exists a set ( X \subseteq V(G) ) of size at most ( k ) such that all terminals in ( S \setminus X ) are in distinct connected components of ( G - X ).

2. **Termin...

Yes. The node (vertex) version remains NP-complete even for planar graphs in which all terminals lie on the outer face; in fact, the hardness already holds for three terminals.

Sketch of why (reduction idea):

• Reduce from Planar Vertex Cover, which is NP-complete even on cubic (3-regular), bridgeless planar graphs.
• For such a cubic bridgeless planar graph H, by Tait’s theorem (via the Four-Col...

This is an interesting question about the complexity of a restricted version of the Node Multiway Cut problem. Let me analyze what we know about this problem.

Current State of Knowledge

The Node Multiway Cut problem on planar graphs with terminals on the outer face appears to be open - its complexity status is not definitively known in the literature as of my knowledge.

What We Do Kno...

<think> We are considering the Node Multiway Cut problem on planar graphs where all terminals lie on the outer face. The problem is to decide whether there exists a set of at most k vertices whose removal disconnects all terminals from each other (i.e., each terminal ends up in a separate connected component).

First, recall that the general Node Multiway Cut problem (without planarity or terminal...

Here is what is known and what is not known about the “planar, boundary-terminal” version of Node-Multiway-Cut:

1. Classical Node-Multiway-Cut (in arbitrary graphs) is NP-complete already for 3 terminals (Dahlhaus, Johnson, Papadimitriou, Seymour & Yannakakis ’92).

2. If you restrict to planar graphs but allow the terminals to live anywhere, the vertex-deletion version remains NP-complete by...

Yes, the problem is already NP-complete even if

• the input graph is planar,
• there are only three terminals, and
• the three terminals all lie on the outer face of the given embedding.

Consequently “Node-MULTIWAY-CUT on planar graphs with all terminals on the outer face’’ cannot be solved in polynomial time unless P = NP.

Below we sketch an explicit polynomial reduction from PLANAR-VER...

At the moment we simply do not know.

• Node-Multiway-Cut (vertex-deletion) is NP-complete in general graphs and it stays NP-complete in planar graphs (first observed already by Dahlhaus, Johnson, Papadimitriou & Yannakakis, JCSS 1994; see also later reductions by Marx, Chitnis, Hajiaghayi, …).

• When all terminals lie on one designated face, the situation changes.
– For the edge-deletion...

Of course. Here is a detailed answer synthesized from the state-of-the-art in computational complexity for planar graphs.

Summary of the Answer

Yes, the Node Multiway Cut on Planar Graphs with terminals on the outer face problem is NP-complete.

This result is a well-known, albeit sometimes hard-to-find, piece of folklore in the parameterized complexity and graph algorithms community...

Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?

This is an interesting complexity question about a specific graph cut problem. To clarify the problem:

• We have a planar graph G with terminals S on the outer face
• We want to determine if there's a set X of at most k vertices that, when removed, separates all terminals in S\X (puts them in different ...