Is this graph grouping problem $\mathsf{NP}$-hard?

Question

Let's introduce the notion of layer: given a simple graph $G$ a layer is a subgraph of $G$ satisfying the following property:

• If any pair of vertices is connected with an edge, these two vertices either belong to the same or adjacent layers.

Now, the problem is to group vertices into layers in such a way that minimizes the function $\max\limits_i(L_i\cup L_{i+1})$.

For example, consider this graph:

graph

It has 3 layers: $L_1$ (red, top), $L_2$ (green, middle) and $L_3$ (blue, bottom). Since graph diameter is 2, there can't be more layers. Therefore this grouping is optimal. Since all layers contain 3 vertices each, both $L_1\cup L_2$ and $L_2\cup L_3$ have 6 vertices each. Therefore the minimal value of $\max(L_i\cup L_{i+1})$ is 6ドル$.

Is this problem $\mathsf{NP}$-hard? I know its decision version is in $\mathsf{NP}$.

To add some context to this. The problem comes as a divide and conquer subroutine for the clique problem.

• codeR: In this graph, take the rightmost blue vertes into a singleton layer. The next layer consists of the two neighbours of this blue vertex, and rest are in layer three. Layers 1 and 2 contain a total of 3 vertices only. Am I missing something?
• rus9384: @codeR That would make the remaining couple (red and green) of layers contain 8 vertices, which is more than 6. The idea is to sort of balance the graph.
• codeR: Then kindly update your question and state the exact problem clearly.
• codeR: Probably your objective function is: $minimize: \max\limits_i |L_i \cup L_{i+1}|$
• D.W.: What does "the largest couple of adjacent layers" mean? Can you formulate the problem using mathematics?

Answer 1

Your problem is closely related to the problem of computing the bandwidth.

Given a graph $G = (V, E)$, the bandwith of the graph $\mathrm{bw}(G)$ is defined as $\min_f \max_{(u, v) \in E} |f(u) - f(v)|$ where $f : V \rightarrow \{1,\dots,n\}$ is a bijection, representing the oredering of the vertices.

We have: $$ \mathrm{bw}(G) + 1 \leq \min_L \max_i |L_i \cup L_{i+1}| \leq 2 \cdot \mathrm{bw}(G) $$

First inequality: Given a list of layers, order the vertices in the order of layers, where the vertices can be ordered arbitrarily within a layer. Then, the edge length of two vertices $u, v \in L_i$ is at most $|L_i| - 1$, and the edge length of $u \in L_i, v \in L_{i+1}$ is at most $|L_i \cup L_{i+1}| - 1$.

Second inequality: Given a bijection $f : V \rightarrow \{1,\dots,n\}$ and its bandwidth $\mathrm{bw} := \max_{(u,v) \in E} |f(u) - f(v)|$, consider the following procedure:

1. Initialize $L_1 := \{ f^{-1}(1) \}$ and $i := 1$.
2. While $\bigcup_i L_{i} \neq V$, do:
   1. Let start := $\max \{ f(u) \mid u \in L_i \} + 1$.
   2. Let end := $\max \{ f(v) \mid u \in L_i, (u, v) \in E, f(u) \lt f(v) \}$.
   3. Let $L_{i+1} := \{ u \mid u \in V, \mathrm{start} \leq f(u) \leq \mathrm{end} \}$.
   4. Set $i \leftarrow i + 1$ and continue.

In step 2.2, we have $\mathrm{end} - \mathrm{start} \leq \mathrm{bw}$ and thus $|L_i| \leq \mathrm{bw}$. Therefore $\max_i |L_i \cup L_{i+1}| \leq 2 \max_i |L_i| \leq 2 \mathrm{bw}$.

Corollary: Because bandwidth is hard to approximate within any constant, finding the optimal grouping is NP-hard as well, even approximately.