wiki_research

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

twin_width (679B)

      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 - [tree] has 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 [excluded_minor] and bounded [cliquewidth]
     20 
     21 guarantees that [first_order_model_checking] 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]