2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

A special case of your problem, where the neighborhoods of the vertices you force together are disjoint, is equivalent to solving (regular) Max-Cut on an apex graph (a graph that is planar, save for one vertex).

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

So, what is the complexity of Max-Cut on apex graphs? The ISGCI page says it's NP-hard. Bear in mind that I haven't read their reference, but it's probably true.

$\endgroup$
1
  • $\begingroup$ The papers that were referenced on ISGCI study a special class of apex graphs where removing an apex gives a planar cubic graph as an output and they show that finding a maximum cut is hard. Thus, the reduction from the apex case to the original problem yields a hardness result. $\endgroup$ Commented Mar 17 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.