EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Algorithms and complexity for geodetic sets on interval and chordal graphs

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

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →