<p>For graphs embedded on a surface of genus g with bounded weights <span class="math-container">$w:E \rightarrow \mathbb{Z}$</span>, you can solve MAX-CUT in time <span class="math-container">$4^g poly(n)$</span> using <a href="https://link.springer.com/article/10.1007/PL00011425" rel="nofollow noreferrer">an algorithm of Gallucio, Loebl and Vondrák</a>. Applying it to your instance after taking the opposite weights and looking whether the result is positive seems to solve your problem.</p>

CC BY-SA 4.0
2019-02-05T16:57:07.143Z
2019-02-05T16:57:07.143Z
Arnaud
<p>What is the status of the following decision problem ?</p>

<p><strong>Input :</strong> A graph <span class="math-container">$G=(V,E)$</span> embedded in a torus (or more generally a surface of <em>genus</em> <span class="math-container">$g$</span>), a weight function <span class="math-container">$w:E \rightarrow \{-1,1\}$</span></p>

<p><strong>Output :</strong> Is there a cut <span class="math-container">$C\subseteq E$</span> with negative weight ?</p>

<p>Recall that <span class="math-container">$C$</span> is a cut in <span class="math-container">$G$</span> if the graph <span class="math-container">$G\setminus C$</span> is disconnected.</p>

<p>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 <em>dual</em> graph. The existance of such a cycle can be decided using Bellman-Ford algorithm.</p>

<p>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.</p>

CC BY-SA 4.0
2019-02-04T21:09:10.013Z
I don't really know the answer for general genus, but the problem is solvable in polynomial time for planar graphs.
Sasho Nikolov
<cc.complexity-theory><planar-graphs><max-cut>
Weighted Min-Cut in bounded-genus graphs
Mathieu Mari
# Weighted Min-Cut in bounded-genus graphs

(Asked by: username_0 on 2019-02-04)

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.

**Tags:** cc.complexity-theory, planar-graphs, max-cut
> **Comments:**
> **username_1**: I don't really know the answer for general genus, but the problem is solvable in polynomial time for planar graphs.  

---

## 1 answers

### Answer by username_2 on 2019-02-05. Score: 2

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](https://link.springer.com/article/10.1007/PL00011425). Applying it to your instance after taking the opposite weights and looking whether the result is positive seems to solve your problem.


---

