twin_width (719B)
1 # Twin width 2 3 [twin_width_definition] 4 5 Recent generalization (2023-02): [flip_width] 6 7 - for [model_counting]: [ganian2022weighted] 8 9 - for [enumeration]: [gajarsky2022twin] 10 11 - recognition: 12 - deciding whether the twin-width is at most 4 is [np_hard] 13 - graphs of twin-width 0 or 1 can be identified i [ptime] 14 15 - [Trees] have twin-width at most 2 16 - so twin-width is at most 2 plus the [feedback_edge_number] 17 18 - incomparable with [nowhere_dense] 19 - capture [h_minor_free] and bounded [cliquewidth] 20 21 guarantees that [first_order_model_checking_parameterized_complexity] is [fixed_parameter_tractable] if the merge sequence is provided 22 23 [twin_width_ordered] 24 25 Up: [width_measure] 26 27 See also: [nowhere_dense], [merge_width]