wiki_research

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

benameur2024cops (610B)


      1 # Benameur2024cops
      2 
      3 they study [hunters_and_rabbit_directed]
      4 
      5 - they show that the cop number is at most the [directed_pathwidth] + 1, but can be arbitrarily smaller
      6 - it is the [directed_pathwidth] or the [directed_pathwidth] + 1 in the [monotone_strategy] case
      7 
      8 - lower bound: minimum [outdegree] of an [induced_subgraph], which can be computed in [ptime]
      9   - just do [binary_search] on the value, then iteratively remove vertices with too small outdegree, and check if the remaining graph is empty or not
     10 - upper bound: minimum [feedback_vertex_set]
     11 
     12 also [benameur2024complexity]
     13 
     14 Up: [hunters_and_rabbit]