Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees (Q1578418): Difference between revisions

A new characterization of width-\(k\) tree-decompositions of partial \(k\)-trees is established. This leads to a novel \(O(n^{k+2})\) time algorithm for determining whether a \(k\)-connected partial \(k\)-tree is a subgraph of another partial \(k\)-tree, improving on the best previous time of \(O(n^{k+ 4.5})\).