# Algorithms and complexity for geodetic sets on interval and chordal graphs

Preprint · Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou

- Archive id: arxiv:2606.30882
- Published: 2026-06-29
- Venue: Information and Computation 311:105456, 2026
- DOI: https://doi.org/10.1016/j.ic.2026.105456
- arXiv: https://arxiv.org/abs/2606.30882
- Source URL: https://arxiv.org/abs/2606.30882
- PDF: https://arxiv.org/pdf/2606.30882
- Provenance: arxiv

## Abstract

We study the computational complexity of finding the geodetic number of a graph on chordal graphs and interval graphs. A set $S$ of vertices of a graph $G$ is a \\textit{geodetic set} if every vertex of $G$ lies in a shortest path between some pair of vertices of $S$. The \\textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality of a given graph. We show that \\textsc{Minimum Geodetic Set} is fixed parameter tractable for chordal graphs when parameterized by its \\emph{tree-width} (which equals its clique number). This implies a polynomial-time algorithm for $k$-trees, for fixed $k$. Then, we show that \\textsc{Minimum Geodetic Set} is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012), who showed that \\textsc{Minimum Geodetic Set} is polynomial-time solvable on proper interval graphs. As interval graphs are very constrained, to prove the latter result, we design a rather sophisticated reduction technique to work around their inherent linear structure.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.