wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

twin_width (859B)

      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 are precisely the [cographs] and can be recognized in [linear_time]
     14   - graphs of twin-width 1 have been characterized and can be recognized in [linear_time]: [ahn2025twin]
     15 
     16 - [Trees] have twin-width at most 2
     17   - so twin-width is at most 2 plus the [feedback_edge_number]
     18 
     19 - incomparable with [nowhere_dense]
     20 - capture [h_minor_free] and bounded [cliquewidth]
     21 
     22 guarantees that [first_order_model_checking_parameterized_complexity] is [fixed_parameter_tractable] if the merge sequence is provided
     23 
     24 [twin_width_ordered]
     25 
     26 Up: [width_measure]
     27 
     28 See also: [nowhere_dense], [merge_width]