wiki_research

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

hu2023finding (648B)

      1 # Hu2023finding
      2 
      3 [academic_paper] on [minimal_witness]
      4 
      5 ## Results
      6 
      7 Only on [conjunctive_query_self_join_free]
      8 
      9 - if Q has [head_cluster_property] then [ptime], otherwise [np_complete]
     10 - if Q has [head_domination_property] then constant-factor [approximation], otherwise conditionally no such algorithm
     11 - general [approximation] algorithm; some algorithms for specific query classes
     12 
     13 Relationship to: [directed_steiner_forest] problem
     14 
     15 Future work:
     16 - [approximation]: picture is not complete
     17 - [self_joins]
     18 - the variant of [minimal_witness] where you want to witness only a fraction of the query results
     19 
     20 Up: [academic_paper] on [minimal_witness]