[Python] How can I compute a vertex permutation with a “prefix-neighbors” property in...

I have an undirected graph and I need to reorder its vertices into a permutation that satisfies the following “prefix-neighbors” property:

Property: For every vertex (with ) in the permutation, if there exists any vertex (with ) that is adjacent to (i.e. ), then every vertex with must also be adjacent to .
​

In other words, if has any neighbors among the vertices that come before it in the ordering, then those neighbors must form a contiguous block starting from the very first vertex in the ordering.

For example, consider a graph with vertices and edges:

One valid ordering is :

Vertex 1: Placed first, so no condition applies.

Vertex 2: Placed second; if it has any neighbor among vertices before it, then the very first vertex must be adjacent—but here it happens that 2 is not adjacent to 1, so the condition is not triggered.

Vertex 0: Placed third; its neighbors among are 1 and 2. The earliest (lowest-index) neighbor is 1, which is at the beginning of the ordering.

Vertex 3: Placed last; its neighbors among are 1 and 2 (its first neighbor is 1 at index 0), so the condition is satisfied.

My questions are:

1. 
   Algorithm & Complexity: Is it possible to compute such a permutation in time?
   
   
2. 
   Approach: What algorithm would you recommend for this problem? (For example, should I try a greedy approach, use properties of chordal graphs or perfect elimination orderings, or perhaps use a backtracking search with an MRV (Minimum Remaining Values) heuristic?)
   
   
3. 
   Uniqueness: Under what conditions is such an ordering unique, and how can I detect if multiple valid orders exist or if no valid ordering exists?
   

Any algorithm sketches, insights, or sample code in Python or C++ would be greatly appreciated!

Continue reading...