Path Decomposition Width

Problem

Compute the width of a path decomposition: the size of its largest bag minus 1.

bags is a list of vertex lists, and one vertex is added at a time along the path. Return 0 for an empty decomposition.

Hint

The width is what makes treewidth and pathwidth hard problems tractable when small.

case 1

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

expected: 1

case 2

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

expected: 2

case 3

in: [[]]

expected: 0

case 4

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

expected: 1

Starter codePython

def path_decomposition_width(bags):
    # Your code here
    pass

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