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]