Finding a subset of fixed size of a graphs vertex set that minimizes 'surface area'. AKA finding min cut for fixed partition size.

Question

Let $G$ be a graph with vertex set $V$ and $n$ a fixed integer. I want to find a set $S\subseteq V$ with $|S|=n$ that minimizes the 'surface area' of $S$, surface area being the number of edges between a vertex in $S$ and a vertex in $V-S$. I would like to know if this problem has a name, if it has been studied before, and if so, where I can find out more about it. This problem is a variation on the min cut problem however the wikipeida page doesn't mention this particular variation that requires a fixed size for the partition.

Answer 1

could you explain how one would express this as a mixed integer optimization problem?

Let $x_i \in \{0,1\}$ be the decision variable that indicates if vertex $i$ is in $S$, and $y_e \in \{0,1\}$ be the decision variable that indicates if edge $e$ connects a vertex in $S$ with a vertex in $V\setminus S$.

\begin{align} \min \quad & \sum_{e \in E} y_e \\ \text{s.t.} \quad & y_e \geq x_i-x_j \quad \forall e \in E, \; \forall (i,j)\in e^2 \; (i\neq j)\\ & \sum_{i \in V} x_i=n \\ & x_i \in \{0,1\}, y_e \geq 0 \end{align} Let me explain the second constraint: for edge $\{1,2\}$ it sets $y_{\{1,2\}}$ to the absolute difference between $x_1$ and $x_2$ (via $y_{\{1,2\}} \geq x_1 - x_2$ and $y_{\{1,2\}} \geq x_2 - x_1$).