Numbering the vertices of an $n$-layer graph so that edges have similar numbered vertices on their ends

Question

Consider a graph whose vertices can be partitioned into $n$ layers. Edges exist only between vertices in successive layers. So, there are edges between layers $1$ and $2$, between layers $2$ and $3$ and so on but never between layers $1$ and $3$ (since they are not successive layers) nor between vertices in the same layer.

An example of such a graph with three layers is shown in the figure below.

Now, I want to number the vertices in each layer from $1$ to $m_i$ (with $m_i$ being the number of vertices in layer $i$) in a way that the vertices at the two ends of any edge are as close in number as possible. We can think of an objective function that is the sum of squared differences of the numbers assigned to the vertices connected by each edge, across all edges.

Is there an efficient algorithm that can do this?

---

One idea is to use concepts from drawing force directed graphs, where we consider that each edge has a spring force trying to make it as short as possible with the additional constraint that vertices in each layer be restricted to vertical "pipes". Trying to implement this seems very complicated and not the most efficient method.

It was mentioned in the comments that this problem is related to the bandwidth problem in graph theory: https://en.wikipedia.org/wiki/Graph_bandwidth

Note: this is cross posted from here: https://math.stackexchange.com/questions/4187496/numbering-the-vertices-of-an-n-layer-graph-so-that-edges-have-similar-numbered?noredirect=1#comment8682241_4187496

Answer 1

Maybe this can work?

Numbering is same as sorting. Disregard the layers and treat the whole thing as a single graph. Use Cuthill-Mckee (if the bandwidth is low) or other heuristics for the graph bandwidth problem to find the big ordering of nodes. For each layer, filter out the nodes of other layers in the big ordering to get the ordering of nodes in that layer.

Wikipedia says the graph bandwidth problem is also called linear graph placement. Linear placement means moving all the nodes to a regular grid on a 1D line, and minimize the distances between the connected nodes by sorting the nodes on that 1D line.

Here is what I guess:

layer 2:      1 - 2
             / \ /
layer 1:    1   2

vs
                -
               / \
big layer:  1-2-3-4

The best ordering on one 1D line is same as the best ordering over multiple lines. The relationships between the nodes in the two cases (big layer and multiple layer) are the same. Since sorting only depends on the relationships, the ordering doesn't change.

---

Boost and other libraries have implementation of Cuthill-Mckee:

https://algorist.com/problems/Bandwidth_Reduction.html

---

Here is my proof that only ordering matters in the single layer case.

Define a gap transform $g(\vec{r}, s)$ as increasing all numbering above $s$ by 1.

For example, originally we number the nodes as $\vec{r} = \begin{bmatrix}1 & 2 & 3 \end{bmatrix}$. After the gap transform with $s = 2$, we would number the nodes as $g(\vec{r}, 2) = \begin{bmatrix}1 & 2 & 4 \end{bmatrix}$.

Claim: Gap transform does not change the ordering of nodes in the best numbering of the nodes.

Proof

• Define the numbering of the nodes as $\vec{r}$ and the total edge cost as $f(\vec{r})$.

• Define the best numbering before we insert any gap as $\vec{b}$.

• Group all nodes with numbering above $s$ as set $A$. Group the remaining nodes into a set $B$.

• Clearly, inserting the gap would increase the total cost by $m$, where $m$ is the number of edges between $A$ and $B$ in the numbering $g(\vec{b}, s)$. In other words, $f(\vec{b}) + m = f(g(\vec{b}, s))$.

• Suppose after inserting the gap to the best numbering before gap insertion $\vec{b}$, we can permute the numbering to $\vec{b}^{*}$ and obtain a better total edge cost $f(\vec{b}^{*}) < f(g(\vec{b}, s)) = f(\vec{b}) + m$.

• All permutations are equivalent to three steps: permute numbering in $A$, permute numbering in $B$, exchange nodes between $A$ and $B$.

  • If we permute only the numbering in group $A$, the total cost would stay the same or increase. Otherwise, if the cost decrease, we can simply remove the gap and find a numbering for the no gap case that is better than $\vec{b}$, a contradiction. Same situation for group $B$.
  • Moving nodes from $A$ to $B$ or from $B$ to $A$ is not possible because the number of nodes in $A$ is fixed by $s$.
  • Exchanging $c$ nodes in $A$ with $c$ node in $B$ would decrease neither the total cost of edges in $A$ nor total cost of edges in $B$.
    • This is because 1. $\vec{b}$ is the best numbering for the no gap case. 2. inserting the gap doesn't change the cost of edges in $A$. Therefore, within $A$, the best numbering stay the same upon inserting the gap. Any change of the numbering within $A$ would make the total cost of edges in $A$ increase or stay the same. Same for edges in $B$ because inserting the gap doesn't change the total cost of edges in $B$.
    • Therefore, the total cost of edges between $A$ and $B$ must decrease.
      • There are two possibilities: we decrease the number of edges between $A$ and $B$ or we don't.
        • If we do, the total number of edges must stay the same. When we reduce the number of edges between $A$ and $B$, there is a corresponding increase of number of edges in either $A$, $B$ or both. That means we are shifting some edges from between $A$ and $B$ to within $A$ or within $B$.
        • Each extra edge in $A$ or $B$ has a cost of at least 1.
        • Therefore, the total cost of edges between $A$ and $B$ must improve by more than $n$, which is the number of edges shifted.
        • But then, we can remove the gap and reduce the cost of edges between $A$ and $B$ by $m - n$, where $m$ is again the number of edges between $A$ and $B$ in no gap numbering $\vec{b}$.
        • The total improvement of the cost of edges between $A$ and $B$ exceeds 0 if we compare the new numbering with gap removed and the old best numbering for the no gap case.
        • That means and get a numbering better than $\vec{b}$ for the no gap case, a contradiction.
        • If we don't reduce the number of edges, remove the gap would again lead to a numbering better than $\vec{b}$, a contradiction.

• Therefore, all permutations would not improve the total cost. $g(\vec{s}, b)$ is the best numbering after we insert the gap.

We can repeat gap transforms to get all possible numbering of the nodes with the same ordering.

Consequently, the exact number on the node doesn't matter. Only the ordering in the numbering of the nodes matter.

---

Gap transform over multiple layers

• Define the best numbering of nodes in $L$ layers as $\beta = \lbrace \vec{b}_{1}, \vec{b}_{2}, \ldots \vec{b}_{L} \rbrace$

• Apply gap transform to the $k^{\mathrm{th}}$ layer: $g(\vec{b}_{k}, s)$

• Assume the gap transform preserves the combined ordering of the nodes of all layers. That means the gap transform does not increase the crossing number for the edges between 2 layers.

• For each layer with index $l$, group the nodes with numbering above $s$ as a set $A_{l}$. Group the remaining nodes in the layer as $B_{l}$.

• For the $(k + 1)^{\mathbb{th}}$ layer, there are 3 cases: $A_{k+1}$ is empty, $B_{k+1}$ is empty, or $A_{k+1}$ and $B_{k+1}$ are both not empty.

  • Case 1: Suppose $A_{k+1}$ is empty and $B_{k+1}$ is nonempty.
    • Then the cost of edges between $B_{k}$ and $B_{k+1}$ remain the same. The cost of each edge between $A_{k}$ and $B_{k+1}$ increases by 1.
    • After insertion of the gap, rearranging the numbering of the nodes within $A_{k}$ would not decrease the total cost of edges between the $A_{k}$ and $B_{k+1}$ for the following reasons:
      • The costs of the edges between $A_{k}$ and $B_{k+1}$ are uniformly increased by 1.
      • The best way to connect $A_{k}$ and $B_{k+1}$ remain the same.
      • Permuting the nodes within $A_{k}$ would permute the edges between $A_{k}$ and $B_{k+1}$. That means deviating from the best connectivity. The total costs for these edges would not decrease. Otherwise, we can remove the gap and get a numbering that is better than $\beta$ for the no gap case, which is a contradiction.
    • After insertion of the gap, rearranging the numbering of the nodes within $B_{k}$ would not decrease the total cost of edges between the $B_{k}$ and $B_{k+1}$. The reason is similar because the cost of the edges remain the same, which means these costs are uniformly increased by 0.
    • Moving a node from $A_{k}$ to $B_{k}$ or from $A_{k}$ to $B_{k}$ is impossible because $s$ fixes the number of nodes in $A_{k}$.
    • After exchanging $c$ nodes in $A_{k}$ with $c$ nodes in $B_k$, there are 2 cases: I. The number of "cross" edges between $A_{k}$ to $B_{k+1}$ increases. II. That number doesn't increases.
      • Case 1I. The number of edges between layer $k$ and layer $k + 1$ is constant. Therefore, we are shifting $n$ "cross" edges between $A_{k}$ to $B_{k+1}$ to "non-cross" edges between $A_{k}$ and $A_{k+1}$. This shift would decrease neither the total cost of edges between the two layers nor the total cost of all edges, for reasons similar to the single layer case.
      • Case 1II. This permutation would not decrease the total cost. Otherwise, removing the gap would lead a numbering better than $\beta$ for the no gap case, which is a contradiction.
  • Case 2: Suppose $B_{k+1}$ is empty and $A_{k+1}$ is nonempty.
    • Upon insertion of the gap, the costs of each edge between $A_{k}$ and $B_{k+1}$ increases by 1. The costs of edges within $A_{k}$ remain the same. The cost of edges between $A_{k}$ and $A_{k+1}$ varies.
    • The change of the cost of the inter-layer edges among $A_{k}$, $A_{k+1}$, and $A_{k-1}$ is the difficult part.
    • Suppose after inserting the gap, a rearrangement of the nodes in $A_{k}$ would decrease the total edge cost.
    • Let $w$ be the total number of edge crossovers between the inter-layer edges among sets $A_{k}, A_{k+1}, A_{k-1}$ plus the number of crossovers within $A_{k}$
    • The rearrangement has three cases: A. $w$ stay the same. B. $w$ increases. C. $w$ decreases.
      • Case 2C: decreasing the number of edge crossovers (untangling) would decrease the inter-layer edge costs for both no-gap and with gap cases. Therefore, this is impossible. Otherwise we can untangle and get a numbering better than $\vec{\beta}$ for the no-gap case, a contradiction.
      • Case 2B: Increasing the number of edge crossovers (tangling up) won't help.
        • There is surely one rearrangement that doesn't increase $w$, which is no rearrangement.
      • Case 2A: The number of edge crossovers stays the same.
        • Case 2A0: 2 times the number of inter-layer crossover points minus the number of inter-layer edges is zero. That means each inter-layer edge from $A_k$ crossover another inter-layer edge for exactly once.
          • In this case, the total costs of all "crossed" inter-layer edges don't change upon insertion of the gap.
          • Define the set of nodes in $A_k$ that are involved in crossovers of inter-layer edges as $S$.
          • Notice that within layer $A_k$, the edge costs don't change upon insertion of the gap.
          • The total costs of all inter-layer edges that contain nodes in $S$ also don't change upon insertion of the gap.
          • Therefore, after insertion of the gap, rearrangement of the nodes in $S$ would cause an increase of cost that must be over-compensated by the remaining edges.
            • The source of this over-compensation can't come from the remaining edges within $A_k$ because those edges are messed up too. The connectivity within $A_k$ deviates from the optimal cases in $\beta$ upon the rearrangement of the nodes in $S$.
            • The over-compensation must come from non-crossing inter-layer edges.
              • The over-compensation can't come from nodes that only have non-crossing inter-layer edges. The reason is that the rearrangement of the nodes in $S$ doesn't provide any improvement to these edges.
              • The remaining possibility is to have a compensation from some non-crossing edge that connects a node in $S$ to a node in $B_{k}$ that is out of $S$. Let's say these edges are in a set $H$.
                • The crossing-edges form a crossfire. Each edge in $H$ can't get caught in the crossfire. Then, each edge in $H$ must be at one of the two ends of a crossfire.
                  • Therefore, if there are $\xi$ crossfires, there is at most $2\xi$ edge $E$s.
                  • Moreover, exchanging two nodes in $S$ that are from two different crossfires would spread the crossfire and kill at most two edge in $E$. So, we can't do that.
                  • Exchanging 1 node in the crossfire with another node at the edge of the same crossfire would increase the cost of the edge E.
                • This last possibility won't help too!
          • Therefore, no rearrangement of the nodes in $S$ can improve the overall cost.
          • Consequently, case 2A0 reduces to the case without any crossover of inter-layer edges.
        • Case 2A1: 2 times the number of inter-layer crossover points minus the number of inter-layer edges is 1.
          • Only the 3 edges that form 2 crossover on 1 edge matters. The remaining edges followings case 2A0.
        • In both cases, upon insertion of the gap, the cost of each inter-layer non-crossed edges change by either +1 or -1, which may not cancel out, unlike the crossed edges. I think rearranging the nodes involved in non-crossed edges won't improve the total cost if $w$ remain the same.
          • Rearranging the nodes is a subset of re-connection of the edges among these nodes. However, If the re-connection of edges is legal (corresponds to a rearrangement of nodes), then if the improvement of cost exceed 1, we would have done it for the no-gap case. That is impossible by contradiction.
        • I guess exchanging nodes involved in inter-layer crossed edges and nodes that only have inter-layer un-crossed edges would increase $w$.

might be easier to prove case 1 and 2 first then sequentially moves nodes into the empty set.

---

Suppose the gap transform doesn't change the ordering of nodes in the multi-layer case. I can find the best ordering for the big graph on 1-D line. Then rise some node onto other layers. And finally remove all the gaps in all layers. The numbering would stay optimal.

---

Bibliography

Tangle base: https://onlinelibrary.wiley.com/doi/epdf/10.1002/net.21979

Gotzsch's theorem: every planar graph without triangle can be colored by 3 colors. Link

Answer 2

I don't know whether this will be efficient enough for your real graph sizes, but with binary decision variables $x_{v,k}$ to indicate whether vertex $v$ is assigned label $k$, you can obtain a formulation that looks a lot like the quadratic assignment problem. Let $V_i$ be the set of vertices in layer $i$. The problem is to minimize $$\sum_{(v,w)\in E} \sum_{k_v, k_w} (k_v-k_w)^2 x_{v,k_v} x_{w,k_w}$$ subject to \begin{align} \sum_{k=1}^{m_i} x_{v,k} &=1 &&\text{for layer $i$ and $v\in V_i$}\\ \sum_{v\in V_i} x_{v,k} &=1 &&\text{for layer $i$ and $k\in\{1,\dots,m_i\}$} \end{align}

Answer 3

I hacked a random key genetic algorithm for the problem in Java, and ran it against a linearized version of Rob Pratt's MIP model (using CPLEX 20.1 with default parameter settings) on some small random test problems (five layers, three to nine nodes per layer, about 1/4 of all possible edges present). Because the GA stagnated very quickly, I did multiple restarts (running the GA ten times on the same problem). Using the parameters I set, the GA generally finished its ten runs in under two minutes.

I then fed the best solution from the GA to CPLEX as a starting solution. I don't know whether the GA was getting an optimal solution in general, because I only gave CPLEX five minutes, and it only got the gap down to zero once (and frequently didn't get it below 50%). What I can say is that (a) in the one case where CPLEX got the gap to 0, the GA solution was indeed optimal and (b) CPLEX never improved on the GA solution in any run. None of that is conclusive, and it might or might not hold up with larger graphs (or with CPLEX given more time), but all told I would say it is an encouraging sign that the GA is "good enough".

Answer 4

Treat nodes in 1st and 3nd layer as extra edges in the 2st layer to make a merged layer. Minimize bandwidth of 2nd layer. Repeat for the other layers.

layer 2: o   o   o
          \ / \ /
layer 1:   @   @

@ becomes an edge:

layer 2: o - o - o
```