wiki_research

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

treewidth_computation (552B)

      1 # Treewidth computation
      2 
      3 The [computational_problem] of computing the [treewidth]
      4 
      5 [flum2002query]
      6 - it can be [FPT_linear] (exp in k)
      7 - it can be in [XP], in n^{k+2}
      8 
      9 [Treewidth] is [NP_hard] to compute when k is given as input
     10 - already on [cubic_graphs], cf [bodlaender2023treewidth]
     11 
     12 [Approximation]: see [treewidth_approximation]
     13 
     14 Open whether it is tractable to compute on [planar_graphs]
     15 
     16 Up: [treewidth], [computational_problem]
     17 
     18 See also: [tree_decomposition_computation], [hypertreewidth_computation], [generalized_hypetreewidth_computation]