Given an undirected graph $G$, I want to find a permutation of its vertices that minimizes the sum of all manhattan distances between all locations of 1s inside the upper triangle of its adjacency matrix. Example:
$$ \begin{matrix} & \bf 0&\bf 1&\bf 2&\bf 3&\bf 4&\bf 5\\ \bf 0&&1&0&0&0&0\\ \bf 1&&&1&0&1&0\\ \bf 2&&&&1&0&0\\ \bf 3&&&&&1&1\\ \bf 4&&&&&&0\\ \bf 5 \end{matrix} \quad\rightarrow\quad \begin{matrix} & \bf 0&\bf 1&\bf 2&\bf 3&\bf 4&\bf 5\\ \bf 0&&0&0&1&1&1\\ \bf 1&&&1&1&1&0\\ \bf 2&&&&0&0&0\\ \bf 3&&&&&0&0\\ \bf 4&&&&&&0\\ \bf 5 \end{matrix} $$
The "manhattan number", $\text{manhattan}(G)$, over the graph on the left would be:
manhattan((0, 1), (1, 2)) = 2
+ manhattan((0, 1), (2, 3)) = 4 + manhattan((1, 2), (2, 3)) = 2
+ manhattan((0, 1), (1, 4)) = 4 + manhattan((1, 2), (1, 4)) = 2
+ manhattan((0, 1), (3, 4)) = 6 + manhattan((1, 2), (3, 4)) = 4
+ manhattan((0, 1), (3, 5)) = 7 + manhattan((1, 2), (3, 5)) = 5
+ manhattan((2, 3), (1, 4)) = 2 + manhattan((1, 4), (3, 4)) = 2
+ manhattan((2, 3), (3, 4)) = 2 + manhattan((1, 4), (3, 5)) = 3
+ manhattan((2, 3), (3, 5)) = 3 + manhattan((3, 4), (3, 5)) = 1
= 49
However, the manhattan number over the graph on the right, which is isomorphic to the left one, is $28$, the minimum possible value between all "isomorphic adjacency matrices" of that graph. Let's call $G_{(u, v)}$ the graph formed by relabelling $u$ and $v$ to each other in $G$, and consider the following algorithm: $$ \begin{align} &{\bf\text{repeat}}&&G\leftarrow G_{(u, v)}\\ &{\bf\text{while}}&&\text{manhattan}(G_{(u, v)}) < \text{manhattan}(G)\\ &{\bf\text{where}}&&(u, v) \leftarrow \min_{(u, v)\in V^2} \text{manhattan}(G_{(u, v)}) \end{align} $$
In other words, choose, per-iteration, the 2-vertex relabelling that minimizes $\text{manhattan}(G)$, apply the relabelling, and repeat until no further improvement is found. This algorithm finds the relabelling $(0\ 3)$ first, lowering $49$ to $31$, and then $(3\ 2)$, lowering $31$ to $28$, the minimum value.
As greedy as it is, is it possible that this algorithm could stop in local minimums, or does it always find optimal solutions? In case it doesn't, is there any polynomial time algorithm that does it?