Hunting a rabbit: complexity, approximability and some characterizations

DOI10.1016/J.TCS.2026.115946MaRDI QIDQ7240322zbMATH OpenFDO

Authors Walid Ben-Ameur, Harmender Gahlawat, Alessandro Maddaloni

Publication date 11 May 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115946

zbMATH Keywords

complexityhunters and rabbitinapproximability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A cops and robber game and the meeting time of synchronous directed walks
• An evasion game on a graph
• Complexity results for a cops and robber game on directed graphs
• Cops and robbers is EXPTIME-complete
• DAG-width
• DAG-width and circumference of digraphs
• Directed path-width and monotonicity in digraph searching
• Directed tree-width
• Finding a princess in a palace: a pursuit-evasion problem
• Finding good approximate vertex and edge partitions is NP-hard
• Further results on the hunters and rabbit game through monotonicity
• Graph searching and a min-max theorem for tree-width
• How to hunt an invisible rabbit on a graph
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Hunting rabbits on the hypercube
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Searching for an intruder on graphs and their subdivisions
• The no-meet matroid
• Vertex Bisection is Hard, too
• Vertex-to-vertex pursuit in a graph

This page was built for publication: Hunting a rabbit: complexity, approximability and some characterizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7240322)