So I asked something related to this a bit, but I don't think this is a duplicate in that I am providing a different version of the problem that is more generic and more easily accessible without knowing coding theory, etc.
Anyway, consider a connected graph $V = (G, E)$. For any $U \subseteq V$ the boundary of $U$ consists of edges $(u, v)$ such that $u \in U$ and $v \in V\setminus U$ or vice versa $v \in U$ and $u \in V\setminus U$ (that is, one end is in $U$ and the other isn't). Let $c(U)$ be the number of edges/size of the boundary of $U$.
Of course when $U$ is trivial, i.e, $U = \emptyset$ or $U = V$, then $c(U) = 0$. We discard these.
We want a polynomial (in $|V|$) time algorithm that finds a nontrivial set $U \subseteq V$ minimizing $c(U)$.
I was thinking of starting with the vertex of least degree $v$ and defining $U = V \setminus \{v\}$. Then we remove from the set $bdry(U) \cap nbrs(v)$ only if doing so decreases the size of the boundary. This only happens when $w\in bdry(U) \cap nbrs(v)$ is such that $nbrs(w) \cap U = \emptyset$ (that is $w$ is disconnected to the rest of $U$). This ensures that removing $w$ doesn't add new neighbors.
I'm not sure this is minimal though, and I don't know if I would call it polynomial (mostly I'm unsure how long checking degrees and neighbors takes)