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?

  • 1
    $\begingroup$ What is the application? Also, do you have a sample graph in mind? $\endgroup$
    – RobPratt
    Mar 25 '21 at 19:55
  • $\begingroup$ 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. $\endgroup$
    – Hugo Manet
    Mar 25 '21 at 22:58
  • $\begingroup$ 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}\}$. $\endgroup$ Mar 25 '21 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.