What is the status of the following decision problem ?

Input : A graph $G=(V,E)$ embedded in a torus (or more generally a surface of genus $g$), a weight function $w:E \rightarrow \{-1,1\}$

Output : Is there a cut $C\subseteq E$ with negative weight ?

Recall that $C$ is a cut in $G$ if the graph $G\setminus C$ is disconnected.

This problem can be solved in polynomial time in planar graphs. Indeed, there exists a negative cut if and only if there exists a negative cycle in the dual graph. The existance of such a cycle can be decided using Bellman-Ford algorithm.

Unfortunately, a cycle in the dual of a higher genus graph may not correspond to a cut in the primal graph, so that a generalisation of this algorithm seems difficult.

  • $\begingroup$ I don't really know the answer for general genus, but the problem is solvable in polynomial time for planar graphs. $\endgroup$ – Sasho Nikolov Feb 4 at 21:09

For graphs embedded on a surface of genus g with bounded weights $w:E \rightarrow \mathbb{Z}$, you can solve MAX-CUT in time $4^g poly(n)$ using an algorithm of Gallucio, Loebl and Vondrák. Applying it to your instance after taking the opposite weights and looking whether the result is positive seems to solve your problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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