Vertex Separation Bound

Problem

Compute the vertex separation of a vertex ordering: the maximum over prefixes of the number of prefix vertices that have a neighbor outside the prefix.

order is a permutation of the n nodes and edges is a list of [u, v] pairs. Return the maximum boundary size.

Hint

Vertex separation and pathwidth are closely related: the minimum over orderings is the pathwidth.

Test cases

case 1

in: [[0,1,2,3],[[0,1],[1,2],[2,3]]]

expected: 1

case 2

in: [[0,1,2,3],[[0,1],[0,2],[0,3]]]

expected: 1

case 3

in: [[1,2,3,0],[[0,1],[0,2],[0,3]]]

expected: 3

case 4

in: [[0,1],[[0,1]]]

expected: 1

Starter codePython

def vertex_separation(order, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor