Geodetic sets for directed acyclic planar geodetic graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.07107
curl -X POST /api/v1/records/arxiv/2607.07107/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.07107/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'