efficient algorithm for min cut with specified number of vertices
For $n= \frac {|V|} 2$, it's called Minimum Bisection, and it's NP-hard. There exists an $O(\log^{3/2} n)$-approximation: &quot;A polylogarithmic approximation of the minimum bisection&quot;.
If you are interested, the more general problem is splitting into multiple components of the same size, and it is called Balanced Graph Partitioning. For more than 2 parts no finite approximation exists unless P=NP: &quot;Balanced Graph Partitioning&quot; (Andreev, Rakke), since you can't efficiently check if the answer is 0.
If the parts are not necessarily exactly balanced (a small imbalance is allowed), an $O(\log n)$-approximation algorithm exists: &quot;Balanced Partitions of Trees and Applications&quot;.

Some algorithms (also check https://en.wikipedia.org/wiki/Graph_partition and &quot;references&quot; sections of the following papers):

Local search with various flavors: we start with some partitioning and then try to swap vertices between parts to minimize the cut. E.g. we compute &quot;gain&quot; for each vertex (improvement if we move it to another part), and swap vertices with the maximum gain. Its advantage is that you can apply it after any other algorithm.

Spectral partitioning (see e.g. Spectral Graph Theory and Graph Partitioning): uses the second eigenvector of a Laplacian matrix to approximate the partitioning (e.g. by moving the smallest $|V|/2$ coordinates to the first part). Works surprisingly well. However, I'm not sure it can be adapted to the case when you want an unbalanced bisection (e.g. $1:2$ instead of $1:1$).

Linear embedding: &quot;Distributed Balanced Partitioning via Linear Embedding&quot;. We embed vertices into a one-dimensional array while minimizing sum over all pairs of vertices: the distance between them multiplied by the weight of their edge. Then we just split this array into consecutive chunks of required sizes. Didn't work that well in my experience.

(Ads) Our paper: &quot;Multi-Dimensional Balanced Graph Partitioning via
Projected Gradient Descent&quot;, where we used gradient descent to find minimum bisection: for each vertex we introduce a variable which roughly represents a probability that the vertex belongs to the first part, and minimizing the cut reduces to constrained optimization of a quadratic function. It's a bit outperformed in practice by a fine-tuned local search, but it works really well when you have multiple balance constraints.


Aside from the spectral method, all of them can be trivially adapted to partitioning the graph in arbitrary proportions.
There are also standard solvers: KaHIP, METIS. In my experience, KaHIP was pretty good. I'm not sure they support splitting into parts of arbitrary sizes though.