Algorithms and complexity for geodetic sets on interval and chordal graphs
Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou · 2026
Read Algorithms and complexity for geodetic sets on interval and chordal graphs by Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30882.txt.
Introduction
Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat and Dimitri Lajou settle how hard it is to cover a graph with shortest paths. A geodetic set is a set of vertices such that every vertex lies on some shortest path between two of them. The geodetic number is the size of the smallest such set. The team study the Minimum Geodetic Set problem on two structured graph classes, chordal graphs and interval graphs, where the answers turn out to differ sharply.
For chordal graphs, the problem is fixed-parameter tractable when parameterised by tree-width, which for these graphs equals the clique number. That yields a polynomial-time algorithm on k-trees for any fixed k. For interval graphs, they prove the problem NP-hard, answering a question open since 2012, when the problem was shown polynomial on the narrower class of proper interval graphs.
Catalog record
| CREATOR | Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 138 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30882
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Algorithms and complexity for geodetic sets on interval and chordal graphs Thanks: This research was supported by the IFCAM project “Applications of graph homomorphisms” (MA/IFCAM/18/39), the ERC grant titled PARAPATH, the IDEX-ISITE initiative CAP 20-25 (ANR-16-IDEX-0001), the International Research Center “Innovation Transportation and Production Systems” of the I-SITE CAP 20-25, and the ANR project GRALMECO (ANR-21-CE48-0004). This work was partially carried out while Harmender Gahlawat was employed at G-SCOP, Grenoble-INP and Université Clermont Auvergne and Ben-Gurion University of the Negev. This paper contains the full versions of parts of an extended abstract from the proceedings of ISAAC 2020 [ 7 ] . The other results of [ 7 ] were published in a journal [ 10 ] , but are completely disjoint from the results in the present paper. Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou Abstract We study the computational complexity of finding the geodetic number of a graph on chordal graphs and interval graphs. A set S S of vertices of a graph G G is a geodetic set if every vertex of G G lies in a shortest path between some pair of vertices of S S . The Minimum Geodetic Set (MGS) problem is to find a geodetic set with minimum cardinality of a given graph. We show that Minimum Geodetic Set is fixed parameter tractable for chordal graphs when parameterized by its tree-width (which equals its clique number). This implies a polynomial-time algorithm for k k -trees, for fixed k k . Then, we show that Minimum Geodetic Set is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012), who showed that 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. 1 Introduction A simple undirected graph G has vertex set V(G) and edge set E(G) . For two vertices u,v\in V(G) , let I(u,v) denote the set of all vertices in G that lie in some shortest path between u and v . For a subset S of vertices of a graph G , let I(S)=\bigcup_{u,v\in S}I(u,v) . We say that T\subseteq V(G) is covered by S if T\subseteq I(S) . A set of vertices S is a geodetic set if V(G) is covered by S . The geodetic number is the minimum integer k such that G has a geodetic set of cardinality k . Given a graph G , the Minimum Geodetic Set (MGS) problem, introduced in [ 21 ] , is to compute a geodetic set of G with minimum cardinality. In this paper, we study the computational complexity of Minimum Geodetic Set on interval and chordal graphs. Minimum Geodetic Set is a natural graph covering problem that falls in the class of problems dealing with the important geometric notion of convexity : see [ 3 , 16 , 29 ] for some general discussion on graph convexities. The setting of Minimum Geodetic Set is quite natural, and it can be applied to facility location problems such as the optimal determination of bus routes in a public transport network [ 8 , 31 ] . See also [ 15 ] for further applications. The aim of this paper is to study Minimum Geodetic Set on chordal graphs. Chordal graphs are the graphs with no induced cycle of order greater than 3 ; equivalently, they are the intersection graphs of subtrees of trees. Their structural properties imply an interesting behaviour for various types of convexity, as pointed out in [ 14 , 16 ] . The algorithmic complexity of Minimum Geodetic Set has been studied actively. Minimum Geodetic Set is known to be NP-hard on chordal graphs [ 14 ] , chordal bipartite graphs [ 13 , 12 ] , subcubic graphs [ 6 ] , planar graphs [ 8 ] , partial grids [ 7 , 10 ] , co-bipartite graphs [ 15 ] , line graphs [ 7 ] , and graphs of diameter 2 [ 7 ] . On the positive side, polynomial-time algorithms to solve Minimum Geodetic Set are known for cographs [ 12 ] , split graphs [ 12 , 14 ] and its superclass well-partitioned chordal graphs [ 1 ] , ptolemaic graphs [ 16 ] and more generally distance-hereditary graphs [ 24 ] , block-cactus graphs [ 15 ] , outerplanar graphs [ 28 ] , solid grid graphs [ 7 , 10 ] , and proper interval graphs [ 15 ] . From the perspective of parameterized complexity, Minimum Geodetic Set is unlikely to be FPT (it is W[1]-hard) for the parameters solution size, feedback vertex set number, and pathwidth, combined [ 25 ] . In fact it is even NP-hard for graphs that have pathwidth 17 and feedback vertex set number 13 [ 30 ] . The problem is FPT for each of the parameters tree-depth, modular-width and feedback edge set number [ 25 ] , and also for treewidth and diameter, combined [ 19 ] . The approximability of Minimum Geodetic Set has also been studied in [ 8 , 11 ] , and fine-grained complexity aspects with respect to solution size and structural parameters have been studied in [ 19 , 18 ] . Our results. To complement the hardness of Minimum Geodetic Set on chordal graphs, in this paper, we design an FPT algorithm for Minimum Geodetic Set on chordal graphs when parameterized by its treewidth, which equals its clique number \omega minus one. We use dynamic programming on tree-decompositions to prove the following. Theorem 1 . Minimum Geodetic Set can be solved in time 2^{2^{O(w)}}n for chordal graphs and in time 2^{O(w)}n for interval graphs, where n is the order and w the treewidth of the input graph. This result applies to the following setting. A k -tree is a graph formed by starting with a complete graph on (k+1) vertices and then repeatedly adding vertices by making each added vertex adjacent to exactly k neighbours forming a (k+1) -clique. Allgeier [ 2 ] gave a polynomial-time algorithm to solve Minimum Geodetic Set on maximal outerplanar graphs, which is a subclass of 2 -trees, and thus our algorithm generalizes this result (note that 2 -trees are both chordal and planar), as it shows that Minimum Geodetic Set can be solved in time 2^{2^{O(k)}}n for k -trees of order n . Recall that this is unlikely to hold for partial k -trees (which are exactly the graphs of treewidth at most k ) since Minimum Geodetic Set is NP-hard for graphs of treewidth 14 [ 30 ] . Recently, it has been proved that Minimum Geodetic Set does not admit a 2^{2^{o(w)}}\cdot n^{O(1)} algorithm (where w is the treewidth) even on bounded diameter graphs [ 19 ] . In this paper, we further strengthen the existing NP-hardness result of Minimum Geodetic Set on chordal graphs by proving it to be NP-hard on interval graphs. An interval representation of a graph G is a collection of intervals on the real line such that two intervals intersect if and only if the corresponding vertices are adjacent in G