tree_decomposition_linked (558B)
1 # Linked tree decomposition 2 3 A [tree_decomposition] with the following extra property: for every integer k, for every two bags b and b', either there are k disjoint paths connecting the vertices of b and those of b', or there is a bag b'' on the path connecting b and b' that has cardinality <k 4 5 Discussed in [erde2018unified] Definition 1.1, shown in [robertson1986graph5] to exist up to an exponential blowup in the [treewidth] only (Theorem 1.2 of [erde2018unified]) 6 7 Up: [tree_decomposition] 8 9 Alias: linked tree decomposition, linked tree decompositions