Algorithms and complexity for geodetic sets on interval and chordal graphs
Information and Computation · 2026-06 · 311 · 105456
DOI: 10.1016/j.ic.2026.105456 ↗Kurz gefasst
Fachartikel in der Zeitschrift Information and Computation, 2026-06. Verfasst von Dibyayan Chakraborty und 4 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 31 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ben-Gurion University of the Negev, Agence Nationale de la Recherche, Université Clermont-Auvergne.
Abstract (Originalsprache)
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.
Förderung
- Ben-Gurion University of the Negev
- Agence Nationale de la Recherche
- Université Clermont-Auvergne
- CEFIPRA
- European Research Council
Zitieren
APA
Chakraborty, D., Das, S., Foucaud, F., Gahlawat, H., & Lajou, D. (2026). Algorithms and complexity for geodetic sets on interval and chordal graphs. Information and Computation, 311, 105456. https://doi.org/10.1016/j.ic.2026.105456
Vancouver
Chakraborty D, Das S, Foucaud F, Gahlawat H, Lajou D. Algorithms and complexity for geodetic sets on interval and chordal graphs. Information and Computation. 2026;311:105456. doi:10.1016/j.ic.2026.105456
BibTeX
@article{Chakraborty2026,
author = {Chakraborty, Dibyayan and Das, Sandip and Foucaud, Florent and Gahlawat, Harmender and Lajou, Dimitri},
title = {Algorithms and complexity for geodetic sets on interval and chordal graphs},
journal = {Information and Computation},
year = {2026},
volume = {311},
pages = {105456},
doi = {10.1016/j.ic.2026.105456}
}
EUVIMED