# Finding Smallest Frontier for Graphs of bounded “width”

Let $$G$$ be a graph and $$X=x_1,x_2,…,x_n$$ be an permutation/ordering of the vertex set of $$G$$. We then let $$S_i = \{x_j:j\le i\}$$, and $$F_i$$ be the number vertices $$v\in S_i$$ that are adjacent to some vertex $$u(v) \not\in S_i$$. We finally define $$F$$ to be a list of values $$F_i$$ sorted from largest to smallest. e.g. if $$F_1=2,F_2=1,F_3=6, F_4=2$$ we’d have $$F = 6,2,2,1$$ (we caution that in reality $$F_{i+1}-F_i\le 1$$ so the sequence features in the example could not occur)

In general, finding $$X$$ such that $$F$$ is lexicographically minimal is a task which I’d assume is NP-Hard.

However, letting $$\mathcal{G}_{k,t}$$ denote the family of graphs $$G$$ such that the vertex set of $$G$$ is partitioned in to $$t$$ parts $$V_1,\dots,V_t$$ such that $$V_i \le k$$ for all $$i$$, and $$|a-b|\ge 2$$ implies there is no edge $$(u,v)$$ in $$G$$ where $$u\in V_a$$ and $$v\in V_b$$.

For fixed $$k$$, and given $$G\in \ mathcal{G}_{k,t}$$, is there an algorithm that finds $$X$$ such that $$F$$ is lexicographically minimal, whose worst case run time is polynomial in $$t$$?