# 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. 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Dec 2022, Seoul, France. pp.12:1–12:17, 10.4230/LIPIcs.ISAAC.2022.12 . hal-03899912

HAL Id: hal-03899912

https://hal.science/hal-03899912

Submitted on 6 Mar 2023

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**

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

**Antoine Dailly 🏠**

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

G-SCOP, Univ. Grenoble-Alpes, Grenoble, France

**Sandip Das**

Indian Statistical Institute, Kolkata, India

**Florent Foucaud 📷 🏠 🌐**

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

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

Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France

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

**Harmender Gahlawat 📷 🏠 🌐**

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

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

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

Ben-Gurion University of the Negev, Beer-Sheva, Israel

Indian Statistical Institute, Kolkata, India

**Subir Kumar Ghosh**

Ramakrishna Mission Vivekananda Educational and Research Institute, Kolkata, India

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

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms

**Keywords and phrases** Shortest paths, Isometric path cover, Chordal graph, Interval graph, AT-free graph, Approximation algorithm, FPT algorithm, Treewidth, Chordality, Treelength

**Digital Object Identifier** 10.4230/LIPIcs.ISAAC.2022.46

**Related Version** Full Version: https://hal.archives-ouvertes.fr/hal-03710812

**Funding** This research was financed by the IFCAM project "Applications of graph homomorphisms" (MA/IFCAM/18/39).

**Florent Foucaud:** This author was financed by the ANR project GRALMECO (ANR-21-CE48-0004) and the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25).

**Harmender Gahlawat:** This author was financed by the ISF grant no. 1176/18.

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

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

© D. Chakraborty, A. Dailly, S. Das, F. Foucaud, H. Gahlawat, and S. Ghosh; licensed under Creative Commons License CC-BY 4.0

33rd International Symposium on Algorithms and Computation (ISAAC 2022).

Editors: Sang Won Bae and Heejin Park; Article No. 46; pp. 46:1–46:17

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

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# 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].

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].
<figure><img src="image_10.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. For all shown graph classes, ISOMETRIC PATH COVER is constant-factor approximable in polynomial time.</figcaption></figure>

**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 subset *X*<sub>*v*</sub> of *V*(*G*) called *bag*, such that: (i) $\bigcup_{v \in V(T)} X_v = V(G)$, (ii) for each edge *xy* ∈ *E*(*G*), there exists a bag *X*<sub>*v*</sub> such that $\{x, y\} \subseteq X_v$, and (iii) for every vertex *x* ∈ *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 result, 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^{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<sub>3</sub>-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<sub>3</sub>-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 ≥ 1. Let G' be the graph whose vertex set is V(G') = V(G) ∪ {u, v, w}, where u, v, w are three new vertices. The edge set of G' is E(G') = E(G) ∪ {(u, v), (v, w)} ∪ {(v, x) | x ∈ 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<sub>3</sub>-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 \{(u, v, w)\}$ 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. ◀

Now consider the set $\mathcal{C}' = \mathcal{C} \setminus \{P\}$ where $P \in \mathcal{C}$ that covers both u and w. Observe that $\mathcal{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 $\mathcal{C}'$ is a partition of $V(G)$, and therefore G is a yes-instance of INDUCED P<sub>3</sub>-PARTITION. ◀

**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
■ Algorithm 1 An algorithm for ISOMETRIC PATH COVER

Input : A graph G and a vertex v ∈ V (G).

Output : An isometric path cover of G.

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

2 $\mathcal{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 $\mathcal{P}_v$ by removing all orientations.

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 ∈ V (G), two vertices x, y ∈ 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 \{ \beta(\vec{G}_r) : r \in V(G) \} $$

► **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:

$$ \text{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:

$$ \text{ipacc}(G) = \min \{ \text{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(\overrightarrow{G_r})$. Then, by Observation 7, we have that $|\mathcal{P}| \le \beta(\overrightarrow{G_r}) = \beta(G)$. Now, let $r'$ be a vertex of $G$ such that $ipacc(G) = ipacc(\overrightarrow{G_{r'}})$. Since any isometric path in $\mathcal{P}$ contains at most $ipacc(\overrightarrow{G_{r'}})$ many elements of $\beta(\overrightarrow{G_{r'}})$, we have $\frac{\beta(\overrightarrow{G_{r'}})}{ipacc(\overrightarrow{G_{r'}})} \le |\mathcal{P}|$. Finally, since $\beta(G) \le \beta(\overrightarrow{G_{r'}})$, we have $\frac{\beta(G)}{ipacc(G)} \le |\mathcal{P}|$. ◀

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

We now 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 $\overrightarrow{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 $\overrightarrow{ab} \in E_1$, $d(r, a) = d(r, b) + 1$. Let the vertices of the largest antichain set of $P$ in $\overrightarrow{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 $\overrightarrow{b_ic_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_ic_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$. ◀

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 $\overrightarrow{G_r}$. Then $\Delta_r(G) \ge [\frac{\alpha}{2}] - 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 \lceil \frac{\alpha}{2} \rceil - 1$. ◀

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$. ◀

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 $\mathrm{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. ◀

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 $\bar{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 \lfloor \frac{k+8}{2} \rfloor - 1 \ge \frac{k}{2} + 3$, and $a,b$ lie in the same cluster with respect to $r$. This contradicts Proposition 17. ◀

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}]$. ◀

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

► **Lemma 20.** If a graph $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.** For any interval graph $G$, we have $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. ◀

Any proper interval graph $G$ has a vertex $v$ such that the spanning tree $\mathcal{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$.

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.
**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.

◀

**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.

◀

**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 $\vec{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 $\vec{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 26. $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})$.
<figure><img src="image_11.png" /><figcaption>Figure 2 Proof of Claim 26. Path $P'$ is dotted, and path $P_j$ is red.</figcaption></figure>

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_jq \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 26, 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) $$

Observe 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 that $d(u, v) \le d(u, x_u) + d(x_u, x_v) + d(x_v, v)$ with Equations 1-3, we get $d(x_u, x_v) \ge 4$. Thus, $\Delta_r(G) \ge 4$, contradicting Proposition 17. This completes the proof. ◀
<figure><img src="image_12.png" /><figcaption>Figure 3 A tight-approximation example for chordal graphs</figcaption></figure>

## 3.3 Proof of Theorem 2 and tightness of our analysis

We now complete the proof of Theorem 2. Recall that Algorithm 1 takes as input a graph $G$ and a vertex $v$ and 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 $\mathcal{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 $\text{OPT}$ be a minimum cardinality isometric path cover of $G$. Due to Lemma 10, we have $|\mathcal{P}_v| \le |\mathcal{A}| \le 2|\text{OPT}|$. This completes the proof.

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).

In the following observations, we show that our analysis of Algorithm 1 is essentially tight for proper interval graphs, interval graphs and chordal graphs.

**► Observation 27.** 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\} \cup \bigcup_{i \in [\ell]} Q_i \cup \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
<figure><img src="image_13.png" /><figcaption>Figure 4 A tight-approximation example for interval graphs</figcaption></figure>

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$. ◀

**Observation 28.** 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 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$. ◀

**Observation 29.** 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$. ◀

# 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.

We will use *nice tree decompositions*, a well-known tool for designing dynamic programming algorithms for graphs of bounded treewidth, that can be constructed optimally in linear time on chordal graphs, see [4, Section 4].

**► Definition 30.** 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 31.** 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. The number of types will be 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 (due to space constraints, the proof is omitted: see the full version of the paper).
**► Lemma 32.** 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 close$(X, y)$.

Thus, following Lemma 32, 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 close$(X_v, y) = X$ in the previously computed partial solutions that can lead to the current partial solution. We will also keep track of 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 32, 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.

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 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 close$(X_v, y) = X$.

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

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. We give all details in the full version.

# 5 Conclusion

We have studied the problem ISOMETRIC PATH COVER in many subclasses of graphs of bounded treelength. 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. 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. 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.

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 that the paths must form a partition). However, our approximation algorithm does not return a feasible solution for ISOMETRIC PATH PARTITION, since it can produce overlapping paths.
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. URL: https://arxiv.org/abs/ 2208.01796, doi:10.48550/ARXIV.2208.01796.

22 W. Lochet. A polynomial time algorithm for the *k*-disjoint shortest paths problem. In *SODA*, pages 169–178, 2021. doi:10.1137/1.9781611976465.12.

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. URL: https://proceedings.neurips.cc/ paper/2021/file/c4bf1e24f3e6f92ca9dfd9a7a1a1049c-Paper.pdf.

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.