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$ ?