A friend shared this paper with me. It was published today, and seems to suggest that max-flow/min-cut can be exactly computed in almost linear time in the number of edges for general graphs.

I haven't gotten much time to read through it, but I thought it would be interesting to post it here for discussion.