Twin-Treewidth: A Single-Exponential Logic-Based Approach

An equivalence class in a set is a subset of elements considered equivalent according to some criterion. This concept is applied to different graph parameters, such as neighborhood diversity, twin-cover, twin-width, and modular width. In this work, we introduce a new parameter in graphs called twin-treewidth, which explores the equivalence classes of twins. This parameter generalizes treewidth and neighborhood diversity, two of the most studied parameters in parameterized complexity. We demonstrate the usefulness of this parameter by proposing a simple exponential-time generic procedure to solve problems that can be expressed in a fragment of a variant of Second-Order Monadic Logic.