In the Isometric Path Partition problem, the input is a graph G with n vertices and an integer k, and the objective is to determine whether the vertices of G can be partitioned into k vertex-disjoint shortest paths. We investigate the parameterized complexity of the problem when parameterized by the treewidth (tw) of the input graph, arguably one of the most widely studied parameters. Courcelle’s theorem [Information & Computation, 1990] shows that graph problems that are expressible as MSO formulas of constant size admit FPT algorithms parameterized by the treewidth of the input graph. This encompasses many natural graph problems. However, many metric-based graph problems, where the solution is defined using some metric-based property of the graph (often the distance) are not expressible as MSO formulas of constant size. These types of problems, Isometric Path Partition being one of them, require individual attention and often draw the boundary for the success story of parameterization by treewidth. We show that Isometric Path Partition is W[1]-hard when parameterized by treewidth (in fact, even pathwidth (pw)), answering the question by Dumas et al. [SIDMA, 2024], Fernau et al. [TCS, 2025], and confirming the aforementioned tendency. We complement this hardness result by designing a tailored dynamic programming algorithm running in n^{O(tw)} time. This dynamic programming approach also results in an algorithm running in time diam^{O(tw²)} ⋅ n^{O(1)}, where diam is the diameter of the graph. It is known that Isometric Path Partition remains NP-hard on graphs of diameter 2; hence, the combination of both parameters is necessary to obtain a tractable algorithm. Note that the dependency on treewidth is unusually high, as most problems that are FPT for treewidth admit algorithms running in time 2^{O(tw)}⋅ n^{O(1)} or 2^{O(tw log (tw))}⋅ n^{O(1)}. However, we rule out the possibility of a significantly faster algorithm, showing that Isometric Path Partition does not admit an algorithm running in time diam^{o(pw²/(log³(pw)))} ⋅ n^{O(1)}, assuming the Randomized-ETH.

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.

For an integer k ≥ 1 , the objective of k -Geodesic Center is to find a set C of k isometric paths such that the maximum distance between any vertex v and C is minimised. Introduced by Gromov, δ-hyperbolicity measures how treelike a graph is from a metric point of view. Our main contribution in this paper is to provide an additive O ( δ ) -approximation algorithm for k -Geodesic Center on δ -hyperbolic graphs. On the way, we define a coarse version of the pairing property introduced by Gerstel & Zaks (Networks, 1994) and show it holds for δ -hyperbolic graphs. This result allows to reduce the k -Geodesic Center problem to its rooted counterpart, a main idea behind our algorithm. We also adapt a technique of Dragan & Leitert, (TCS, 2017) to show that for every k ≥ 1 , k - Geodesic Center is NP-hard even on partial grids.

A path cover of a digraph is a collection of paths collectively containing its vertex set. A path cover with minimum cardinality for a directed acyclic graph can be found in polynomial time [Fulkerson, AMS'56; Cáceres et al., SODA'22]. Moreover, Dilworth’s celebrated theorem on chain coverings of partially ordered sets equivalently states that the minimum size of a path cover of a DAG is equal to the maximum size of a set of mutually unreachable vertices. In this paper, we examine how far these classic results can be extended to a dynamic setting. A temporal digraph has an arc set that changes over discrete time-steps; if the underlying digraph is acyclic, then it is a temporal DAG. A temporal path is a directed path in the underlying digraph, such that the time-steps of arcs are strictly increasing along the path. Two temporal paths are temporally disjoint if they do not occupy any vertex at the same time. A temporal path cover is a collection 𝒞 of temporal paths that covers all vertices, and 𝒞 is temporally disjoint if all its temporal paths are pairwise temporally disjoint. We study the computational complexities of the problems of finding a minimum-size temporal (disjoint) path cover (denoted as Temporal Path Cover and Temporally Disjoint Path Cover). On the negative side, we show that both Temporal Path Cover and Temporally Disjoint Path Cover are NP-hard even when the underlying DAG is planar, bipartite, subcubic, and there are only two arc-disjoint time-steps. Moreover, Temporally Disjoint Path Cover remains NP-hard even on temporal oriented trees. We also observe that natural temporal analogues of Dilworth’s theorem on these classes of temporal DAGs do not hold. In contrast, we show that Temporal Path Cover is polynomial-time solvable on temporal oriented trees by a reduction to Clique Cover for (static undirected) weakly chordal graphs (a subclass of perfect graphs for which Clique Cover admits an efficient algorithm). This highlights an interesting algorithmic difference between the two problems. Although it is NP-hard on temporal oriented trees, Temporally Disjoint Path Cover becomes polynomial-time solvable on temporal oriented lines and temporal rooted directed trees. Motivated by the hardness result on trees, we show that, in contrast, Temporal Path Cover admits an XP time algorithm with respect to parameter t_max + tw, where t_max is the maximum time-step and tw is the treewidth of the underlying static undirected graph; moreover, Temporally Disjoint Path Cover admits an FPT algorithm with respect to the same parameterization.

In this paper, we study the computational complexity of s-Club Cluster Vertex Deletion. Given a graph, s-Club Cluster Vertex Deletion (s-CVD) aims to delete the minimum number of vertices from the graph so that each connected component of the resulting graph has a diameter at most s. When s=1, the corresponding problem is popularly known as Cluster Vertex Deletion (CVD). We provide a faster algorithm for s-CVD on interval graphs. For each s≥1, we give an O(n(n+m))-time algorithm for s-CVD on interval graphs with n vertices and m edges. In the case of s=1, our algorithm is a slight improvement over the O(n3)-time algorithm of Cao et al. (2018), and for s≥2, it significantly improves the state-of-the-art running time On4. We also give a polynomial-time algorithm to solve CVD on well-partitioned chordal graphs, a graph class introduced by Ahn et al. (WG 2020) as a tool for narrowing down complexity gaps for problems that are hard on chordal graphs, and easy on split graphs. Our algorithm relies on a characterisation of the optimal solution and on solving polynomially many instances of the Weighted Bipartite Vertex Cover. This generalises a result of Cao et al. (2018) on split graphs. We also show that for any even integer s≥2, s-CVD is NP-hard on well-partitioned chordal graphs.

A perfect matching cut is a perfect matching that is also a cutset, or equivalently, a perfect matching containing an even number of edges on every cycle. The corresponding algorithmic problem, Perfect Matching Cut, is known to be NP-complete in subcubic bipartite graphs [Le & Telle, TCS '22], but its complexity was open in planar graphs and cubic graphs. We settle both questions simultaneously by showing that Perfect Matching Cut is NP-complete in 3-connected cubic bipartite planar graphs or Barnette graphs. Prior to our work, among problems whose input is solely an undirected graph, only Distance-2 4-Coloring was known to be NP-complete in Barnette graphs. Notably, Hamiltonian Cycle would only join this private club if Barnette's conjecture were refuted. Funding This work was supported by the ANR projects TWIN-WIDTH (ANR-21-CE48-0014) and Digraphs (ANR-19-CE48-0013). Acknowledgements We are much indebted to Carl Feghali for introducing us to the topic of (perfect) matching cuts, and for presenting open problems to us that led to the current paper. We also wish to thank him and Kristóf Huszár for helpful discussions at an early stage of the project.

A set $S$ of isometric paths of a graph $G$ is ``$v$-rooted'', where $v$ is a vertex of $G$, if $v$ is one of the endpoints of all the isometric paths in $S$. The isometric path complexity of a graph $G$, denoted by $ipco{G}$, is the minimum integer $k$ such that there exists a vertex $v\in V(G)$ satisfying the following property: the vertices of any single isometric path $P$ of $G$ can be covered by $k$ many $v$-rooted isometric paths. First, we provide an $O(n^2 m)$-time algorithm to compute the isometric path complexity of a graph with $n$ vertices and $m$ edges. Then we show that the isometric path complexity remains bounded for graphs in three seemingly unrelated graph classes, namely, hyperbolic graphs, (theta, prism, pyramid)-free graphs, and outerstring graphs. There is a direct algorithmic consequence of having small isometric path complexity. Specifically, we show that if the isometric path complexity of a graph $G$ is bounded by a constant, then there exists a polynomial-time constant-factor approximation algorithm for ISOMETRIC PATH COVER, whose objective is to cover all vertices of a graph with a minimum number of isometric paths. This applies to all the above graph classes.

A set $S$ of vertices of a graph $G$ is a \emph{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. A \emph{grid embedding} of a graph is a set of points in two dimensions with integer coordinates such that each point in the set represents a vertex of the graph and, for each edge, the points corresponding to its endpoints are at Euclidean distance~$1$. A graph is a \emph{partial grid} if it has a grid embedding. In this paper, we first prove that \textsc{Minimum Geodetic Set} remains NP-hard even for subcubic partial grids of arbitrary girth. This jointly strengthens three existing hardness results: for bipartite graphs (Dourado et al., Discrete. Math, 2010), subcubic graphs (Bueno et al., Inf. Process. Lett., 2018)~\cite{bueno2018}, and planar graphs (Chakraborty et al., CALDAM, 2020). The \emph{area} of an internal face is the number of integer points lying on the boundary or interior of the face. A graph is a \emph{solid grid} if it has a grid embedding such that all interior faces have area exactly four. To complement the above hardness result, we design a linear-time algorithm for \textsc{Minimum Geodetic Set} on solid grids, improving on a $3$-approximation algorithm by Chakraborty et al. (CALDAM, 2020). Our results hold for \textsc{Edge Geodetic Set} as well. A set $S$ of vertices of a graph $G$ is a \emph{geodetic set} if every edge of $G$ lies in a shortest path between some pair of vertices of $S$. The \textsc{Minimum Edge Geodetic Set (MEGS)} problem is to find an edge geodetic set with minimum cardinality of a given graph. As corollaries, we obtain that \textsc{MEGS} remains NP-hard on partial grids and is linear-time solvable on solid grids.

A path is isometric if it is a shortest path between its endpoints. In this article, we consider the graph covering problem Isometric Path Cover, where we want to cover all the vertices of the graph using a minimum-size set of isometric paths. Although this problem has been considered from a structural point of view (in particular, regarding applications to pursuit-evasion games), it is little studied from the algorithmic perspective. We consider Isometric Path Cover on chordal graphs, and show that the problem is NP-hard for this class. On the positive side, for chordal graphs, we design a 4-approximation algorithm and an FPT algorithm for the parameter solution size. The approximation algorithm is based on a reduction to the classic path covering problem on a suitable directed acyclic graph obtained from a breadth first search traversal of the graph. The approximation ratio of our algorithm is 3 for interval graphs and 2 for proper interval graphs. Moreover, we extend the analysis of our approximation algorithm to k-chordal graphs (graphs whose induced cycles have length at most k) by showing that it has an approximation ratio of k+7 for such graphs, and to graphs of treelength at most 𝓁, where the approximation ratio is at most 6𝓁+2.

We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC '22] and permutation graphs [BKTW, JACM '22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated. In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA '21]. We show that K_{t,t}-free segment graphs, and axis-parallel H_t-free unit segment graphs have bounded twin-width, where H_t is the half-graph or ladder of height t. In contrast, axis-parallel H₄-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated. More broadly, we explore which structures (large bicliques, half-graphs, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for first-order model checking on graphs given with O(1)-sequences [BKTW, JACM '22], give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If p is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C, then p(G) ⩾ k can be decided in FPT time f(k) ⋅ |V(G)|^O(1). For instance, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width.

A set $S$ of vertices of a graph $G$ is a \emph{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. A \emph{grid embedding} of a graph is a set of points in two dimensions with integer coordinates such that each point in the set represents a vertex of the graph and, for each edge, the points corresponding to its endpoints are at Euclidean distance~$1$. A graph is a \emph{partial grid} if it has a grid embedding. In this paper, we first prove that \textsc{Minimum Geodetic Set} remains NP-hard even for subcubic partial grids of arbitrary girth. This jointly strengthens three existing hardness results: for bipartite graphs (Dourado et al., Discrete. Math, 2010), subcubic graphs (Bueno et al., Inf. Process. Lett., 2018)~\cite{bueno2018}, and planar graphs (Chakraborty et al., CALDAM, 2020). The \emph{area} of an internal face is the number of integer points lying on the boundary or interior of the face. A graph is a \emph{solid grid} if it has a grid embedding such that all interior faces have area exactly four. To complement the above hardness result, we design a linear-time algorithm for \textsc{Minimum Geodetic Set} on solid grids, improving on a $3$-approximation algorithm by Chakraborty et al. (CALDAM, 2020). Our results hold for \textsc{Edge Geodetic Set} as well. A set $S$ of vertices of a graph $G$ is a \emph{geodetic set} if every edge of $G$ lies in a shortest path between some pair of vertices of $S$. The \textsc{Minimum Edge Geodetic Set (MEGS)} problem is to find an edge geodetic set with minimum cardinality of a given graph. As corollaries, we obtain that \textsc{MEGS} remains NP-hard on partial grids and is linear-time solvable on solid grids.