<p>Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph. </p>

<p>This was based on the Ellipsoidal Method. </p>

<p>Finding a Max Cut is the same for Bipartite Graphs as finding a Perfect Matching. Therefore, is seems to me that if you could Count the solutions to Barahona Ellipsoidal Method, you could have fast fpras for Nonnegative Permanent!</p>

<p>Question: Has any work been done in this direction? Thanks in advance!</p>

CC BY-SA 3.0
2013-03-31T05:39:32.287Z
Excuse me, but I don't understand why finding a max cut is the same for bipartite graphs as finding a perfect matching.  A max cut for bipartite graphs is trivial: a proper 2-coloring gives a max cut.
Yoshio Okamoto
CC BY-SA 3.0
2013-03-31T12:40:26.240Z
[Nonnative permanent already has an FPRAS](http://en.wikipedia.org/wiki/Computing_the_permanent#Approximate_computation)
Tyson Williams
<ds.algorithms><reference-request><graph-theory><co.combinatorics><graph-algorithms>
Nonnegative Permanent and Ellipsoidal Method
Zelah 02
# Nonnegative Permanent and Ellipsoidal Method

(Asked by: username_0 on 2013-03-30)

Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph.

This was based on the Ellipsoidal Method.

Finding a Max Cut is the same for Bipartite Graphs as finding a Perfect Matching. Therefore, is seems to me that if you could Count the solutions to Barahona Ellipsoidal Method, you could have fast fpras for Nonnegative Permanent!

Question: Has any work been done in this direction? Thanks in advance!

**Tags:** ds.algorithms, reference-request, graph-theory, co.combinatorics, graph-algorithms

> **Comments:**
> **username_1**: Excuse me, but I don't understand why finding a max cut is the same for bipartite graphs as finding a perfect matching.  A max cut for bipartite graphs is trivial: a proper 2-coloring gives a max cut.  
> **username_2**: [Nonnative permanent already has an FPRAS](http://en.wikipedia.org/wiki/Computing_the_permanent#Approximate_computation)  

---

## 0 answers

