Weighted Min-Cut in bounded-genus graphs

Question

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.

Answer 1

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.