2023/07/30 by Devin Jean, Jean, Devin, Suk J. Seo +1
Computer Science · #05C69 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2307.16312
openalex publication_date 2023/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An open-locating-dominating set of a graph models a detection system for a facility with a possible "intruder" or a multiprocessor network with a possible malfunctioning processor. A "sensor" or "detector" is assumed to be installed at a subset of vertices where it can detect an intruder or a malfunctioning processor in their neighborhood, but not at itself. We consider a fault-tolerant variant of an open-locating-dominating set called an error-correcting open-locating-dominating set, which can correct a false-positive or a false-negative signal from a detector. In particular, we prove the problem of finding a minimum error-correcting open-locating-dominating set in an arbitrary graph is NP-complete. Additionally, we characterize the existence criteria for an error-correcting open-locating-dominating sets for an arbitrary graph. We also consider extremal graphs that require every vertex to be a detector and minimum error-correcting open-locating-dominating sets in infinite grids.