# Complexity and algorithms for Isometric Path Cover on chordal graphs and beyond

Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, Subir Kumar Ghosh

► To cite this version:

Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, et al. Complexity and algorithms for Isometric Path Cover on chordal graphs and beyond. 2022. hal-03710812v2

HAL Id: hal-03710812

https://hal.science/hal-03710812v2

Preprint submitted on 27 Oct 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Complexity and algorithms for ISOMETRIC PATH COVER on
chordal graphs and beyond*

Dibyayan Chakraborty† Antoine Dailly‡ Sandip Das§ Florent Foucaud¶||

Harmender Gahlawat** § Subir Kumar Ghosh††

October 27, 2022

Abstract

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 *l*, where the approximation ratio is at most 6*l* + 2.

# 1 Introduction

Problems involving paths in graphs are fundamental in theoretical computer science. A prominent example is PATH COVER, which asks whether the vertex set of an input graph can be covered by at most *k* paths. This problem is NP-hard even for *k* = 1 as, in this case, it is HAMILTON PATH. PATH COVER is extensively studied and has many applications, see [3, 5, 26]. A packing counterpart of PATH COVER is the well-known problem DISJOINT PATHS which asks, given pairs of terminal vertices of a graph *G*, for disjoint paths joining the terminal pairs. DISJOINT PATHS has found many applications, due to its connections to the Graph Minor project [29].

Certain types of paths are of special interest, in particular, shortest paths between vertex pairs are
important in many applications. A path is called *isometric* if it is a shortest path between two vertices.
The corresponding variant of DISJOINT PATHS, called DISJOINT SHORTEST PATHS, has recently gained
some attention [22]. The goal of this paper is to study the “shortest path” variant of PATH COVER, which
was introduced in [13] with inspiration from earlier work on pursuit-evasion games [2].

<footnote>*This research was partially financed by the IFCAM project "Applications of graph homomorphisms" (MA/IFCAM/18/39), the ANR project GRALMECO (ANR-21-CE48-0004) and the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25).</footnote>

<footnote>†Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France</footnote>

<footnote>‡G-SCOP, Univ. Grenoble-Alpes, Grenoble, France</footnote>

<footnote>§Indian Statistical Institute, Kolkata, India</footnote>

<footnote>¶Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France</footnote>

<footnote>|| Univ. Orléans, INSA Centre Val de Loire, LIFO EA 4022, F-45067 Orléans Cedex 2, France</footnote>

<footnote>**Ben-Gurion University of the Negev, Beer-Sheva, Israel</footnote>

<footnote>††Ramakrishna Mission Vivekananda Educational and Research Institute, Kolkata, India</footnote>
An *isometric path cover* of a graph *G* is a set of isometric paths such that each vertex of *G* belongs to at least one of the paths. The *isometric path number* of *G* is the smallest size of an isometric path cover of *G*. The algorithmic problem studied in this paper is as follows.

ISOMETRIC PATH COVER

**Input:** A graph *G*, and a positive integer *k*.

**Question:** Does *G* have an isometric path cover of size at most *k*?

ISOMETRIC PATH COVER was introduced in the context of the well-known *Cops and Robber* game (where multiple cops try to catch a robber, each protagonist being able to move to an adjacent vertex in each round of the game). Indeed, given an isometric path cover, one can assign a cop to “guard” each isometric path: each cop patrols along its path, always staying as close as possible to the robber. This strategy shows that the isometric path number of the graph is an upper bound to the cop number of the graph (the smallest number of cops needed to catch one robber) [2, 13]. More sophisticated techniques, still based on isometric paths, have been developed in this context, for example *cop-decompositions*, which are tree decomposition where the subgraph induced by the vertices of each bag that are not present in the parent’s bag has a small isometric path cover [1]. ISOMETRIC PATH COVER plays a crucial role in the proof of the *Product Structure Theorem* [11] of planar graphs. ISOMETRIC PATH COVER is also studied in the context of machine learning [30].

Surprisingly, the algorithmic complexity of ISOMETRIC PATH COVER has not garnered much attention. Its NP-hardness was recently posed as an open problem in both [23, 24]. The problem is easy to solve on trees [3]. More generally, ISOMETRIC PATH COVER is known to be polynomial-time solvable on block graphs [27]. It can be approximated in polynomial time within a factor of $log(d)$ for graphs of diameter $d$ by a greedy algorithm [30] and solved in polynomial time for every fixed value of $k$ by an XP algorithm [12]. ISOMETRIC PATH COVER has also been studied from a structural point of view: the optimal solution sizes have been determined for square grids [13], hypercubes [14], complete $r$-partite graphs [28] and Cartesian products of complete graphs [28], and it was recently proved that the pathwidth of a graph is always upper-bounded by the size of its smallest isometric path cover [12]. The version where the cover is actually a *partition* was also studied [23]. The variants where the set of endpoints of the paths is prescribed in the input is studied in [8, 12, 21], and when the set of allowed paths is prescribed it is studied on trees in [18].

**Graph classes studied in this paper.** Let us introduce the various graph classes studied in this paper. See Figure 1 for a visualization of the inclusion diagram of the graph classes discussed in this paper (and related ones). A *chordal graph* is a graph without any induced cycle of order at least 4. An *interval representation* of a graph *G* is a set $\mathcal{I} = \{[x_u^-, x_u^+]: u \in V(G)\}$ of intervals where each interval in $\mathcal{I}$ corresponds to a vertex, and two intervals intersect if and only if the corresponding vertices share an edge. A graph is an *interval graph* if it has an interval representation. A graph is a *proper interval graph* if it has an interval representation where no interval contains another interval as a subset. Interval graphs are also chordal graphs. In fact, Fulkerson & Gross [15] proved that interval graphs are exactly the chordal graphs without an *asteroidal triple* (three vertices *a*, *b*, *c* of a graph *G* form an asteroidal triple if for any $\{w_1, w_2, w_3\} = \{a, b, c\}$, there is a path between $w_1, w_2$ that does not contain any vertex from the neighbourhood of $w_3$.)

Even though the classes of *AT*-free graphs (*i.e.*, graphs without an *asteroidal triple*) and chordal graphs are incomparable, both of them have bounded *chordality*. A graph is *k-chordal* if it does not contain an induced cycle of order greater than *k*. Chordal graphs are exactly the class of 3-chordal graphs, and all *AT*-free graphs are 5-chordal. A superclass of *AT*-graphs are graphs that contain a *dominating shortest path* [7]. A graph *G* has a *dominating shortest path* if there exists a shortest path *P* in *G* such that the closed neighbourhood of any vertex of the graph intersects with the vertex set of *P*. Even though graph classes with bounded *chordality* are incomparable with the class of graphs having a dominating shortest path, both of these classes have bounded *treelength*, a parameter introduced by Dourisboure & Gavoille [10]. A *tree-decomposition* of a graph *G* is a tree *T* where each vertex *v* of *T* is associated to a
<figure><img src="image_2.png" /><figcaption>Figure 1: Inclusion diagram for graph classes discussed here (and related ones). If a class A has an upward path to class B, then A is included in B. For graphs in the green classes, ISOMETRIC PATH COVER is polynomial-time solvable; for graphs in the red classes, it is NP-complete. The white classes are still open. For all shown graph classes, ISOMETRIC PATH COVER is constant-factor approximable in polynomial time.</figcaption></figure>

subset $X_v$ of $V(G)$ called *bag*, such that: (i) $\bigcup_{v \in V(T)} X_v = V(G)$, (ii) for each edge $xy \in E(G)$, there exists a bag $X_v$ such that $\{x, y\} \subseteq X_v$, and (iii) for every vertex $x \in V(G)$, the vertices of $T$ associated to the bags containing $x$ induce a connected subtree of $T$. Define $length(T) = \max_{\substack{v \in V(T) \\ u, v \in X_v}} d(u, v)$, where the distance $d(u, v)$ denotes the number of edges in a shortest path between $u$ and $v$ in $G$. The *treelength* of $G$, denoted as $tl(G)$, is defined as $\min_T length(T)$, where the minimum is taken over all tree-decompositions of $G$.

**Our results.** We first settle the question of the complexity of ISOMETRIC PATH COVER, showing it is NP-hard even for chordal graphs.

**Theorem 1.** ISOMETRIC PATH COVER is NP-hard, even for chordal graphs with a dominating vertex.

To complement the above results, we design a constant-factor approximation algorithm for ISOMETRIC PATH COVER for graph classes that strictly contain chordal graphs, and other related ones. We summarize these results in Theorem 2.

**Theorem 2.** *There is a polynomial-time approximation algorithm that computes a valid solution for ISOMETRIC PATH COVER for every input graph, and has performance ratio of:*

(a) 2 on proper interval graphs,

(b) 3 on interval graphs,

(c) 4 on chordal graphs,

(d) 5 on graphs with a dominating shortest path,

(e) $(k+7)$ on $k$-chordal graphs, for $k \ge 4$, and

(f) $(6\ell + 2)$ on graphs with treelength at most $\ell$.

Theorem 2 is proved by analyzing one algorithm, which is based on constructing a suitable directed acyclic graph by breadth-first-search, and a reduction to the directed path covering problem for this digraph. We also prove that our analysis is tight for items (a), (b) and (c).
We then show that, on chordal graphs, one can solve ISOMETRIC PATH COVER in linear time when the treewidth (i.e., the clique number) is bounded, which implies that ISOMETRIC PATH COVER is fixed-parameter-tractable (FPT) on this class for parameter solution size.

**Theorem 3.** On chordal graphs of order $n$ and treewidth $w$, ISOMETRIC PATH COVER can be solved in time $2^{k2^{O(w)}}n$ and in time $2^{O(k)}n$, where $k$ is the solution size.

**Organisation of the paper.** We first prove our hardness result in Section 2. We then describe and analyze our approximation algorithm for ISOMETRIC PATH COVER in Section 3. The FPT algorithm for ISOMETRIC PATH COVER on chordal graphs is described in Section 4. We conclude in Section 5.

**General notations.** A sequence of vertices forms a path $P$ if any two consecutive vertices are adjacent. Whenever we fix a path $P$ of $G$, we shall refer to the subgraph formed by the edges between the consecutive vertices of $P$. For a path $P$ of a graph $G$ between two vertices $u$ and $v$, the vertices $V(P) \setminus \{u, v\}$ are internal vertices of $P$. A path between two vertices $u$ and $v$ is called a $(u, v)$-path. Similarly, we have the notions of isometric $(u, v)$-path and induced $(u, v)$-path.

## 2 NP-hardness of ISOMETRIC PATH COVER on chordal graphs

In this section, we prove that ISOMETRIC PATH COVER is NP-hard, answering a question raised in both [24, 23]. In fact, we prove that ISOMETRIC PATH COVER is NP-hard for chordal graphs. To prove this, we reduce INDUCED $P_3$-PARTITION on chordal graphs to ISOMETRIC PATH COVER on chordal graphs (in fact the reduction is the same as the one in [23]). Given a graph $G$, the objective of INDUCED $P_3$-PARTITION is to decide if there exists a partition $\mathcal{P}$ of $V(G)$ such that each set in $\mathcal{P}$ induces a path on three vertices in $G$. We use the following result, which is implied from a result of van Bevern et al. [31, Theorem 9] (their result does not concern induced paths, but one can easily check that their reduction holds with this restriction too).

**Proposition 4** ([31]). INDUCED $P_3$-PARTITION is NP-hard even if the input is a chordal graph with $3k$ vertices for some integer $k$.

**Proof of Theorem 1:** To prove this, we give a reduction from INDUCED $P_3$-PARTITION on chordal graphs to ISOMETRIC PATH COVER on chordal graphs. Let $G$ be a chordal graph such that $|V(G)| = 3k$ for some integer $k \ge 1$. Let $G'$ be the graph whose vertex set is $V(G') = V(G) \cup \{u, v, w\}$, where $u, v, w$ are three new vertices. The edge set of $G'$ is $E(G') = E(G) \cup \{(u, v), (v, w)\} \cup \{(v, x) \mid x \in V(G)\}$. It is easy to see that $G'$ is a chordal graph, and that $v$ is a dominating vertex.

We shall show that $G$ is a yes-instance of INDUCED $P_3$-PARTITION if and only if $G'$ has an isometric path cover of cardinality $k+1$. We have the following observation, due to the fact that $G'$ has diameter 2.

**Observation 5.** Any isometric path of $G'$ contains at most three vertices.

First, let $\mathcal{P}$ be a partition of $V(G)$ such that each set $P \in \mathcal{P}$ induces a path on three vertices. Observe that for any two vertices $u, v \in V(G')$, the isometric $(u, v)$-path in $G'$ contains at most three vertices. Therefore, each path $P \in \mathcal{P}$ is in fact an isometric path in $G'$. Hence, $\mathcal{P} \cup \{uvw\}$ is a set of isometric paths with cardinality $k+1$ that covers all vertices of $G'$.

To prove the reverse direction, assume that $G'$ has an isometric path cover $\mathcal{C}$ of size at most $k+1$. We now have the following observation.

**Observation 6.** There is an isometric path in $\mathcal{C}$ that covers both $u$ and $w$ in $G'$.

*Proof.* Otherwise, let $P, Q \in \mathcal{C}$ be two distinct isometric paths that cover $u$ and $v$, respectively and $S = V(G') \setminus (P \cup Q)$. Observe that $|S| \ge 3k-2$ and $\mathcal{C}$ contains a subset with $\mathcal{C}'$ containing $k-1$ isometric paths and covering all vertices of $S$. Therefore, $\mathcal{C}'$ contains an isometric path that covers at least four vertices of $S$. But this contradicts Observation 5. □
**Algorithm 1:** An algorithm for ISOMETRIC PATH COVER

**Input**: A graph $G$ and a vertex $v \in V(G)$.

**Output**: An isometric path cover of $G$.

1. Construct the graph $\vec{G}_v$ using a BFS starting at $v$;

2. $P_v \leftarrow$ directed path cover of $\vec{G}_v$ with minimum cardinality, computed using the reduction to bipartite matching;

3. **return** the set of paths obtained from $P_v$ by removing all orientations.

Now consider the set $C' = C \setminus \{P\}$ where $P \in C$ that covers both $u$ and $w$. Observe that $C'$ contains $k$ paths that must cover all vertices of $V(G') \setminus \{u, v, w\}$, i.e., of $V(G)$. Due to the facts that $|V(G)| = 3k$ and any isometric path in $G'$ contains at most three vertices of $G'$ (Observation 5), we have that $C'$ is a partition of $V(G)$, and therefore $G$ is a yes-instance of INDUCED P$_3$-PARTITION. $\square$

## 3 An approximation algorithm for ISOMETRIC PATH COVER

In this section, we will describe our approximation algorithm and prove Theorem 2. We will need the following definitions. For a vertex $r$ of $G$ and a set $S$ of vertices of $G$, the distance of $S$ from $r$, denoted as $d(r, S)$, is the minimum of the distance between any vertex of $S$ and $r$. For a subgraph $H$ of $G$, the distance of $H$ w.r.t. $r$ is $d(r, V(H))$. Formally, we have $d(r, S) = \min\{d(r, v) : v \in S\}$ and $d(r, H) = d(r, V(H))$.

For a graph $G$ and a vertex $r \in V(G)$, consider the following operations on $G$. First, remove all edges $xy$ from $G$ such that $d(r, x) = d(r, y)$. Let $G'_r$ be the resulting graph. Then, for each edge $e = xy \in E(G'_r)$ with $d(r, x) = d(r, y) - 1$, orient $e$ from $y$ to $x$. Let $\vec{G}'_r$ be the directed acyclic graph formed after applying the above operation on $G'$. Note that this digraph can easily be computed in linear time using a Breadth-First Search (BFS) traversal with starting vertex $r$.

In a digraph, a *directed path* is a path in the underlying *undirected graph*, such that all arcs are oriented in the same direction. A *directed path cover* of $\vec{G}'_r$ is a set of directed paths such that each vertex of $\vec{G}'_r$ belongs to at least one of the paths. We have the following observation, which holds because any directed path of $\vec{G}'_r$ is an isometric path in $G$.

**Observation 7.** For any vertex $r$ of a graph $G$, a *directed path cover* of $\vec{G}'_r$ is an isometric path cover of $G$.

The directed path cover problem in directed acyclic digraphs is the subject of Dilworth's theorem [9] (phrased in the equivalent language of partially ordered sets), which states that the size of an optimal solution is equal to the maximum size of an *antichain*, that is, a set of vertices in which no two vertices have a directed path connecting them. In a constructive proof of this theorem, Fulkerson [16] showed that the problem can be reduced to the maximum matching problem in a suitable bipartite graph, and thus, can be solved optimally in polynomial time.

The pseudocode of our algorithm for ISOMETRIC PATH COVER is given in Algorithm 1. Even though our algorithm will remain the same for all the considered graph classes, the analysis will differ. We will show that, depending on the graph class of the input graph $G$, there exists a “favourable choice” of a vertex $v$ such that a directed path cover of $\vec{G}_v$ is an isometric path cover of $G$, whose cardinality is not too far away from the isometric path number of $G$. To analyse the performance of our algorithm, we need the following definitions.

**Definition 8.** For a graph $G$ and a vertex $r \in V(G)$, two vertices $x, y \in V(G)$ are antichain vertices if there are no directed paths from $x$ to $y$ or from $y$ to $x$ in $\vec{G}'_r$. A set $X$ of vertices of $G$ is an antichain set if any two vertices in $X$ are antichain vertices. The cardinality of the largest antichain set in $\vec{G}'_r$ will be denoted by $\beta(\vec{G}'_r)$. The cardinality of the largest antichain set of $G$, is defined as

$$ \beta(G) = \min \left\{ \beta(\vec{G}_r) : r \in V(G) \right\} $$
**Definition 9.** Let $r$ be a vertex of a graph $G$. For a path $P$, $A_r(P)$ shall denote the maximum antichain set of $P$ in $\vec{G}_r$. The isometric path antichain cover number of $\vec{G}_r$, denoted by $ipacc(\vec{G}_r)$, is defined as follows:

$$ipacc(\vec{G}_r) = \max \{|A_r(P)|: P \text{ is an isometric path}\}$$

The isometric path antichain cover number of graph $G$, denoted as $ipacc(G)$, is defined as the minimum over all possible antichain covers of its associated directed acyclic graphs:

$$ipacc(G) = \min \{ipacc(\vec{G}_r) : r \in V(G)\}$$

We will use the next lemma that follows directly from Dilworth's Theorem [9], Observation 7, and Definitions 8 and 9.

**Lemma 10.** Let $G$ be a graph and $\mathcal{P}$ be any isometric path cover of $G$ with minimum cardinality. We have:

$$\frac{\beta(G)}{ipacc(G)} \le |\mathcal{P}| \le \beta(G).$$

*Proof.* Let $r$ be a vertex of $G$ such that $\beta(G) = \beta(\vec{G}_r)$. Then, by Observation 7, we have that $|\mathcal{P}| \le \beta(\vec{G}_r) = \beta(G)$. Now, let $r'$ be a vertex of $G$ such that $ipacc(G) = ipacc(\vec{G}_{r'})$. Since any isometric path in $\mathcal{P}$ contains at most $ipacc(\vec{G}_{r'})$ many elements of $\beta(\vec{G}_{r'})$, we have $\frac{\beta(\vec{G}_{r'})}{ipacc(\vec{G}_{r'})} \le |\mathcal{P}|$. Finally, since $\beta(G) \le \beta(\vec{G}_{r'})$, we have $\frac{\beta(G)}{ipacc(G)} \le |\mathcal{P}|$. $\square$

In the next section, we will prove upper bounds on the isometric path antichain cover number of various graph classes, implying the approximation ratios fulfilled by Algorithm 1.

## 3.1 Lemmas on the isometric path antichain cover number

In this section, we shall prove some lemmas relating the isometric path antichain cover number with other parameters. We begin by establishing a relationship between the length of an isometric path $P$ and the size of $A_r(P)$, which will be crucial for our analysis of Algorithm 1.

**Lemma 11.** Let $G$ be a graph and $r$, an arbitrary vertex of $G$. Consider the directed acyclic graph $\vec{G}_r$, and let $P$ be an isometric path between two vertices $x$ and $y$ in $G$ with $d(r, x) \le d(r, y)$. Then $|P| \ge d(r, y) - d(r, x) + |A_r(P)| - 1$.

*Proof.* Orient the edges of $P$ from $y$ to $x$ in $G$. First, observe that $P$ must contain a set $E_1$ of oriented edges such that $|E_1| = d(r, y) - d(r, x)$ and for any $\vec{ab} \in E_1$, $d(r, a) = d(r, b) + 1$. Let the vertices of the largest antichain set of $P$ in $\vec{G}_r$, i.e., $A_r(P)$, be ordered as $a_1, a_2, \dots, a_t$ according to their occurrence while traversing $P$ from $y$ to $x$. For $i \in [2, t]$, let $P_i$ be the subpath of $P$ between $a_{i-1}$ and $a_i$. Observe that for any $i \in [2, t]$, since $a_i$ and $a_{i-1}$ are antichain vertices, there must exist an oriented edge $\vec{b_i c_i} \in E(P_i)$ such that either $d(r, b_i) = d(r, c_i)$ or $d(r, b_i) = d(r, c_i) - 1$. Let $E_2 = \{b_i c_i\}_{i \in [2, t]}$. Observe that $E_1 \cap E_2 = \emptyset$ and therefore $|P| \ge |E_1| + |E_2| = d(r, y) - d(r, x) + |A_r(P)| - 1$. $\square$

Next, we shall relate isometric path antichain cover number with a parameter called *cluster diameter*, introduced in [10]. Let $G$ be a graph and $r$ be an arbitrary vertex of $G$. For a non-negative integer $i$, let $G^i(r)$ denote the graph induced by the vertices whose distance from $r$ is at least $i$. Formally, $G^i(r) = G[\{u: d(r, u) \ge i\}]$. A *cluster* is a set $S$ of vertices such that all vertices of $S$ are at the same distance from $r$ and any two vertices of $S$ lie in the same connected component of $G^i(r)$, where $i = d(r, S)$. The *cluster diameter* of $G$ with respect to $r$, denoted as $\Delta_r(G)$, was defined in [10] as follows:

$$\Delta_r(G) = \max\{d(u, v) : u, v \text{ lie in the same cluster with respect to } r\}$$
We shall use the following technical lemma to prove bounds on the isometric path antichain cover number of graphs with bounded treelength and on graphs with bounded chordality in Lemma 16 and Lemma 18, respectively.

**Lemma 12.** Let $G$ be a graph, $r$ be an arbitrary vertex of $G$, and let $P$ be an isometric path such that $|A_r(P)| \ge \alpha$ in $\vec{G}_r$. Then $\Delta_r(G) \ge \lfloor \frac{\alpha}{2} \rfloor - 1$.

*Proof.* Let the two endpoints of $P$ be $u$ and $v$ and, without loss of generality, assume $\mathbf{d}(r, u) \le \mathbf{d}(r, v)$. Let $A = A_r(P)$, and let $a$ be a vertex of $P$ such that $\mathbf{d}(r, a) = \mathbf{d}(r, P)$. Let $P_u$ (resp. $P_v$) denote the subpath of $P$ between $u$ and $a$ (resp. between $v$ and $a$). Observe that there exists a path $Q \in \{P_u, P_v\}$ such that $Q$ contains an antichain set of cardinality $\lceil \frac{\alpha}{2} \rceil$. Notice that $a$ is one of the endpoints of $Q$ and $\mathbf{d}(r, Q) = \mathbf{d}(r, a)$. Let $c$ be the other endpoint of $Q$. Let $a_1$ be the first vertex of $A$ which is encountered while traversing $Q$ starting from $c$ and ending at $a$. If $\mathbf{d}(r, a_1) = \mathbf{d}(r, a)$, then let $b = a_1$. Otherwise, consider a vertex $b$ such that $\mathbf{d}(r, b) = \mathbf{d}(r, a)$ and there is an oriented path from $a_1$ to $b$ in $\vec{G}_r$. Clearly, $a$ and $b$ lie in the same cluster of $G$ with respect to $r$. If $\mathbf{d}(a, b) \le (\lceil \frac{\alpha}{2} \rceil - 2)$, then $\mathbf{d}(a, a_1) \le \mathbf{d}(a, b) + \mathbf{d}(b, a_1) \le (\lceil \frac{\alpha}{2} \rceil - 2) + \mathbf{d}(r, a_1) - \mathbf{d}(r, b) < |A_r(Q)| - 1 + \mathbf{d}(r, a_1) - \mathbf{d}(r, a)$. But this contradicts Lemma 11. Hence, $\mathbf{d}(a, b) \ge \lfloor \frac{\alpha}{2} \rfloor - 1$. $\square$

Next, we state the following definition.

**Definition 13.** For an integer $t \ge 1$, a graph $G$ is *t-slender* if there exists a vertex $r \in V(G)$ such that, for all vertices $u, v \in V(G)$ with $\mathbf{d}(r, u) = \mathbf{d}(r, v)$, we have $\mathbf{d}(u, v) \le t$.

Observe that if a graph $G$ is *t-slender*, then, there exists a vertex $r \in V(G)$ such that $\Delta_r(G) \le t$. Lemma 12 then implies *ipacc*($G$) $\le 2t+2$. However, the following lemma will help us prove better upper bounds for graphs that are *t-slender*.

**Lemma 14.** Let $G$ be a $t$-slender graph for some integer $t \ge 1$. Then, *ipacc*($G$) $\le t+1$.

*Proof.* By definition, there exists a vertex $r \in V(G)$ such that for any $u, v \in V(G)$ with $\mathbf{d}(r, u) = \mathbf{d}(r, v)$, we have $\mathbf{d}(u, v) \le t$. Let $P$ be an isometric path between two vertices $x$ and $y$ with, without loss of generality, $\mathbf{d}(r, x) \le \mathbf{d}(r, y)$. If $\mathbf{d}(r, x) < \mathbf{d}(r, y)$, then let $y'$ be a vertex such that $\mathbf{d}(r, y') = \mathbf{d}(r, x)$ and there is a path between $y$ to $y'$ in $\vec{G}_r$. Otherwise, let $y' = y$. Since $\mathbf{d}(x, y') \le t$, $\mathbf{d}(x, y) \le t + \mathbf{d}(r, y) - \mathbf{d}(r, x)$. On the other hand, due to Lemma 11, we have $|P| = \mathbf{d}(x, y) \ge \mathbf{d}(r, y) - \mathbf{d}(r, x) + |A_r(P)| - 1$. Hence, $|A_r(P)| \le t+1$. $\square$

In particular, we shall use the above lemma to prove better upper bounds for the isometric anti chain path cover number of graphs containing a dominating shortest path, interval graphs and proper interval graphs in Lemma 20, 21, and 22, respectively.

## 3.2 Upper bounds on the isometric path antichain cover number

In this section, we will first show that *ipacc*($G$) can be bounded by a linear function of *tl*($G$). We will use the following result of Dourisboure & Gavoille [10], which was restated in the following form by Abdulhakeem & Dragan [25].

**Proposition 15** ($[10, 25]$). Let $r$ be an arbitrary vertex of a graph $G$ with treelength at most $\ell$. Then $\Delta_r(G) \le 3\ell$.

**Lemma 16.** If $G$ is a graph with treelength at most $\ell$, then *ipacc*($G$) $\le 6\ell + 2$.

*Proof.* Assume that there exists a vertex $r$ of $G$ and an isometric path $P$ of $G$ such that $|A_r(P)| \ge 6\ell + 3$ in $\vec{G}_r$. Then, by Lemma 12, there are two vertices $a$ and $b$ such that $\mathbf{d}(r, a) = \mathbf{d}(r, b)$, $\mathbf{d}(a, b) \ge \lceil \frac{6\ell+3}{2} \rceil - 1 \ge 3\ell + 1$, and $a, b$ lie in the same cluster with respect to $r$. Hence, $\Delta_r(G) \ge 3\ell + 1$. This contradicts Proposition 15. $\square$
Now, we will prove an upper bound for the isometric path antichain cover number of k-chordal graphs. Note that the treelength of k-chordal graphs is at most $\frac{k}{2}$ [17]. Therefore, Lemma 16 implies that the isometric path antichain cover number of a k-chordal graph is at most $3k + 1$. To prove a better upper bound, we will also use the following result of Dourisboure & Gavoille [10].

**Proposition 17** ([10]). Let $r$ be any vertex of a k-chordal graph $G$. Then, $\Delta_r(G) \le \frac{k}{2} + 2$.

**Lemma 18.** If $G$ is a k-chordal graph with $k \ge 4$, then $ipacc(G) \le k + 7$.

*Proof.* Assume that there exists a vertex $r$ of $G$ and an isometric path $P$ of $G$ such that $|A_r(P)| \ge k+8$ in $\overarc{G}_r$. Then, by Lemma 12, there are two vertices $a$ and $b$ such that $d(r, a) = d(r, b)$, $d(a, b) \ge \lceil \frac{k+8}{2} \rceil - 1 \ge \frac{k}{2} + 3$, and $a, b$ lie in the same cluster with respect to $r$. This contradicts Proposition 17. $\square$

Now, we will prove upper bounds on the isometric path antichain cover number of graphs with a dominating shortest path. Recall that a shortest path $P$ of a graph $G$ is dominating if any vertex of the graph is either in $P$ or adjacent to at least one of the vertices of $P$. Note that the class of graphs with a dominating shortest path is incomparable with the class of k-chordal graphs for any fixed integer $k$. We can now prove the following lemma.

**Lemma 19.** If a graph $G$ has a dominating shortest path, then $G$ is 4-slender.

*Proof.* Let $r, s$ be the endpoints of a dominating shortest path $P$. Let $x_0 = r, x_1, x_2, \dots, x_i = s$ be the vertices of $P$ ordered as they are encountered while traversing $P$ from $r$ to $s$. Let $a, b$ be two vertices of $G$ such that $d(r, a) = d(r, b)$. If $d(r, a) = i + 1$, then $d(a, b)$ is at most 2 as both $a, b$ will be adjacent to $x_i$. If $d(r, a) = i$, then $d(a, b)$ is at most 3 since $\{a, b\} \subset N[x_i] \cup N[x_{i-1}]$. Otherwise, $0 < d(r, a) \le i - 1$. In this case, $d(a, b)$ is at most 4 since $\{a, b\} \subset N[x_{i-1}] \cup N[x_i] \cup N[x_{i+1}]$. $\square$

Taken together, Lemmas 14 and 19 imply the following lemma which we will use again in Section 3.3.

**Lemma 20.** If $G$ has a dominating shortest path, then $ipacc(G) \le 5$.

We will prove an improved version of Lemma 20 for interval graphs.

**Lemma 21.** If $G$ is an interval graph, then $ipacc(G) \le 3$.

*Proof.* Due to Lemma 14, we will be done by showing that if $G$ is an interval graph, then, $G$ is 2-slender. Let $\mathcal{I} = \{[x_u^-, x_u^+] : u \in V(G)\}$ be an interval representation of $G$. Let $v$ be the vertex such that $x_v^+ = \min\{x_a^+ : a \in V(G)\}$. In other words, $v$ corresponds to the interval with the leftmost right endpoint. For a vertex $w$, define $r_w = z$ such that $x_z^+ = \max\{x_{z'}^+ : z' \in N[z]\}$. In other words, $z$ is the neighbour of $w$ that has the rightmost right endpoint. Observe that $G$ has a dominating shortest path $x_0 = v, x_1, x_2, \dots, x_i$ such that for each $1 \le j \le i$, $x_i = r_{x_{i-1}}$. Now, consider two vertices $a, b$ with $d(v, a) = d(v, b) = j$. Observe that $\{a, b\} \subset N[x_{j-1}]$. Hence, $d(a, b) \le 2$ and therefore, $G$ is 2-slender. $\square$

In Observation 27 we show that that the bound proved in the above lemma is essentially tight by constructing an interval graph whose isometric path antichain cover number is exactly three. Any proper interval graph $G$ has a vertex $v$ such that the spanning tree $T_v$ obtained from a BFS starting at $v$ is 1-slender [19], and thus, $G$ is 1-slender as well. An immediate consequence of this result, due to Lemma 14, is the following.

**Lemma 22.** If $G$ is a proper interval graph, then $ipacc(G) \le 2$.

In Observation 28 we show that that the bound proved in the above lemma is essentially tight.

Interval graphs are a subclass of chordal graphs (i.e., graphs with chordality 3). Since chordal graphs are exactly the graphs with treelength 1, Lemma 16 implies that the isometric path antichain cover number of chordal graphs is at most 7. Below, we prove a better upper bound using the two following properties of chordal graphs.
<figure><img src="image_3.png" /><figcaption>Figure 2: Proof of Claim 25.1. Path $P'$ is dotted, and path $P_j$ is red.</figcaption></figure>

**Observation 23.** Let $r$ be an arbitrary vertex of a chordal graph $G$. Let $u, v \in V(G)$ be two vertices such that $d(r, u) = d(r, v) = i$ and there exists an $(u, v)$-path $P$ such that $V(P - \{u, v\}) \subseteq V(G_r^{i+1})$. Then $uv \in E(G)$.

*Proof.* If $P$ has length one, the result is obvious, thus, we can assume that $P$ has length at least 2. Assume for contradiction that $uv \notin E(G)$. Let $P_1$ be an isometric $(u, v)$-path in the graph induced by $V(G - G^i(r)) \cup \{u, v\}$. Consider another isometric $(u, v)$-path $Q$ such that $d(r, Q - \{u, v\}) = d(r, u) + 1$. Note that the existence of $P$ guarantees that there is at least one such path. For any two nonconsecutive vertices $u_i, u_j \in Q$, $u_i u_j \notin E(G)$. Since $uv \notin E(G)$, note that $P_1$ and $Q$ are induced paths. Moreover, since, for any vertex $p \in V(P_1 - \{u, v\})$ and $q \in V(Q - \{u, v\})$, $d(r, q) - d(r, p) \ge 2$, the paths $P_1$ and $Q$ are internally disjoint. Therefore, $P_1 \cup Q$ induces a cycle of length at least 4, which contradicts the fact that $G$ is a chordal graph. $\square$

**Observation 24.** Let $r$ be an arbitrary vertex of a chordal graph $G$, and let $P$ be an isometric path of $G$. Let $u, v \in V(P)$ be two distinct vertices of $P$ such that $d(r, u) = d(r, v)$. Then, there cannot be any vertex $w$ in the $(u, v)$-subpath of $P$ such that $d(r, w) > d(r, v)$.

*Proof.* Assume for contradiction that such a path $P$ and vertices $u, v$, and $w$ exist, and let $d(r, u) = d(r, v) = i$. Consider the $(u, v)$-subpath $Q$ of $P$, and let $u = v_1, \dots, v_\ell = v$ be the ordering of vertices of $Q$, along the path $Q$. Moreover, let the alias of the vertex $w$ in this ordering be $v_b$. Then, observe that there exist two vertices $v_a, v_c \in V(Q)$, where $1 \le a < b < c \le \ell$, such that $d(r, v_a) = d(r, v_c) = i$, $v_a v_c \notin E(G)$, and there is a $(v_a, v_c)$-subpath $Q'$ of $Q$ such that $V(Q' - \{v_a, v_c\}) \subseteq V(G_r^{i+1})$. However, this contradicts Observation 23. $\square$

**Lemma 25.** If $G$ is a chordal graph, then, ipacc ($G$) $\le 4$.

*Proof.* Let $r$ be an arbitrary vertex of $G$. Now, assume by contradiction that there is an isometric path $P$ in $G$ with endpoints $u$ and $v$, such that $|A_r(P)| \ge 5$ in $\overrightarrow{G_r}$. Let $a_1, \dots, a_5 \in A_r(P)$ be five antichain elements, that appear in this order while traversing $P$ from $u$ to $v$. We will eventually show that the existence of $P$ implies that $\Delta_r(G) \ge 4$, contradicting Proposition 17. Let $d(r, P) = i$ and $x_u$ (resp. $x_v$) be a vertex such that $d(r, x_u) = i$ (resp. $d(r, x_v) = i$) and there is an oriented path from $u$ (resp. $v$) to $x_u$ (resp. $x_v$) in $\overrightarrow{G_r}$ (possibly, $u = x_u$ or $v = x_v$). Observe that $x_u$ and $x_v$ lie in the same cluster with respect to $r$. First, we prove the following claim.
**Claim 25.1.** $d(r, P) = d(r, a_3)$.

*Proof.* Assume by contradiction that $d(r, P) < d(r, a_3)$. Refer to Figure 2 for an illustration of the different notations for this proof. Let $top \in V(P)$ be a vertex such that $d(r, top) = d(r, P)$. Recall that $d(r, top) = i$. Now, let $P_u$ be the $(u, top)$-subpath of $P$, and let $P_v$ be the $(v, top)$-subpath of $P$. Observe that either $a_3 \in V(P_u)$ or $a_3 \in V(P_v)$. Without loss of generality, assume that $a_3 \in V(P_u)$.

Let $P'$ be the $(top, a_3)$-subpath of $P_u$, and let $top = u_1, \dots, u_\ell = a_3$ be the ordering of vertices of $V(P')$, along the path $P'$. Let $u_j$, for $j \ge 1$, be the vertex with minimum index $j$ such that $d(r, u_j) = i$ and $d(r, u_{j+1}) = i + 1$. Note that $u_j$ is distinct from $a_3$, and $u_j$ can be the same as top.

(+) The $(u_j, u)$-subpath of $P_u$, say $P_j$, satisfies $V(P_j - \{u_j\}) \subseteq V(G_r^{i+1})$.

To prove (+), assume by contradiction that there is a vertex $w \in V(P_j - \{u_j\})$ with $d(r, w) = i$. Then, due to the definition of $u_j$, $u_{j+1}$ is in the $(u_j, w)$-subpath, with $d(r, w) = d(r, u_j) = i$ and $d(r, u_{j+1}) = i + 1$. But this contradicts Observation 24 and completes the proof of (+).

Let $q$ be a vertex such that $d(r, q) = i$ and there is an oriented path $\vec{Q}$ in $\vec{G}_r$ from $u$ to $q$. Due to (+), $q$ is distinct from $u$. Let $Q$ be the path obtained after removing the orientation of $\vec{Q}$. Note that $Q$ is an isometric $(q, u)$-path in $G$. Also, note the following:

(++) $V(Q - \{q\}) \subseteq V(G_r^{i+1})$.

Now, let us consider the $(u_j, u)$-subpath $P_j$ of $P_u$ defined above. Combining (+) and (++), we have that $V(Q) \cup V(P_j)$ forms a $(u_j, q)$-path, say $T$, such that $V(T - \{u_j, q\}) \subseteq V(G_r^{i+1})$. Due to Observation 23, $u_j q \in E(G)$. This implies that $d(u, u_j) \le d(r, u) - d(r, q) + 1$. But, since $P_j$ is an isometric $(u_j, u)$-path and $|A_r(P_j)| \ge 3$ (indeed $a_3, a_2, a_1$ lie in $P_j$), due to Lemma 11, we have $d(u, u_j) \ge d(r, u) - d(r, u_j) + 2 = d(r, u) - d(r, q) + 2$, which is a contradiction. □

Using Claim 25.1, we can now prove that $d(x_u, x_v) \ge 4$. Since $P$ is an isometric $(u, v)$-path and $a_3 \in V(P)$, we have:

$$d(u, v) = d(u, a_3) + d(a_3, v) \qquad (1)$$

cObserve that the $(u, a_3)$-subpath of $P$ contains at least three antichain elements of $\vec{G}_r$. Lemma 11 then implies $d(u, a_3) \ge d(r, u) - d(r, a_3) + 2 = d(r, u) - d(r, x_u) + 2$. Since $x_u$ belongs to an isometric $(r, u)$-path, we have $d(x_u, u) = d(r, u) - d(r, x_u)$, and therefore:

$$d(u, a_3) \ge d(x_u, u) + 2 \qquad (2)$$

By symmetry, we have:

$$d(v, a_3) \ge d(x_v, v) + 2 \qquad (3)$$

Combining the fact that $d(u, v) \le d(u, x_u) + d(x_u, x_v) + d(x_v, v)$ with Equations 1-3, we have $d(x_u, x_v) \ge 4$. This implies $\Delta_r(G) \ge 4$, which contradicts Proposition 17. This completes the proof. □

In Observation 26 we show that that the bound proved in the above lemma is essentially tight by constructing a chordal graph whose isometric path antichain cover number is exactly four.

## 3.3 Proof of Theorem 2

In this section we complete the proof of Theorem 2. Recall that Algorithm 1 takes as input a graph $G$ and a vertex $v$. Then, it constructs the directed acyclic graph $\vec{G}_v$ and a directed path cover of $\vec{G}_v$.

First, we will prove Theorem 2(a). Let $G$ be a proper interval graph. Then, due to Lemma 22, $G$ has a vertex $v$ such that for any isometric path $P$ of $G$, the cardinality of $A_v(P)$ in $\vec{G}_v$ is at most two. Let $P_v$ be the isometric path cover returned by Algorithm 1 with $G$ and $v$ as input. Let $\mathcal{A}$ be the largest antichain set of $\vec{G}_v$ and $OPT$ be a minimum cardinality isometric path cover of $G$. Due to Lemma 10, we have $|P_v| \le |\mathcal{A}| \le 2|OPT|$. This completes the proof.
<figure><img src="image_4.png" /><figcaption>Figure 3: A tight-approximation example for chordal graphs</figcaption></figure>

Proofs of Theorem 2(b)-(f) follow from similar arguments. In particular, by combining Lemmas 10 and 21 we have the proof of Theorem 2(b). Combining Lemmas 10 and 25 we have the proof of Theorem 2(c). Combining Lemmas 10 and 20 we have the proof of Theorem 2(d). Combining Lemmas 10 and 18 we have the proof of Theorem 2(e). Combining Lemmas 10 and 16 we have the proof of Theorem 2(f).

## 3.4 Tightness of our analysis

In this section, we show that the analysis of our algorithm is tight for chordal graphs, interval graphs, and proper interval graphs.

**Observation 26.** There exist chordal graphs whose isometric path antichain cover number is 4. Moreover, for any $c < 4$, Algorithm 1 cannot guarantee an approximation ratio of $c$ for chordal graphs.

*Proof.* For integers $\ell$ and $k$, consider the following construction for graph $G_k^\ell$. Let $V(G_k^\ell) = \{w\} \cup \{u^i, v^i: i \in [\ell]\} \cup \{a_j^i, b_j^i, c_j^i, d_j^i: i \in [\ell], j \in [k]\}$ and $E(G_k^\ell) = \{wu_i, wv_i: i \in [\ell]\} \cup \{u^i a_j^i, u^i b_j^i, u^i c_j^i, v^i b_j^i, v^i c_j^i, v^i d_j^i: i \in [\ell], j \in [k]\} \cup \{a_j^i b_j^i, b_j^i c_j^i, c_j^i d_j^i: i \in [\ell], j \in [k]\}$. See Figure 3 for reference. Note that $G_k^\ell$ is a chordal graph and ipacc($G_k^\ell$) = 4. Observe that the isometric path cover number of $G$ is at most $\ell k + \ell + 1$. Indeed one such isometric path cover can be constructed as follows. For $i \in [\ell]$ and $j \in [k]$, consider the isometric paths $P_j^i = a_j^i b_j^i c_j^i d_j^i$. Also consider, for $i \in [\ell]$, the isometric paths $Q_i = u^i v^i$. Observe that

$$ \mathcal{P} = \{w\} \bigcup_{i \in [\ell]} Q_i \bigcup_{\substack{i \in [\ell] \\ j \in [k]}} P_j^i $$

is an isometric path cover of $G_k^\ell$ of size $\ell k + \ell + 1$. Moreover, Algorithm 1 will return a solution of size at least $4k(\ell - 1)$ for $G_k^\ell$. Indeed if Algorithm 1 has $G_k^\ell$ and $w$ as the input, then it will return a solution of size $4\ell k$. Otherwise, there exists a $i \in [\ell], j \in [k]$ such that Algorithm 1 has $G_k^\ell$ and $z$ as the input where $z \in \{u^i, v^i\} \cup \{a_j^i, b_j^i, c_j^i, d_j^i\}$. In this case, Algorithm 1 will return a solution of cardinality at least $4k(\ell - 1)$. This gives us an approximation ratio of $\frac{4k(\ell - 1)}{\ell(k+1)+1}$. Now, for any $c < 4$, we can set $k$ and $\ell$ such that the approximation ratio is greater than $c$. $\square$

**Observation 27.** There exist interval graphs whose isometric path antichain cover number is 3. Moreover, for any $c < 3$, Algorithm 1 cannot guarantee an approximation ratio of $c$ for interval graphs.

*Proof.* To see this, consider the following graph. Let $P_k$ be a path on $k$ vertices $v_1, \dots, v_k$ (where $k$ is a multiple of 3). Let $G$ be the graph obtained by adding a universal vertex $v$ to $P_k$ (i.e., $V(G) = V(P_k) \cup \{v\}$ and $E(G) = E(P_k) \cup \{vv_i: i \in [k]\}$). See Figure 4 for reference. Note that $G$ is an interval graph and ipacc()($G$) = 3. Moreover, isometric path cover number of $G$ is $\frac{k}{3} + 1$, and Algorithm 1 returns an
<figure><img src="image_5.png" /><figcaption>Figure 4: A tight-approximation example for interval graphs</figcaption></figure>

isometric path cover of size at least $k-3$. Now, for any $c < 3$, we can set $k$ such that the approximation ratio $\left(\frac{3(k-3)}{k+1}\right)$ is greater than $c$. $\square$

**Observation 28.** There exist proper interval graphs whose isometric path antichain cover number is 2. Moreover, for any $c < 2$, Algorithm 1 cannot guarantee an approximation ratio of $c$ for proper interval graphs.

*Proof.* Let $G$ be the complete graph on $k$ vertices (where $k$ is even). Note that $G$ is a proper interval graph. Moreover, isometric path cover number of $G$ is $\frac{k}{2}$, and Algorithm 1 returns an isometric path cover of size $k-1$. Now, for any $c < 2$, we can set $k$ such that the approximation ratio $\left(\frac{2(k-1)}{k}\right)$ is greater than $c$. $\square$

# 4 An FPT algorithm for solution size on chordal graphs

In this section, we prove Theorem 3 using dynamic programming on tree decompositions. As the problem deals with shortest paths, it seems difficult to generally solve it on graphs of bounded treewidth, as it is not straightforwardly expressible in monadic second-order logic. Certain related problems like GEODETIC SET are in fact W-hard for treewidth [20]. For chordal graphs however, we can exploit the structural properties of shortest paths to design such an algorithm. As a corollary, we show that this yields an FPT algorithm for the parameter solution size alone.

Indeed, we will prove the first part of Theorem 3 that ISOMETRIC PATH COVER can be solved in time $2^{O(2^k w^2)} \cdot n$ on chordal graphs of order $n$ and treewidth $w$, where $k$ is the solution size. To obtain the running time $2^{2^O(k)} \cdot n$ as a corollary, note first that for chordal graphs, the treewidth $w$ is equal to the clique number minus one (and the latter can be determined in polynomial time on this class). However, an isometric path can cover at most two vertices of any clique. Thus, if $k < (w+1)/2$, then we can return NO. Otherwise, the running time follows from the first running time.

Nice tree decompositions are a well-known tool for designing dynamic programming algorithms for graphs of bounded treewidth, see [4]. Let us start by properly defining what is a nice tree decomposition of a chordal graph (those can be constructed in linear time, see [4, Section 4]).

**Definition 29.** A nice tree decomposition of a chordal graph $G$ is a rooted tree $T$ where each node $v$ is associated to a subset $X_v$ of $V(G)$ called a *bag*, and each internal node has one or two *children*, with the following properties.

1. The nodes of $T$ containing a given vertex of $G$ form a nonempty connected subtree of $T$.

2. Any two adjacent vertices of $G$ appear in the bag of a common node of $T$.

3. For each node $v$ of $T$, $X_v$ is a clique.

4. Each node of $T$ belongs to one of the following types: *introduce*, *forget*, *join* or *leaf*.

5. A join node $v$ has two children $v_1$ and $v_2$ such that $X_v = X_{v_1} = X_{v_2}$.
6. An introduce node v has one child $v_1$ such that $X_v \setminus \{x\} = X_{v_1}$, for some vertex $x \in X_v$.

7. A forget node v has one child $v_1$ such that $X_v = X_{v_1} \setminus \{x\}$, for some vertex $x \in X_{v_1}$.

8. A leaf node v is a leaf of T with $X_v = \{x\}$ for some vertex x of G.

9. The tree T is rooted at a leaf node r.

For a nice tree decomposition and a node v, we define $G_{\le v}$ as the subgraph of G induced by the vertices of the subtree of the decomposition rooted at v. We can similarly define $G_{<v} = G_{\le v} - X_v$, $G_{\ge v} = G - G_{<v}$, and $G_{>v} = G - G_{\le v}$.

Note that for a clique X and a vertex y, X can be partitioned into two (not necessarily both nonempty) sets of vertices according to their distances to y, as y has at most two distinct distance values to the vertices of X, with a difference of at most 1 between these values. Based on this, we give the following definition, inspired from [6].

**Definition 30.** For a clique X and a vertex y of G, we denote by $\text{close}(X, y)$ the set of vertices of X that have minimal distance to y among the vertices of X, that is, for every vertex z of X, $d(y, z) = d$ if $z$ is in $\text{close}(X, y)$, and $d(y, z) = d+1$ otherwise. We say that y is close to the set $\text{close}(X, y)$.

In a chordal graph, every maximal clique forms a clique cutset, and that clique will be associated to some node of the tree decomposition. As in most treewidth-based dynamic programming schemes, we will compute the potential solutions by bottom-up traversal of the tree decomposition. For this, we will define some *types* of solutions of ISOMETRIC PATH COVER, depending on how they interact with a given bag of the tree decomposition. The number of types is bounded by a function of *k* and *w*. We must then show how local solutions of a given type (if they exist) can be computed using the already computed information from the children.

Let us first give the key ideas needed for the dynamic programming scheme. We name the *k* paths $P_1, \dots, P_k$. A *partial solution* for ISOMETRIC PATH COVER with respect to a bag $X_v$ of a node *v* of *T*, consists of *k* (possibly empty) subsets $P_1^v, \dots, P_k^v$ of $X_v$ of size at most 2, each representing the intersection of a path $P_i$ with $X_v$, whose union equals $X_v$.

Making sure that an existing partial solution is extended so as to give an *induced* path cover is not too difficult, indeed, since the graph is chordal, if a path has a chord, that would give a cycle and thus there would be a triangle consisting of three vertices of the path. Necessarily, this triangle would be included in some bag, a contradiction. However, to make sure that the computed path is *isometric* is less trivial, but can be done due to the above definition of closeness. Indeed, we have the following lemma.

**Lemma 31.** Let G be a chordal graph and P be a path in G. The path P is isometric if and only if, for every clique X of G intersecting P and for every vertex y of P, there is exactly one vertex of $V(P) \cap X$ in $\text{close}(X, y)$.

*Proof.* Assume that P is a path of G.

For the first implication, assume that P is isometric, and let X be a clique of G intersecting P. If, for some vertex y of P, there are two vertices of $V(P) \cap X$ in $\text{close}(X, y)$, then both have the same distance to y. Thus, y is in the middle of the two vertices with respect to P, but then there is a chord on P, which is not isometric, a contradiction.

For the reverse direction, assume that the condition holds for every clique X of G. Assume by contradiction that P is not isometric, which means that there are two vertices of P whose distance in G is less than their distance in P. Let $x_1, x_2$ be two such vertices with the smallest possible distance in P, and let us call $P'$ the $(x_1, x_2)$-subpath of P. Thus, any proper subpath of $P'$ is isometric. Note that $P'$ has at least two edges. Let $P''$ be a shortest path from $x_1$ to $x_2$. By the choice of $x_1, x_2$, we have $V(P') \cap V(P'') = \{x_1, x_2\}$. Let $z'$ be the neighbour of $x_2$ in $P'$. Since $P'$ is not isometric, we have $z' \neq x_1$. Let $z''$ be the neighbour of $x_2$ on $P''$ (possibly, $z'' = x_1$).

We claim that $z'$ and $z''$ are adjacent in G. If $z'' = x_1$ and $z'$ is a neighbour of $x_1$, this is true. Note that $P' \cup P''$ form a cycle. Since any proper sub-path of $P'$ is isometric, if $z'' = x_1$ (that is, $d(x_1, x_2) = 1$)
but $P''$ has length at least 3, then this cycle is an induced cycle of length at least 4, a contradiction. Thus, we can next assume that $P''$ has at least two edges (then $P'$ has at least three edges). Since any proper sub-path of $P'$ is isometric and $d(x_1, x_2) \ge 2$, $x_1, x_2$ are not adjacent, and so $P'$ is an induced path. Since $P''$ is isometric, $P''$ is induced as well. Thus, since $G$ is chordal, each internal vertex of $P'$ has a neighbour in $V(P'') \setminus \{x_1, x_2\}$, each internal vertex of $P''$ has a neighbour in $V(P') \setminus \{x_1, x_2\}$, and $x_1, x_2$ have exactly one neighbour in each of $P', P''$. Thus, $z'$ and $z''$ are adjacent, as claimed (otherwise $z'$ forms an induced cycle of length at least 4 with its neighbour in $P''$ that is closest to $x_2$ and the sub-path of $P''$ from that neighbour to $x_2$, a contradiction).

Now, consider the clique consisting of $x_2$ and $z'$. Then, $\text{close}(\{x_2, z'\}, x_1)$ contains both $x_2$ and $z'$, which contradicts the condition of the statement. This completes the proof. $\square$

Thus, following Lemma 31, for every bag $X_v$ and for every subset $X$ of $X_v$, we will keep track of whether each path $P_i$ contains a vertex $y$ with $\text{close}(X_v, y) = X$ in the previously computed partial solutions that can lead to the current partial solution. We will also keep track whether the future partial solutions contain such a vertex. This information can be propagated along the bottom-up dynamic programming, together with the fact that the computed solutions must form a path cover. By Lemma 31, it will then be enough to check whether two partial solutions are compatible with respect to this information, to make sure they form a valid partial solution to ISOMETRIC PATH COVER.

More formally, for a partial solution of node $v$, we define its *type* by the following information.

* The partial solution on $X_v$ (i.e. the intersection of the $k$ paths with $X_v$).

* For each path $P_i$ and each vertex $y$ of $P_i$ in the partial solution of $X_v$, whether $y$ is an endpoint of $P_i$, has a neighbour in $P_i$ in $G_{<v}$, or in $G_{>v}$ (one can check that there are six distinct possibilities).

* For each path $P_i$, if $P_i$ is not represented in the partial solution, a bit indicating whether $P_i$ has been present in $G_{<v}$ or not (if yes, it can never be used in a future partial solution).

* For each path $P_i$, for each subset $X$ of $X_v$, whether $P_i$ has a vertex $y$ in $G_{<v}$ with $\text{close}(X_v, y) = X$.

* For each path $P_i$, for each subset $X$ of $X_v$, whether $P_i$ has a vertex $y$ in $G_{>v}$ with $\text{close}(X_v, y) = X$.

Note that the number of possible types for a node $v$ is at most $k^{\mathcal{O}(w^2)} \times 6^{kw} \times 2^k \times k^{\mathcal{O}(w)} \times k^{\mathcal{O}(w)}$, which is dominated by $2^{k2^{\mathcal{O}(w)}}$.

We now give more details on how to compute the admissible types of partial solutions for a node of $T$, given that the ones of its children are already computed. The algorithm will consist of computing all tables in a bottom-up manner, and return YES if and only if the root node has an admissible partial solution type. To compute the table of a node, for each possible type, we need only to consider all (pairs of) types of the children nodes, and check their compatibility.

**Leaf node.** For a leaf node $v$, we have $X_v = \{x\}$ for some vertex $x$ of $G$, and the admissible types can easily be computed.

**Introduce node.** Let $v$ be an introduce node with child $v_1$, and $X_v = X_{v_1} \cup \{x\}$ for some vertex $x$ of $G$. Here it suffices to extend the partial solutions in every possible way. To do so, for each possible type for node $v$, we check whether it forms a valid partial solution for the clique $X_v$, and whether it is compatible with some type of the child node. In particular, if $G_{<v}$ is not empty, note that $x$ cannot belong to any set $\text{close}(X_v, y)$ for a vertex $y$ of $G_{<v}$ since $y$ has no edge to any vertex of $G_{<v}$, and thus a shortest path from $x$ to $y$ must go through another vertex of $X_v$. Thus the types where $x$ are in $\text{close}(X_v, y)$ for a vertex $y$ of $G_{<v}$ must be discarded.

**Forget node.** Let $v$ be an introduce node with child $v_1$, and $X_{v_1} = X_v \cup \{x\}$ for some vertex $x$ of $G$. Here, we take the admissible partial solution types of the child and we restrict them to the partial solutions where $x$ is removed. Note that here, we must discard the types where $x$ belongs to $\text{close}(X_v, y)$ for a vertex $y$ of $G_{>v}$ (if $G_{>v}$ is not empty), since $x$ has no edge to any vertex of $G_{>v}$, and thus a shortest path from $x$ to $y$ must go through another vertex of $X_v$.
**Join node.** Let $v$ be an introduce node with children $v_1$ and $v_2$, and $X_{v_1} = X_{v_2} = X_v$. Here, for each possible partial solution type $\tau$ of $v$, we have to check whether it is consistent with some admissible types $\tau_1$ and $\tau_2$ of the two children nodes. First of all, we must only consider such triples which have the same intersection of the solution paths with $X_v$, and the same sets of endpoints of these paths. If in $\tau$, we require a vertex $y$ in $G_{>v}$ with close($X_v, y$) = $S$, then we must either have such a vertex in exactly one of $\tau_1$ (with $G_{>v_1}$) and $\tau_2$ (with $G_{>v_2}$), or in none of them, otherwise the three types are not compatible. Indeed, we have $G_{>v} = G_{>v_1} - G_{<v_2}$ and vice-versa. Similarly, if we require a vertex $y$ in $G_{<v}$ with close($X_v, y$) = $S$, then we must have such a vertex in exactly one of $\tau_1$ (with $G_{>v_1}$) and $\tau_2$ (with $G_{>v_2}$), since $G_{<v} = G_{<v_1} \cup G_{<v_2}$. Similarly, if for a path $P_i$ not represented in $X_v$, we require that $P_i$ has already been present in $G_{<v}$, it must hold for exactly one of $\tau_1$ and $\tau_2$ (not both). Similar facts must hold for the requirements whether each path $P_i$ has a neighbour in $G_{<v}$ or in $G_{>v}$.

**The case of interval graphs.** When the input graph $G$ is an interval graph, the nice tree decomposition of $G$ does not contain any join nodes. Moreover, the linear structure of interval graphs helps us to reduce the time complexity of the dynamic programming algorithm proposed above. Essentially, we shall show that the number of different types associated with a node $v$ is at most $O(2^{k\omega^2})$. We shall use the following lemma.

**Lemma 32.** Let $X$ be a clique cutset of an interval graph $G$. There exists a collection $\mathcal{A}$ of subsets of $X$ of size $O(|X|)$ such that for each vertex $v \in V(G)$, if $v$ is close to $A$ with respect to $X$, then $\text{close}(X, v) \in \mathcal{A}$.

*Proof.* If $v \in X$, then $A = \{v\}$. Without loss of generality, assume now that $\min(v) < \min(X)$ (where $\min(v)$ denotes the left endpoint of the interval associated to $v$, and $\min(X)$, the leftmost left endpoint of an interval of $X$). If $u \in X$ such that $d(v, u) = d$, then for every $w \in X$ such that $\min(w) \le \min(u)$, $d(v, w) \le d$. Indeed, take a shortest path from $v$ to $u$ and let $z$ be the neighbour of $u$ in this path. Then, $z$ is also a neighbour of $w$. This implies that $\text{close}(X, v)$ is one of the following sets: $\bigcup_{u \in X} \{\{w \in X | \min(w) \le \min(u)\}\}$. Hence,

$$ \mathcal{A} = \bigcup_{u \in X} \{\{w \in X | \min(w) \le \min(u)\}, \{w \in X | \max(w) \ge \max(u)\}, \{u\}\} $$

Observe that $|\mathcal{A}|$ is $O(|X|)$. $\square$

The above lemma implies that for an interval graph, the set of partial solutions is $2^{O(k\omega^2)}$ for interval graphs. This proves the statement of Theorem 3 for interval graphs.

# 5 Conclusion

We have studied the problem ISOMETRIC PATH COVER in many subclasses of graphs of bounded tree-length. Our main contribution is a polynomial-time algorithm to solve the problem, that provides a constant-factor approximation on a very large class of graphs. Note that our algorithm is not a constant-factor approximation in general. Indeed, it was proved that the hypercube $H_d$ on $n = 2^d$ vertices can be covered with $\frac{2^d}{d+1}$ isometric paths whenever $d+1$ is a power of 2 [14]. However, on this graph, our algorithm would return a solution of size $\binom{d}{\lfloor d/2 \rfloor}$ by Sperner's lemma, which is $\Theta(\frac{2^d}{\sqrt{d}})$ using Stirling's approximation. Thus, our algorithm cannot have a better approximation ratio than $\sqrt{\log n}$ on general graphs of order $n$.

It remains an interesting open question whether, for general graphs, there exists a polynomial-time constant-factor approximation algorithm for ISOMETRIC PATH COVER, and whether ISOMETRIC PATH COVER is FPT for solution size or treewidth. We also leave the complexity of ISOMETRIC PATH COVER on interval graphs open. As these questions are all answered in the negative for the related problem GEODETIC SET [6, 20], possibly the same holds for ISOMETRIC PATH COVER as well. Other interesting
classes on which to study ISOMETRIC PATH COVER, and which seem challenging, can be found in Figure 1, for example split graphs or proper interval graphs.

We remark that ISOMETRIC PATH COVER remains NP-hard on *apex graphs*, i.e. graphs which can be made planar by the removal of just one vertex. Indeed, the construction used to prove Theorem 1 can be used to reduce from INDUCED $P_3$-PARTITION on subcubic grid graphs (a special subclass of planar graphs), which is NP-hard [31]. However, the complexity of ISOMETRIC PATH COVER on planar graphs remains unknown.

Finally, we remark that some of our results also hold for the *partition* version of ISOMETRIC PATH COVER, called ISOMETRIC PATH PARTITION [23], where the isometric paths must be pairwise vertex-disjoint. This is the case for our NP-hardness proof for chordal graphs (indeed all considered isometric path covers are in fact isometric path partitions), and the FPT algorithm for treewidth (indeed it is not difficult to include in the constraints the fact that the paths must form a partition). However, our approximation algorithm does not return a feasible solution for ISOMETRIC PATH PARTITION, since in general it can produce overlapping isometric paths.

**Acknowledgements.** We thank Vincent Limouzy, Joydeep Mukherjee, Lucas Pastor and Jean-Florent Raymond for initial discussions on the topic of this paper.

## References

[1] I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. *SIAM Journal on Computing*, 48(3):1120–1145, 2019.

[2] M. Aigner and M. Fromme. A game of cops and robbers. *Discrete Applied Mathematics*, 8(1):1–12, 1984.

[3] G. Andreatta and F. Mason. Path covering problems and testing of printed circuits. *Discrete Applied Mathematics*, 62(1-3):5–13, 1995.

[4] R. Belmonte, P. A. Golovach, P. Heggernes, P. van't Hof, M. Kamiński, and D. Paulusma. Detecting fixed patterns in chordal graphs in polynomial time. *Algorithmica*, 69(3):501–521, 2014.

[5] M. Cáceres, M. Cairo, B. Mumey, R. Rizzi, and A. I. Tomescu. Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time. In *Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022*, pages 359–376. SIAM, 2022.

[6] D. Chakraborty, S. Das, F. Foucaud, H. Gahlawat, D. Lajou, and B. Roy. Algorithms and complexity for geodetic sets on planar and chordal graphs. In *Proceedings of the 31st International Symposium on Algorithms and Computation, ISAAC 2020*, volume 181 of *LIPIcs*, pages 7:1–7:15, 2020.

[7] D. G. Corneil, S. Olariu, and L. Stewart. Computing a dominating pair in an asteroidal triple-free graph in linear time. In *Workshop on Algorithms and Data Structures*, pages 358–368. Springer, 1995.

[8] T. Davot, L. Isenmann, and J. Thiebaut. On the approximation hardness of geodetic set and its variants. In *Proceedings of the 27th International Computing and Combinatorics Conference, COCOON 2021*, volume 13025 of *Lecture Notes in Computer Science*, pages 76–88. Springer, 2021.

[9] R. P. Dilworth. A decomposition theorem for partially ordered sets. *Annals of Mathematics*, 51(1):161–166, 1950.

[10] Y. Dourisboure and C. Gavoille. Tree-decompositions with bags of small diameter. *Discrete Mathematics*, 307(16):2008–2029, 2007.
[11] V. Dujmović, G. Joret, P. Micek, P. Morin, T. Ueckerdt, and D. R. Wood. Planar graphs have bounded queue-number. *Journal of the ACM (JACM)*, 67(4):1–38, 2020.

[12] M. Dumas, F. Foucaud, A. Perez, and I. Todinca. On graphs coverable by *k* shortest paths. In *Proceedings of the 33rd International Symposium on Algorithms and Computation, ISAAC 2022*, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.

[13] D. C. Fisher and S. L. Fitzpatrick. The isometric number of a graph. *Journal of Combinatorial Mathematics and Combinatorial Computing*, 38(1):97–110, 2001.

[14] S. L. Fitzpatrick, R. J. Nowakowski, D. A. Holton, and I. Gaines. Covering hypercubes by isometric paths. *Discrete Mathematics*, 240(1-3):253–260, 2001.

[15] D. Fulkerson and O. Gross. Incidence matrices and interval graphs. *Pacific journal of mathematics*, 15(3):835–855, 1965.

[16] D. R. Fulkerson. Note on dilworth's decomposition theorem for partially ordered sets. *Proceedings of the American Mathematical Society*, 7:701–702, 1956.

[17] C. Gavoille, M. Katz, N. A. Katz, C. Paul, and D. Peleg. Approximate distance labeling schemes. In *ESA*, pages 476–487. Springer, 2001.

[18] J. Guo, R. Niedermeier, and J. Uhlmann. Two fixed-parameter algorithms for vertex covering by paths on trees. *Information Processing Letters*, 106(2):81–86, 2008.

[19] P. Heggernes, D. Meister, and C. Papadopoulos. A new representation of proper interval graphs with an application to clique-width. *Electronic Notes in Discrete Mathematics*, 32:27–34, 2009.

[20] L. Kellerhals and T. Koana. Parameterized complexity of geodetic set. In *IPEC*, volume 180, pages 20:1–20:14.

[21] C. V. G. C. Lima, V. F. dos Santos, J. H. G. Sousa, and S. A. Urrutia. On the computational complexity of the strong geodetic recognition problem, 2022.

[22] W. Lochet. A polynomial time algorithm for the *k*-disjoint shortest paths problem. In *SODA*, pages 169–178, 2021.

[23] P. D. Manuel. On the isometric path partition problem. *Discussiones Mathematicae: Graph Theory*, 41(4):1077–1089, 2021.

[24] P. D. Manuel, S. Klavžar, A. Xavier, A. Arokiaraj, and E. Thomas. Strong geodetic problem in networks. *Discussiones Mathematicae Graph Theory*, 40(1):307–321, 2018.

[25] A. Mohammed and F. F. Dragan. Slimness of graphs. *Discrete Mathematics & Theoretical Computer Science*, 21, 2019.

[26] Simeon C. Ntafos and S. Louis Hakimi. On path cover problems in digraphs and applications to program testing. *IEEE Transactions on Software Engineering*, SE-5(5):520–529, 1979.

[27] J. Pan and G. J. Chang. Isometric-path numbers of block graphs. *Information processing letters*, 93(2):99–102, 2005.

[28] J. Pan and G. J. Chang. Isometric path numbers of graphs. *Discrete mathematics*, 306(17):2091–2096, 2006.

[29] N. Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. *Journal of Combinatorial Theory, Series B*, 63(1):65–110, 1995.
[30] M. Thiessen and T. Gaertner. Active learning of convex halfspaces on graphs. In *Proceedings of the 35th Conference on Neural Information Processing Systems, NeurIPS 2021*, volume 34, pages 23413–23425. Curran Associates, Inc., 2021.

[31] R. van Bevern, R. Bredereck, L. Bulteau, J. Chen, V. Froese, R. Niedermeier, and G. J. Woeginger. Partitioning perfect graphs into stars. *Journal of Graph Theory*, 85(2):297–335, 2017.