{"id":"arxiv/2607.07107","url":"https://arxiv.org/abs/2607.07107","tags":["math.CO","cs.DS"],"score":0,"title":"Geodetic sets for directed acyclic planar geodetic graphs","domain":"math.CO","source":"arxiv","authors":["Benedikt G. Hein","Egon Wanke"],"reviews":0,"subject":"math.CO","summary":"A set of vertices $S$ of a directed graph $G$ is geodetic if every vertex of $G$ lies on a shortest path from a vertex of $S$ to a vertex of $S$. A directed graph is geodetic if there is at most one shortest path from every vertex of $G$ to every vertex of $G$. We prove the NP-completeness of the following decision problem. Given a directed acyclic planar geodetic graph $G$ and an integer $k$, does $G$ have a geodetic set with at most $k$ vertices? This implies that the question of whether $G$ has a strong or a monitoring geodetic set with at most $k$ vertices is also NP-complete for…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-08","reactions":{}}