Algorithms and complexity for monitoring edge-geodetic sets in graphs
<|reference_start|>Algorithms and complexity for monitoring edge-geodetic sets in graphs: 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 \textsc{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\cdot OPT$ and $\sqrt{n\ln 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.<|reference_end|>
@article{foucaud2024algorithms,
    title={Algorithms and complexity for monitoring edge-geodetic sets in graphs},
    author={Florent Foucaud, Clara Marcille, R. B. Sandeep, Sagnik Sen and S
  Taruni},
    journal={arXiv preprint arXiv:2409.19067},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.19067},
    primaryClass={cs.CC cs.DM cs.DS math.CO}
}