# Weighted Min-Cut in bounded-genus graphs

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.

• I don't really know the answer for general genus, but the problem is solvable in polynomial time for planar graphs. – 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.