Fast–mixed searching and related problems on graphs

In this paper, we introduce the fast–mixed search model, which is a combination of the fast search model and the mixed search model. Given a graph G in which a fugitive hides on vertices or along edges, the fast–mixed search problem is to find the minimum number of searchers to capture the fugitive in the fast–mixed search model. We establish a relation between the fast–mixed search problem and the induced-path cover problem. We also consider relations between the fast–mixed search problem and other graph search problems. We prove that Fast–Mixed Searching From Leaves is NP-complete, and it remains NP-complete for planar graphs with maximum degree 3. We also prove that Fast–Mixed Searching Between Leaves is NP-complete, and it remains NP-complete for graphs with maximum degree 4. We present linear-time algorithms for computing the fast–mixed search number and optimal search strategies of some classes of graphs, including trees, cacti, and proper interval graphs.