An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
This provides a solution for monitoring communication failures in networks modeled as chordal graphs, though it is incremental as it extends prior results to a specific graph class.
The paper tackled the problem of computing minimum monitoring edge-geodetic sets (meg-sets) for network failure monitoring, proving that chordal graphs admit a unique minimal meg-set, which resolves an open question and enables polynomial-time computation.
A monitoring edge-geodetic set (or meg-set for short) of a graph is a set of vertices $M$ such that if any edge is removed, then the distance between some two vertices of $M$ increases. This notion was introduced by Foucaud et al. in 2023 as a way to monitor networks for communication failures. As computing a minimum meg-set is hard in general, recent works aimed to find polynomial-time algorithms to compute minimum meg-sets when the input belongs to a restricted class of graphs. Most of these results are based on the property of some classes of graphs to admit a unique minimal meg-set, which is then easy to compute. In this work, we prove that chordal graphs also admit a unique minimal meg-set, answering a standing open question of Foucaud et al.