Linear-time algorithms for partial \(k\)-tree complements (Q1578411)

It is well known that many problems that are NP-hard for general graphs become linear time solvable when restricted to graphs of bounded treewidth, or, equivalently, partial \(k\)-trees. This is for instance true for all problems that can be expressed in monadic second-order logic, or extensions, like counting MSOL, where quantification can be done over (sets of) vertices and edges. In this paper, the variant where quantification over sets of non-edges can be done is considered. The paper explores relations with complements of partial \(k\)-trees. It analyses some concrete problems, including \(\chi_t\)-coloring, \(f\)-factoring, and Hamiltonian circuit, for partial \(k\)-trees or their complements.