{'fraction_non_alphanumeric': 0.0461152529657242, 'fraction_numerical': 0.007596005064003376, 'mean_word_length': 3.623347062649035, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fixed-parameter tractable algorithms for Tracking Shortest Paths

We consider the parameterized complexity of the problem of tracking shortest s-t paths in graphs, motivated by applications in security and wireless networks. Given an undirected and unweighted graph with a source s and a destination t, Tracking Shortest Paths asks if there exists a k-sized subset of vertices (referred to as tracking set) that intersects each shortest s-t path in a distinct set of vertices. We first generalize this problem for set systems, namely Tracking Set System, where given a family of subsets of a universe, we are required to find a subset of elements from the universe that has a unique intersection with each set in the family. Tracking Set System is shown to be fixed-parameter tractable due to its relation with a known problem, Test Cover. By a reduction to the well-studied d-hitting set problem, we give a polynomial (with respect to k) kernel for the case when the set sizes are bounded by d. This also helps solving Tracking Shortest Paths when the input graph diameter is bounded by d. While the results for Tracking Set System help to show that Tracking Shortest Paths is fixed-parameter tractable, we also give an independent algorithm by using some preprocessing rules, resulting in an improved running time.


Introduction and Motivation
In this paper, we consider the parameterized complexity of the problem of tracking shortest s-t paths in graphs and some related versions of the problem.
Given a graph with a specified source s and a destination t, a simple path between s and t is referred to as an s-t path, and a shortest simple path between s and t is referred to as a shortest s-t path. In Tracking Shortest Paths problems, the goal is to find a small subset of vertices that can help uniquely identify all shortest s-t paths in a graph.
We start with some motivation for the problem. Consider the security system at a large airport. As a security measure it is required to identify the route taken by passengers across the airport from entry to departure or from arrival to exit.
A set of carefully chosen security scan points can be selected as identification points to trace the movement of passengers. A similar scenario can arise in any other secure facility where movement of entities need to be tracked. Note that in practical scenarios, often it is resourceful to use the shortest s-t paths available.
Other major application scenarios are tracking of moving objects in telecommunication networks and road networks. The goal can be efficient and optimized tracking of objects, for the purpose of surveillance, monitoring, intruder detection, and operations management. The solution to the problem can then be used for reconstruction of path traced by an object in order to detect potential network flaws, to study traffic patterns of moving objects, to optimize network resources based on such patterns, and for other such network analysis based tasks.
Tracking of moving objects has been studied in the field of wireless sensor networks. See [2] for a survey of target tracking protocols using wireless sensor networks. Some researchers have studied this with respect to power management of sensors [3]. Despite being an active area of research, a major part of this research so far has been based on heuristics. In [4], the authors formalized the problem of tracking in networks as a graph theoretic problem and did a systematic study. Among other problems, they introduced the following optimization problem. V (P ) is used to denote the set of vertices in path P . A graph with a unique source s and unique destination t is called an s-t graph.

Tracking Shortest Paths
Input: An undirected s-t graph G = (V, E).
Output: A minimum set of vertices T ⊆ V , such that for any two distinct shortest s-t paths P 1 and P 2 in G, it holds that T ∩ V (P 1 ) = T ∩ V (P 2 ).
The output set of vertices is referred to as a tracking set and the vertices in a tracking set are called trackers. In [4], Tracking Shortest Paths was shown to be NP-hard for undirected graphs and a 2-approximate algorithm was given for the case of planar graphs. An α-approximation algorithm for a minimization problem gives a solution that is at most α times the size of an optimum solution, in time polynomial in the input size.
Tracking Shortest Paths can be generalized to the case where not just the shortest s-t paths, but all s-t paths in a graph need to be identified uniquely by a minimum subset of vertices. For a set of vertices T ⊆ V and a path P , Π P (T ) denotes the sequence in which the vertices from V (P )∩T appear in path P . Formally the problem of tracking all s-t paths in a graph is defined as follows

Tracking Paths
Input: An s-t graph G = (V, E).
Output: A minimum set of vertices T ⊆ V , such that for any two distinct s-t paths P 1 and P 2 in G, it holds that Π P1 (T ) = Π P2 (T ).
For a graph G, solving Tracking Paths requires finding a tracking set that intersects all s-t paths in a unique sequence. Note that if we consider only shortest s-t paths, a pair of vertices cannot appear in different sequence in two distinct shortest s-t paths, as this would mean that at least one of the paths is not a shortest s-t path in the graph. Hence in case of Tracking Shortest Paths, it is sufficient to find a tracking set that intersects each shortest s-t path in a unique set of vertices.
It has been proven that Tracking Paths is NP-hard for undirected graphs, and admits a polynomial kernel when parameterized by k, the size of the tracking set [5]. In parameterized complexity, a (polynomial) kernel is an equivalent instance whose size is a (polynomial) function of a parameter k, where k is either the size of output or some other integer related to the input instance such that k is preferably very small compared to the input size. See Section 2.1 for details on FPT and kernels.
Observe that for a graph G, a tracking set for all s-t paths is also a tracking set for all shortest s-t paths. However, it may be the case that G does not have a tracking set of size at most k for all s-t paths, but it might still have a tracking set of size at most k for all shortest s-t paths. Hence the parameterized complexity of Tracking Shortest Paths is a problem of independent interest.
The key idea behind the kernel for Tracking Paths in [5] originates from the fact that for an undirected graph G, a tracking set for all s-t paths is also a feedback vertex set (FVS) for G. A feedback vertex set for a graph G is a set of vertices whose removal makes G acyclic. However, a tracking set for all shortest s-t paths in a graph need not be a FVS. In this paper we address the parameterized complexity of Tracking Shortest Paths along with its restricted version diam-d-Tracking Shortest Paths. diam-d-Tracking Shortest Paths requires finding a tracking set for distinguishing between shortest s-t paths in a graph whose diameter is restricted to d. We show that diam-d-Tracking Shortest Paths is NP-hard and FPT.
We first study a combinatorial version of Tracking Shortest Paths, which is Tracking Set System, in Section 3. A set system is a pair P = {X, S}, where X is a finite set and S is a family of subsets of X. For a set system, a tracking set is a set of elements that has a unique intersection with each of the subsets in the family. Tracking Set System is formally defined as follows.

Tracking Set System
Input: A set system P = {X, S}.
Output: A minimum cardinality set T ⊆ X, such that for any two distinct Here the elements in a tracking set are referred as trackers.
Tracking Set System has some resemblance to the well known Hitting Set problem. For a set system (U, F ) comprising of a finite universe U and a collection F of subsets of U , a hitting set is a set H ⊆ U that has a non-empty intersection with each set in F , and the optimization version of Hitting Set requires finding a minimum cardinality hitting set. Observe that while hitting set is a set of elements that is required to have a non-empty intersection with each of the sets in the set system family, a tracking set is required to have a unique intersection with each of the sets in the family. Hitting Set was one of Karp's original NP-complete problems [6].
We first study d-Tracking Set, which is a restricted version of Tracking Set System where the size of subsets in the family is restricted to d. We show d-Tracking Set to be NP-hard by showing a correlation with the problems Identifying Vertex Cover and Packing [7], [8]. We then give a compression for d-Tracking Set by showing a reduction from d-Tracking Set to the d-Hitting Set problem. d-Hitting Set is a restricted version of Hitting Set where the set sizes in the family are restricted to d. Compression of a parameterized problem X into a problem Y is an algorithm that takes as input an instance (x, k) of X, works in time polynomial in |x| + k, and returns a problem instance y, such that |y| ≤ p(k) for some polynomial p(·), and, y Tracking Set System is known to be related to Test Cover [10]. Test Cover requires finding a subfamily of sets in a set system, that can help identify each element in the universe uniquely by inclusion. Using known results about Test Cover [11], we show that the size of a tracking set for a set system with n elements and m sets is at least ⌈lg m⌉ 1 . This, along with some reduction rules, leads to the result that the problem of determining whether a given set system has a tracking set of size at most k has a FPT algorithm running in time We then consider other natural parameterizations of Tracking Set System and give FPT algorithms and hardness results that follow from the equivalence to Test Cover.
In Section 4, we consider the parameterized complexity of Tracking Shortest Paths problems. We study Tracking Shortest Paths along with a restricted version of it i.e. diam-d-Tracking Shortest Paths problem. diamd-Tracking Shortest Paths requires finding a tracking set for shortest s-t paths when the input graph has diameter at most d. Using results from Section 3 and [4], we first prove that both these problems are NP-hard and admit FPT 1 We use lg to denote logarithm to the base 2 2 O * notation ignores the polynomial factors in terms of the size of input n algorithms. Then in Section 4.2, we introduce the Tracking Paths in DAGs problem which requires finding a tracking set for all (directed) s-t paths in a directed acyclic graph (DAG). We give an improved fixed-parameter tractable algorithm for Tracking Shortest Paths by first reducing it to Tracking Paths in DAGs, and then giving a kernel for Tracking Paths in DAGs.
The following table gives a summary of our results in this paper.

Problem
Kernel FPT Section Tracking Paths in DAGs O(2 2k+4 ) O * (2 2k 2 +4k ) 4.2 Polynomial indicates polynomial in k for a fixed d, and c is a function polynomial with respect to d.

Related Work
Tracking Set System has been studied earlier under the problem name Distinguishing Transversals in Hypergraphs [12]. Some closely related graph theoretic problems are Discriminating Code [13] and Identifying Codes [14], [15], [16]. Distinguishing Transversals when restricted to 2uniform hypergraphs is equivalent to Identifying Vertex Cover, which is the problem of finding a set of vertices V ′ ⊆ V for a graph G = (V, E), such that a ∩ V ′ = b ∩ V ′ , for a pair of distinct edges a, b ∈ E. Henning and Yeo give some bounds for the size of an output in [7] and [12] for Identifying Vertex Cover and Distinguishing Transversal, respectively.
Recently Eppstein et al. proved Tracking Paths in planar graphs to be NP-hard and gave a 4-approximation algorithm for the same.

Preliminaries
Throughout this paper, we assume that each graph is an s-t graph with s and t already given to us. V (G) denotes the vertex set of graph G and E(G) denotes the edges whose both endpoints belong to V (G). We use DAG to denote directed acyclic graph. For vertices u, v ∈ V (G) where G is an undirected graph, uv ∈ E(G) denotes an edge between vertices u and v. For vertices a, b ∈ V (G) where G is directed graph, (a, b) ∈ E(G) denotes an edge between vertices a and b, oriented from a towards b. Given a graph G = (V, E), G − e denotes the graph induced by removing the edge e ∈ E from G, i.e.
The degree of a vertex v is denoted by deg(v) = |N (v)|. In a directed graph G, . Short-circuiting a vertex of degree two means deleting the vertex and introducing an edge between its neighbors.
A path is a sequence of vertices. We only consider simple paths in this paper i.e. paths that do not repeat vertices. V (P ) is used to denote the vertex set of path P . For vertices a, b ∈ V , an a-b path means a path between vertices a and b.
If there exists a path P 1 between vertices u and v, and there exists another path P 2 between vertices v and w, we use P 1 · P 2 to denote the path between u and w obtained by concatenation of paths P 1 and P 2 at v. The distance between two vertices x, y ∈ V (G), denoted by dis(x, y), is the length of the shortest x-y path in G. Length of a path is equal to the number of edges in that path. The greatest distance between any two vertices in G is the diameter of G, denoted by diam(G).
We use the term unrestricted as an attribute for a problem when there are no restrictions on the input.

Fixed-parameter tractability
there exists an algorithm A (called a fixed-parameter algorithm), a computable function f : N → N, and a constant c such that, given ( The complexity class containing all fixed-parameter tractable problems is called FPT. There is also an associated hardness hierarchy and the basic hardness classes are W [1] and W [2]. The clique problem (does the given graph have a clique of size at least k ?) is a canonical complete problem for W [1] while the dominating set problem (does the given graph have a dominating set of size at most k?) is a canonical complete problem for W [2]. We refer to [9] for more details on parameterized complexity.
Let A, B ⊆ Σ * × N be two parameterized problems. A parameterized reduction from A to B is an algorithm that, given an instance (x, k) of A, outputs an for a computable function g, and 3. the running time of algorithm is f (k) · |x| O(1) for a computable function f .
A polynomial compression of a parameterized language Q ⊆ Σ × N into a language R ⊆ Σ * is an algorithm that takes as input an instance (x, k) ∈ Σ * × N, works in polynomial time in |x| + k, and returns a string y such that: A kernelization algorithm is a polynomial-time algorithm that transforms an arbitrary instance of the problem to an equivalent instance (known as kernel) of the same problem, such that the size of the new instance is bounded by some computable function g of the parameter of the original instance. Kernelization typically involves applying a set of rules (called reduction rules) to the given instance. A reduction rule is a rule that translates a given instance into another.
The rule is said to be safe if the reduced instance is equivalent to the original instance in the sense that the reduced instance is an YES instance if and only if the original instance is an YES instance. Unless otherwise specified, we use polynomial time, to denote a running time that is a polynomial function of the input size.

Tracking Set Systems
In this section we study generalized versions of the Tracking Shortest Paths problem. In Tracking Set System problems, the input is a set system, and we aim to find a subset of elements from the universe that uniquely intersects all sets in the family. For a set system P = {X, S}, a tracking set is a subset of elements T ⊆ X, that has a unique intersection with each set in the family S i.e.
. For the remainder of this section, unless otherwise specified, by tracking set we mean tracking set for set systems.
We first consider a restricted version of Tracking Set System wherein the size of the sets in family S is limited to d, which is referred as d-Tracking Set.

d-Tracking Set
In this section we give a kernel and an FPT algorithm for a restricted version of Tracking Set System wherein the size of each set in the family is restricted to d. We formally define the problem as follows.
When d = 2, d-Tracking Set is the same as Identifying Vertex Cover [7].
It is known that Identifying Vertex Cover is related to Packing, which involves finding a maximum set of disjoint packing of paths of length at least four in a graph [16]. Packing is formally defined as follows.
Packing(G, k) Output: A maximum cardinality set P of paths of length at least four, such that for any two distinct paths P 1 , P 2 ∈ P, it holds that V (P 1 ) ∩ V (P 2 ) = ∅, It is known from [8] that Packing is NP-hard, and it is known that there exists a polynomial time reduction from Packing to Identifying Vertex Cover [7]. Hence we have the following lemma.  Proof. Let P 1 = (X, S, d, k) be an instance of d-Tracking Set. We construct an instance P 2 = (U, F , 2d, k) of d-Hitting Set as follows. Set U = X, and the family consists of the symmetric difference of every pair of sets in S. First we prove that if T is a tracking set for P 1 then T is a hitting set for P 2 . Suppose not. Then there exists a set F ∈ F such that T ∩ F = ∅. Due to the construction of P 2 , there exist two sets, say R, S ∈ S, such that which implies that T ∩ R = T ∩ S. This contradicts the assumption that T is a tracking set for P 1 .
Next we prove that if H is a hitting set for P 2 then H is a tracking set for This contradicts the assumption that H is a hitting set for P 2 . Hence the lemma holds.
It is known that d-Hitting Set admits a kernel with O((2d − 1)k d−1 + k) [18]. Due to this fact and Lemma 3, we have the following lemma.

Tracking Set for Set Systems
Although d-Hitting Set is FPT, the general hitting set problem is W[2]hard [19]. Thus if we consider the unrestricted version of Tracking Set Sys-tem, it does not help to reduce it to the hitting set problem. Hence we consider a different problem for analysis of Tracking Set System, which is the Test Cover problem.
We refer to an instance of the Tracking Set System as an (x, y) instance if the size of the universe (element set) is x and the size of the family is y.
In Test Cover we are given a set of elements M = {1, 2, . . . n}, called vertices and a family T = {T 1 , T 2 , . . . , T m } of distinct subsets of M called tests.
We say that a test T separates a pair i, is called a test cover if for every pair of distinct vertices i, j ∈ M , there exists a test T ∈ T ′ that separates them. Test Cover requires finding a minimum size test cover if there exists one.
Test Cover is a well studied problem [20,21]. It is known that Test Cover is NP-hard and APX-hard [22]. There exists an O(log n)-approximation algorithm for the problem [23] and there is no o(log n)-approximation algorithm unless P = N P [22]. The parameterized complexity of Test Cover has also been studied extensively [24,11,25]. Given (M, T ), and k ∈ N ∪ {0}, the parameterized version of Test Cover asks if there exists a test cover of size at most k.
For n elements and a family of m tests, lg n is a lower bound for the size of test cover (Theorem 2(i)), and, n and m are upper bounds for the size of test cover [26], [25]. Given lower and upper bounds of solution size, it is a natural question to ask if there exists an FPT algorithm on a parameter k which determines whether there exists a solution of size k greater than the lower bound or k less than the upper bound. Parameterizations of NP-optimization problems above or below their guaranteed lower/upper bounds are well studied parameterizations [27], [28], [29].
Some results by Crowston et al. [11] on Test Cover have been summarized in the following theorem. Test Cover is known to be a dual of Tracking Set System [10], as explained in the following lemmas.

Tracking Set for Paths in Graphs
In this section, we provide FPT algorithms for Tracking Shortest Paths problems in graphs. In Tracking Shortest Paths, the input is a graph G with a unique source s ∈ V (G) and a unique destination t ∈ V (G), and the required output is a tracking set, T ⊆ V , whose intersection with the vertex set of each s-t path is unique. The first problem we consider is diam-d-Tracking Shortest Paths where the input graph has diameter d, and then we tackle the general Tracking Shortest Paths problem.

Tracking Shortest Paths in diameter d graphs
In this section we give a kernel and an FPT algorithm for a special case of Tracking Shortest Paths where we consider those graphs whose diameter is at most d.
diam-d-Tracking Shortest Paths involves finding a tracking set i.e. a subset of vertices from V (G), that distinguishes all shortest s-t paths when the input graph has diameter restricted to d. We define the problem formally as follows.

diam-d-Tracking Shortest Paths
Input: An s-t graph G with diam(G) ≤ d, and an integer k. Banik et al. [4] proved that Tracking Shortest Paths is NP-hard when the length of shortest paths is greater than or equal to three. Note that here the graph diameter is greater than or equal to three and dis(s, t) ≥ 3. Hence we have the following corollary.

Corollary 3. diam-d-Tracking
Shortest Paths is NP-hard when d ≥ 3 for a fixed d.

Next we give a polynomial kernel and FPT algorithm for diam-d-Tracking
Shortest Paths by reducing it to d-Tracking Set. We start by giving the following Reduction Rule that is similar to Reduction Rule 1, and ensures that each vertex and edge in the input graph participates in an shortest s-t path.

Reduction Rule 1. If there exists a vertex or an edge in G that does not
participate in any shortest s-t path, delete it.

Lemma 7. Reduction Rule 1 is safe and can be applied in polynomial time.
Proof. Let G = (V, E) be a graph, where |V | = n and |E| = m. If a vertex or an edge does not participate in any shortest s-t path in G, it cannot play a role in tracking shortest s-t paths in G. To implement the rule, we first find the distance between s and t in G, using a breadth first search (BFS). Let l be the length of a shortest s-t path in G. Now for each edge e = ab ∈ E, we check if, dis(s, a) + dis(b, t) + 1 = l or dis(s, b) + dis(a, t) + 1 = l.
If above condition is not satisfied, then we remove the edge e from G. This step takes O(m(n + m)) time. After above step, we also remove all isolated vertices from G, in O(n) time.
The main challenge in solving diam-d-Tracking Shortest Paths using d-Tracking Set is that while the sets that need to be distinguished, are received as a part of the input in Tracking Set System, while the shortest s-t paths, which need to be distinguished, are implicit in the input for Tracking Shortest Paths. Thus, we need a procedure to procure the family of shortest s-t paths from G for solving Tracking Shortest Paths.
Although for a general graph, counting the number of s-t paths is hard for the complexity class #P [30], for some special class of graphs it can be done in polynomial time. Particularly counting shortest s-t paths for a graph can be done in polynomial time O(m + n) as explained below.
In order to construct the set system (U, F ) we first define level L(v) of a vertex v ∈ V (G) as the length of the shortest path from s to v. After application of Reduction Rule 1, there does not exist an edge between vertices equidistant from s (or t). In fact, the end points of each edge are such that the difference between their distances from s (or t) is always exactly one. Thus the vertices of the graph can be categorized into layers, such that each layer consists of the vertices equidistant from s (or t). Such a graph is called a layered s-t graph.
Next we have the following observation that helps to enumerate all shortest s-t paths in a layered s-t graph. Next we give a lemma that gives a reduction from diam-d-Tracking Shortest Paths to d-Tracking Set.

Then there exists an instance
Proof. We create an instance (X, S, d ′ , k ′ ) of d-Tracking Set from G as follows.
We introduce an element in X for each vertex in G. The vertex set of each shortest s-t path in G forms a set in the family S. We can construct the family S using Observation 1. Let d ′ = dis(s, t). Since diam(G) = d, the length of a shortest s-t path in G will be less than or equal to d, i.e. d ′ ≤ d. We claim that there exists a tracking set of size k in G if and only if there exists a tracking set of size k ′ = k for (X, S, d ′ , k ′ ). Let T ⊆ V (G) be a tracking set for (G, d, k).
We prove that T ′ is a solution for (X, S, d, k ′ ), T ′ being the set of elements in X corresponding to the vertices in V (G) ∩ T . Suppose not. Then there exists two sets, say A, B ∈ S such that A ∩ T ′ = B ∩ T ′ . Due to the construction of (X, S), it follows that there are two shortest s-t paths, say P 1 , P 2 in G, such that . This contradicts the assumption that T is a tracking set for (G, d, k).
Conversely let T ′ be a tracking set for (X, S, d ′ , k ′ ). We prove that T is a solution for (G, d, k), T being the set of vertices in V (G) corresponding to the elements in X ∩ T ′ . Suppose not. Then there exists two shortest s-t paths in G, say P 1 , P 2 , such that T ∩ V (P 1 ) = T ∩ V (P 2 ). Due to the construction of (X, S), it follows that there exist two sets, say A, B ∈ S such that T ′ ∩ A = T ′ ∩ B.
This contradicts the assumption that T ′ is a tracking set for (X, S, d ′ , k ′ ).
Note that Lemma 9 also serves as a reduction from Tracking Shortest Paths to Tracking Set System.
Note that we did not talk about the running time of the reduction in Lemma 9, which in general case may be exponential. However, if the time taken to enumerate all shortest s-t paths is FPT then the reduction from diamd-Tracking Shortest Paths to d-Tracking Set can be done in FPT time.
Hence we have the following corollary. Proof. Let G be the graph in the input instance of diam-d-Tracking Shortest Paths or Tracking Shortest Paths. We start by applying Reduction Rule 1 to G. Using Lemma 8 we can enumerate the vertex sets of all shortest s-t paths in graph G. If there are more than 2 k shortest s-t paths in G, then due to Corollary 1(i), it is a NO instance. Else using Lemma 9 we can reduce the input instance to an equivalent instance of d-Tracking Set.
In the case of diam-d-Tracking Shortest Paths, from Lemma 3, we know that d-Tracking Set can be reduced to d-Hitting Set. Hence, due to [17],

Improved FPT algorithm for Tracking Shortest Paths
Here we obtain an improved FPT algorithm for Tracking Shortest Paths. This is done by first reducing Tracking Shortest Paths to the problem of tracking all paths in a directed acyclic graph. Some additional preprocessing rules are given for DAGs, that result in a larger lower bound for the number of s-t paths in a graph, thereby giving a smaller upper bound for the size of the vertex set.
Let (G, k) be an instance of Tracking Shortest Paths. We start by applying Reduction Rule 1. This removes all those vertices and edges from G that do not participate in any shortest s-t path.
Next we reduce Tracking Shortest Paths to the problem of tracking all s-t paths in a directed acyclic graph. We formally define the problem as follows.

Tracking Paths in DAGs
Input: A directed acyclic s-t graph G = (V, E).
Output: A minimum set of vertices T ⊆ V , such that for any two distinct s-t paths P 1 and P 2 in G, it holds that T ∩ V (P 1 ) = T ∩ V (P 2 ).
An instance of the parameterized version of Tracking Paths in DAGs is denoted by (G, k), where G is the input graph and k is the size of the desired tracking set for G. Note that a pair of paths in G cannot have the same vertex set but different sequence of vertices, as this would create a cycle. Hence in a DAG, in order to identify each s-t path uniquely, it is sufficient for each s-t path to have a unique intersection with a tracking set. Next we prove that there exists a polynomial time reduction from Tracking Shortest Paths to Tracking Paths in DAGs.

is a YES instance if and only if (G ′ , k) is a YES instance.
Proof. We assume G to be preprocessed by Reduction Rule 1. We create the graph G ′ from G as follows. Construct the s-t graph G ′ by creating a copy of G. Next, orient each edge in G ′ towards the destination t. Note that now each shortest s-t path in G is an s-t path in G ′ . Further, each s-t path in G ′ is a shortest s-t path in G. This holds due to the application of Reduction Rule 1 on G. Since the set of shortest s-t paths in G is same as the set of s-t paths in G ′ , it holds that if there exists a tracking path T of size k, for all shortest s-t paths in G, then T is also a tracking set for all s-t paths in G ′ .
Lemma 10 also proves the hardness for the problem of tracking all s-t paths in directed acyclic graphs.

Corollary 5. Tracking Paths in DAGs is NP-hard.
In the remainder of the section, by graph we mean a DAG, and by path we mean a directed path. Now we give a kernel and an FPT algorithm for Tracking Paths in DAGs. Note that here our objective is to track all s-t paths in a DAG. We start by giving a reduction rule that removes all those vertices from a DAG G, that do not participate in any s-t path in G. In order to implement the rule, we perform the following steps exhaustively:

Reduction Rule 2. If there exists a vertex or an edge in
1. Delete all incoming edges on the source s.
2. Delete all outgoing edges from the destination t.

For a vertex
v along with all its incident edges.
Note that after performing the above steps, there exists a path from s to each vertex in G, and there exists a path from each vertex in G to t. Suppose not. Let π be a topological ordering of G. Let x be a vertex that is not reachable from s. Without loss of generality, let x be the first vertex in π, such that x is not reachable from s. Thus all vertices that appear before x in π are reachable from s. Since deg − (x) ≥ 1, there exists a vertex y such that y ∈ N − (x). Since y is an in-neighbor of x, y is reachable from s. Further, since (y, x) ∈ E(G), it holds that x is also reachable from s. Similarly it can be proven that t is reachable from each vertex in G. Note that for a vertex v ∈ G, a path from s to v cannot intersect a path from v to t at any vertex other than v, as this would create a cycle, and contradict the fact that G is a DAG. Hence now each vertex and edge in G, participates in an s-t path in G. It can be seen that the total time taken to apply the rule is O(n + m).
Note that after application of Reduction Rule 2, each vertex in a graph except s and t has non zero in-degree and out-degree. Further, if the degree of a vertex is two, then both its out-degree and in-degree are exactly one. For the remainder of the paper we assume that the graph has been preprocessed using Reduction Rule 2.
Next we give a lemma that gives a lower bound for the number of s-t paths in a directed acyclic graph reduced using Reduction Rule 2. Assume that the claim is true for p ≤ k, where k ≥ 2. Consider p = k + 1, First we consider the case when (s, t) ∈ E(G). Delete the edge (s, t). This reduces the out-degree of s by one and thus reduces the value of p by one. Further, after deletion of (s, t), the resultant graph is still reduced under Reduction Rule 2, i.e. each vertex and edge participates in an s-t path. Hence by induction hypothesis, after deletion of the edge (s, t), the claim holds for p = k. Since the edge (s, t) itself is also an s-t path, it increases the count of s-t paths in G by one. Hence the claim holds for p = k + 1 as well.
Next consider the case when (s, t) / ∈ E(G). In the following, we will reduce the value of p by exactly one, and show that the number of s-t paths in the graph is also reduced by exactly one. Let x be a vertex closest to t, such that Such a vertex exists, since due to Reduction Rule 3, deg + (s) ≥ 2.
Due to Reduction Rule 2, there exists a directed path, say P xt , from x to t. Let v be the first vertex in P xt such that deg − (v) ≥ 2. Such a vertex exists since due to Reduction Rule 3, deg − (t) ≥ 2. Let P ′ xt be the subpath of P xt lying between vertices x and v, excluding the vertices x and v. Note that P ′ xt is either a single edge or a path of degree two vertices. Let G ′ be the graph obtained after deletion of P ′ xt . Note that the out-degree of x is reduced by one in G ′ . For each vertex deleted in P ′ xt , the value of p remains unchanged as the reduction in summation of out-degree is accompanied by an equal reduction in the count of vertices. Hence, in G ′ , p is reduced by exactly one, i.e. p = k. Further note that, after deletion of P ′ xt , each vertex and edge in the graph still participates in an s-t path. Hence by induction hypothesis, the claim holds for p = k. Observe that deletion of P ′ xt reduces the number of s-t paths by at least one. Hence the claim holds for p = k + 1 as well. This completes the proof.
Next we give a reduction rule that ensures that degree of s and t is at least two.  Proof. Observe that if deg(s) = 1 and u ∈ N + (s), then all paths that start at s, pass through u and vice-versa. Similarly, if deg(t) = 1 and v ∈ N − (t), then all paths that reach t, pass through v and vice-versa. Hence in such a case, it is safe to assign the neighbor of s (t) as the source (destination), and delete the original s (t). It can be seen that the rule can be applied in constant time.

Reduction
Next we give a reduction rule that helps remove long degree two paths (paths containing only vertices with degree two in the graph) from the input graph. Let G ′ be the graph obtained after deletion of the vertex y and introduction of the edge (x, z). We claim that (G, k) is a YES instance if and only if (G ′ , k) is a YES instance.
Let (G, k) be a YES instance where T is a tracking set of size k. Consider the case when y / ∈ T , then we claim that T ′ = T is a tracking set for G ′ .
Suppose not. Then there exists two s-t paths, say P 1 , P 2 , in G ′ such that , then P 1 and P 2 are also paths in G with the same trackers, contradicting the assumption that T is a tracking , then without loss of generality, let P ′ 1 be the path in G corresponding to P 1 before deletion of y. Now, P ′ 1 and P 2 are two paths in G with the same set of trackers, which is a contradiction. If x ∈ V (P 1 ) ∩ V (P 2 ), then let P ′ 1 and P ′ 2 be the paths in G corresponding to P 1 and P 2 , before deletion of y. Now, P ′ 1 and P ′ 2 are two paths in G with the same set of trackers, which is a contradiction.
Next, consider the case when y ∈ T . We claim that T ′ = T \ {y} ∪ {x} is a tracking set for G ′ . Suppose not. Then there exists two s-t paths, say P 1 , P 2 , , then P 1 and P 2 are also paths in G with the same trackers, contradicting the assumption that T is a tracking set for G. If x ∈ V (P 1 ) \ V (P 2 ), it contradicts the assumption that P 1 and P 2 have the same set of trackers. If x ∈ V (P 1 ) ∩ V (P 2 ), then let P ′ 1 and P ′ 2 be the paths in G corresponding to P 1 and P 2 , before deletion of y. Now, P ′ 1 and P ′ 2 are two paths in G with the same set of trackers, which is a contradiction.
Let (G ′ , k) be a YES instance where T ′ is a tracking set of size k. We claim that T = T ′ is also a tracking set for G. Suppose not. Then there exists two s-t paths P 1 , P 2 in G, such that V (P 1 )∩T ′ = V (P 2 )∩T ′ . If y / ∈ V (P 1 )∪V (P 2 ), then P 1 and P 2 are also paths in G ′ with the same set of trackers. This contradicts the assumption that (G ′ , k) is a YES instance. So y ∈ V (P 1 ) \ V (P 2 ). Then let P ′ 1 be the path in G ′ corresponding to P 1 after deletion of y. Note that P ′ 1 and P 2 are paths in G ′ with the same set of trackers, which is a contradiction. Else, if y ∈ V (P 1 ) ∩ V (P 2 ), then let P ′ 1 and P ′ 2 be the paths in G ′ corresponding to P 1 and P 2 after deletion of y. Note that P ′ 1 and P ′ 2 have the same set of trackers. This contradicts the assumption that T ′ is a tracking set for G ′ .
In order to apply the rule, we consider each vertex u ∈ V (G). If deg(u) = 2 and deg(v) = 2, where v ∈ N + (u), then we delete v and introduce an edge between u and w ∈ N + (v). This can be done in O(n + m) time.
Next we give a reduction rule which helps finding trackers for a special type of subgraph, and also further reduces the number of degree two vertices in the graph.
Reduction Rule 5. In a DAG G, if two vertices u, v ∈ V (G) have ℓ ≥ 2 common neighbors that are of degree two, delete ℓ−1 of those common neighbors and reduce k by ℓ − 1.

Lemma 15. Reduction Rule 5 is safe and can be applied in polynomial time.
Proof. Let V ′ be the set of ℓ degree two vertices that are common neighbors of u and v. Note that all the ℓ vertices in V ′ should have both in-degree and outdegree exactly one, else they would not be part of some s-t path. Observe that the vertices in V ′ form ℓ vertex disjoint paths between u and v. Let (u, w) be an edge that is part of one of these ℓ paths, where w ∈ V ′ . Note that (w, v) ∈ E(G).
Due to Reduction Rule 2, (u, w) participates in an s-t path, say P . Note that (w, v) also belongs to P . Observe that there exists ℓ − 1 distinct s-t paths in G, if the edges (u, w) and (w, v) are replaced by edges (u, x) and (x, v), where x ∈ V ′ . Hence, including path P , there exists ℓ distinct s-t paths in G that differ only at the vertices in V ′ . Hence in order to distinguish between these paths, we have to put trackers on at least ℓ − 1 of the ℓ vertices in V ′ . In order to apply Reduction Rule 5, for each pair u, v ∈ V , check if two or more vertices in N (u) ∩ N (v) are of degree two. This can be done in O(n 3 ) time.
After the application of Reduction Rules 4 and 5, we have the following observation.
Observation 2. For a pair of vertices u, v ∈ V (G) there exists at most one vertex of degree two that is adjacent to both u and v. Further, each vertex of degree two, is adjacent to vertices of degree greater than two.
Next we give a lower bound for the number of s-t paths in a DAG reduced under Reduction Rules 2, 3, 4, and 5. We call such DAGs reduced DAGs. and t is at least two. In order to ensure that degree of s and t is at least three, we introduce the edge (s, t) to E(G ′ ). Note that this increases the count of s-t paths by exactly one. Since now G ′ comprises of only vertices with degree at least three, the summation of degree of all vertices in G ′ is greater than or equal to 3n 3 . Thus the total out-degree of all vertices in the graph is at least 3n 3 /2.
From Lemma 12, we know that the total number of s-t paths, say p, is at least reducing the count by one due to the new edge(s, t) ≥ √ n/4 (since n 3 + n 2 = n) Next we have the following observation which helps to count the number of s-t paths in a DAG, similar to Observation 1. Next we give a condition that helps verify if a set of vertices is a tracking set for all s-t paths in a graph, in polynomial time.
Tracking Set Condition. For a graph G, a set of vertices T ⊆ V (G) is said to follow the tracking set condition if there exists at most one path between any two vertices u, v ∈ T ∪ {s, t} in the graph G(V \ (T \ {u, v})).
Next we show that the Condition 4.2 is necessary and sufficient for a set of vertices to be a tracking set. Proof. Let T ⊆ V be a tracking set for G. We claim that T follows the tracking set condition. Suppose not. Then there exists two vertices u, v ∈ T ∪ {s, t} such that there exists two paths, say P 1 , P 2 , between u and v that do not contain any vertex from T \ {u, v}. Due to Reduction Rule 2, each vertex in G participates in a s-t path. Hence there exists a path from s to u, say P su , and there exists a path from v to t, say P vt . Note that since G is a directed acyclic graph, P su can intersect with P 1 and P 2 only at u. Similarly, P vt can intersect with P 1 and P 2 only at v. Observe that paths P su · P 1 · P vt and P su · P 2 · P vt are two distinct s-t paths that contain the same set of trackers. This contradicts the assumption that T is a tracking set for G.
Conversely, let T ⊆ V be a set of vertices that follows the tracking set condition. We claim that T is a tracking set for G. Suppose not. Then there exists two distinct s-t paths in G, say P 1 , P 2 , that contain the same set of trackers. Let x, y ∈ V (P 1 ) ∩ V (P 2 ) be two vertices, such that x, y ∈ T ∪ {s, t}.
Note that if P 1 and P 2 are vertex disjoint paths except for vertices s and t, then vertices x and y are s and t. Let P ′ 1 be the subpath of P 1 between vertices x and y, and P ′ 2 be the subpath of P 2 between vertices x and y. Observe that x, y is a pair in T ∪ {s, t} such that there exists two paths between x and y that do not contain any vertices from T \ {x, y}. This violates the tracking set condition and thus contradicts the assumption that T follows tracking set condition.  Proof. We start by applying Reduction Rules 2, 4, and 5. For convenience, we use (G, k) to denote the reduced instance, and n and m to denote the number of vertices and edges in G. Let p be the number of s-t paths in G. In order to track p paths, we need at least lg(p) trackers (follows from Corollary 1(i)).
From Lemma 16, we know that p ≥ √ n/4. Hence lg(p) ≥ lg √ n − 2. Using Observation 3, we find the value of p in O(m + n) time. Next, if k < lg(p), i.e. k < 0.5 lg n − 2, we report that it is a NO instance. Else, k ≥ lg( √ n/4). Hence n ≤ 2 2k+4 . Now for each subset of T ⊆ V of size k, we verify whether T is a tracking set for G, using the tracking set condition in O(k 2 (m + n)) time. Thus in O(2 2k 2 +4k k 2 (m + n)) time, we can find a tracking set of size at most k if one exists.

Conclusions
In this paper we have studied tracking set problems for set systems, shortest s-t paths in undirected graphs and s-t paths in DAGs. We gave a polynomial kernel for Tracking Set System for the case when size of the sets in the family is restricted to at most d. The improved kernel and algorithm for Tracking Set System in this case also implies corresponding improvements for Test Cover for the case when frequency of appearance of each element is restricted to at most d sets.
The results for Tracking Set System are then used to give an FPT algorithm for Tracking Shortest Paths in graphs, and a polynomial kernel for the case when the diameter of the input graph is restricted to d. Finally we give an improved algorithm for Tracking Shortest Paths by first reducing it to Tracking Paths in DAGs and then using some structural properties of DAGs.
Possible directions of further study include exploration of other variants of Tracking Set System and obtaining improved FPT algorithms for Tracking Shortest Paths at least in special graph classes.