2022/08/11 by Devin Jean, Jean, Devin, Suk Min Seo +1 · 1 citation
Computer Science · #05C69 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Distributed systems and fault tolerance #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2208.06052
openalex publication_date 2022/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Assume that a graph G models a detection system for a facility with a possible ``intruder," or a multiprocessor network with a possible malfunctioning processor. We consider the problem of placing detectors at a subset of vertices in G to determine the location of an intruder if there is any. Many types of detection systems have been defined for different sensor capabilities; in particular, we focus on Identifying Codes, where each detector can determine whether there is an intruder within its closed neighborhood. In this research we explore a fault-tolerant variant of identifying codes applicable to real-world systems. Specifically, error-detecting identifying codes permit a false negative transmission from any single detector. We investigate minimum-sized error-detecting identifying codes in several classes of graphs, including cubic graphs and infinite grids, and show that the problem of determining said minimum size in arbitrary graphs is NP-complete.