# Finding a Maximum Cut With Force Labeled Vertices for Planar Graphs

The maximum cut problem is a combinatorial optimization problem that seeks to partition the vertices of a graph into two sets, $$S$$ and $$T$$, in a way that maximizes the number of edges that cross between the two sets. The problem is tractable for planar graphs. However, the vertices can be assigned to any of the two sets arbitrarily. A variant of the maximum cut problem for planar graphs forces some of the vertices to be in the same set and leaves the other set empty. Is there a fast algorithm to solve the forced variant?

Let $$D$$ be the set of vertices that are forced to one side. Recall that the neighborhoods of vertices in $$D$$ are disjoint. Make a graph $$G'$$ by contracting $$D$$ into a single vertex $$d$$. $$G'$$ is an apex graph - it may well not be planar, but if you take away $$d$$, the rest of the graph must be planar since it is unchanged from $$G$$. Solving Max-Cut on $$G'$$ solves your problem on the original graph $$G$$.
In the other direction, you have an apex graph $$G$$ with an apex $$d$$, and want to solve Max-Cut on this graph. Let $$N(d)$$ be the neighborhood of $$d$$, and let $$r=|N(d)|$$. Make a graph $$G'$$ by deleting $$d$$ and adding a set $$D$$ of $$r$$ vertices, each of them adjacent to exactly one vertex in $$N(d)$$ (all of them different). Adding a bunch of leaves to a planar graph clearly does not destroy planarity, so $$G'$$ is planar. Solving Forced Max-Cut on this graph where every vertex in $$D$$ is forced, solves Max-Cut on the original apex graph $$G$$.