Hacker News Reader

Comment by vsskanth | Hacker News Reader

What is it used for

This is a bit like asking what is matrix diaginalization used for. The applications are much too numerous in many different fields of science and engineering. "Graph partition" problems generally search for ways to separate a graph into subgraphs such that some measure is optimized. E.g. resilience of network connections, immunizations, some error correction algorithms, optimizing flow of stuff through nodes, logistics. This list probably barely scratches the surface.

Edit: my comment sounds a bit rude on second read. My apologies, it is the limitations of this medium.

Thanks. I wasnt being snarky. I really didn't know what such algorithms are used for and the paper didn't mention examples either.

This problem is assumed to be common knowledge among graph theory specialists.

Everyone on Hacker News is not assumed to be graph theory specialists.

That's assumed common knowledge for non-graph theory specialists.

I would say it's common knowledge for anyone with a CS degree.

its a bit advanced. Many university curriculums just skim through max flow min cut algorithms in a week or two as part of the algorithms class.

Isn’t graph partition a form of diagonalization?

What is the relationship? I guess most of us are not spectral graph theory experts. Are you looking at the adjacency matrix or the Laplacian matrix?

http://www.math.ucsd.edu/~fan/talks/mlg.pdf

Okay yeah, Cheeger's inequality and all those are straight up graduate-level theoretical computer science. Definitely not something you can just throw into a discussion assuming people know what you're talking about!

There are tons of applications, but many of them come down to variations on breaking up some universe of things to minimize the downsides of breaking them up.

If you have a bunch of chat users and a bunch of chat servers, and you want to figure out how to assign users to servers in a way that minimizes the number of messages going between your chat servers, then you're solving a min cut problem on a graph where users are nodes, edges are communications, and edge weights are communications volumes. Any links that you cut in order to partition the graph end up being cross-server traffic.

Thank you. That's really an excellent example. I recall the early days of IRC networks being plagued by frequent "splits" as different chunks of the graph became disconnected, which was largely a result of the architecture of the servers and is probably the worst-case scenario for this sort of thing, but your example is immediately graspable.

It is used for calculate the maximum flow of a flow network. https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Appli...

The max flow is the prime to the min-cut. But you don't use min-cut to find the max flow.

I don’t understand the distinction you’re drawing. Can you explain? Max flow and min cut are entirely dual. Which one you use is more a matter of convenience

What I meant was that if you wish to find the maximum flow, you'd use push-relabel or another max-flow algorithm instead of finding the min-cut first and then building the max-flow solution from there.

Well if you have designated source (s) and sink (t) in a directed network, then yes, finding max s-t flow and min s-t cut are dual problems. Here the paper seems to be dealing with undirected graphs and all cuts in them, not necessarily between a given pair of vertices, so it is slightly different.

It is a fundamental graph problem with many applications in different fields, such as network reliability, where assuming equal failure probability edges, the smallest edge cut in the network has the highest chance to disconnect the network; in VLSI design, where the minimum cut can be used to minimize the number of connections between microprocessor blocks; and as a subproblem in branch-and-cut algorithms for the Traveling Salesman Problem (TSP) and other combinatorial problems.

(Copy paste from viecut github repo)

Thanks.

Graph cut is useful in computer vision.

Still used extensively for background-forground segmentation in e.g. Photoshop, I am guessing.

Research these days mostly focuses on deep learning though.

Ban half of Twitter accounts so that as little people as possible notice.

"Eschew flamebait. Don't introduce flamewar topics unless you have something genuinely new to say. Avoid unrelated controversies and generic tangents."

https://news.ycombinator.com/newsguidelines.html

Reply on news.ycombinator.com