2024/10/30 by Andrea C. Burgess, Burgess, Andrea, Danny Dyer +9 · 1 citation
Computer Science · #05C57 #05C85 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic, programming, and type systems #Optimization and Search Problems #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2410.22962
openalex publication_date 2024/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Deduction is a recently introduced graph searching process in which searchers clear the vertex set of a graph with one move each, with each searcher's movement determined by which of its neighbors are protected by other searchers. In this paper, we show that the minimum number of searchers required to clear the graph is the same in deduction as in constrained versions of other previously studied graph processes, namely zero forcing and fast-mixed search. We give a structural characterization, new bounds and a spectrum result on the number of searchers required. We consider the complexity of computing this parameter, giving an NP-completeness result for arbitrary graphs, and exhibiting families of graphs for which the parameter can be computed in polynomial time. We also describe properties of the deduction process related to the timing of searcher movement and the success of terminal layouts.