CODEWITHSUNDEEP
algorithmgraphgraph-theorygraph-algorithm
eddyxu
eddyxu

Reputation: 668

Find a cut in graph that divides the graph to approximately equal two subgraphs

Is there a practical algorithm (not NP-hard) that can cut a graph into two approximately equal sub-graphs (e.g., One sub-graph has 40%-50% vertices), in the meantime, prove that the cut is the minimal possible cut given the condition that two sub-graphs have approximately equal number of vertices?

Upvotes: 3

Views: 1293

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

This is not exactly sparsest cut; it's balanced cut, also NP-hard, as described in Chapter 8 of Dasgupta, Papadimitriou, and Vazirani. The canonical version of the sparsest cut problem does not allow specification of the partition size.

There are two streams of research on graph partitioning problems: algorithms with worst-case approximation guarantees, of which Arora–Rao–Vazirani is the main result of interest to you, and algorithms without worst-case guarantees, which are evaluated by their practical performance (random example I have no experience with: METIS). Even though I don't know it very well, I'd be inclined to steer you toward the latter line of work; a priori, O(√log n) bicriteria approximation is just not a very useful guarantee, and there's likely to be some nontrivial algorithms engineering to get ARV working well at scale in the first place.

Upvotes: 5

Related Questions