2024/09/27 by Foucaud, Florent, Marcille, Clara, Sandeep, R. B. +2 · 1 citation
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.19067
A monitoring edge-geodetic set of a graph is a subset M of its vertices such that for every edge e in the graph, deleting e increases the distance between at least one pair of vertices in M. We study the following computational problem MEG-set: given a graph G and an integer k, decide whether G has a monitoring edge geodetic set of size at most k. We prove that the problem is NP-hard even for 2-apex 3-degenerate graphs, improving a result by Haslegrave (Discrete Applied Mathematics 2023). Additionally, we prove that the problem cannot be solved in subexponential-time, assuming the Exponential-Time Hypothesis, even for 3-degenerate graphs. Further, we prove that the optimization version of the problem is APX-hard, even for 4-degenerate graphs. Complementing these hardness results, we prove that the problem admits a polynomial-time algorithm for interval graphs, a fixed-parameter tractable algorithm for general graphs with clique-width plus diameter as the parameter, and a fixed-parameter tractable algorithm for chordal graphs with treewidth as the parameter. We also provide an approximation algorithm with factor ln m⋅ OPT and √(nln m) for the optimization version of the problem, where m is the number of edges, n the number of vertices, and OPT is the size of a minimum monitoring edge-geodetic set of the input graph.