{"ID":5439500,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-02T20:10:16.354447893Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.30882","arxiv_id":"2606.30882","title":"Algorithms and complexity for geodetic sets on interval and chordal graphs","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.","short_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 t...","url_abs":"https://arxiv.org/abs/2606.30882","url_pdf":"https://arxiv.org/pdf/2606.30882v1","authors":"[\"Dibyayan Chakraborty\",\"Sandip Das\",\"Florent Foucaud\",\"Harmender Gahlawat\",\"Dimitri Lajou\"]","published":"2026-06-29T20:16:45Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}