# Is this a known graph theory problem? What algorithms can solve it?

Let $$G = (V,E)$$ be an undirected graph on $$n$$ vertices. Pick an ordering of the vertices, $$\mathcal{O} = ( v_{i_1},v_{i_2},v_{i_3},\dots )$$. Now from that ordering, create a sequence of subgraphs $$(H_{k})_{k=1}^n$$ where the subgraph $$H_k$$ is the induced subgraph from the first $$k$$ vertices in $$\mathcal{O}$$. For any subgraph $$H_k$$, define the "frontier" to be the number of vertices in $$G \setminus H_k$$ such that are adjacent to a vertex in $$H_k$$.

The problem: Which ordering $$\mathcal{O}$$ of vertices minimizes the maximum frontier over all subgraphs in the induced sequence of subgraphs?

• What is the application? Also, do you have a sample graph in mind? Mar 25 '21 at 19:55
• One usually defines the frontier as the set of edges between $H$ and $G \setminus H$, which could help because it is symmetric. But unlike what I was suggesting in (now deleted) comments, I'm not sure the problem is tractable even with this update. Mar 25 '21 at 22:58
• For simplicity, you don't need to define the induced subgraph $H_k$ and so on. you just look at the size of the neighborhood of $\{v_{i_1},v_{i_2},\ldots,v_{i_k}\}$. Mar 25 '21 at 23:10