Given a graph G with source and destination vertices s; t 2 V (G) respectively, Tracking Paths asks for a minimum set of vertices T V (G), such that the sequence of vertices encountered in each simple path from s to t is unique. The problem was proven NP-hard [3] and was found to admit a quadratic kernel when parameterized by the size of the desired solution [6]. Following recent trends, for the rst time, we study Tracking Paths with respect to structural parameters of the input graph, parameters that measure how far the input graph is, from an easy instance. We prove that Tracking Paths admits xed-parameter tractable (FPT) algorithms when parameterized by the size of vertex cover, and the size of cluster vertex deletion set for the input graph.
Graph theory plays a fundamental role in modeling many real world problems related to (but not limited to) road networks, tra c monitoring, world wide web, social networks and circuit design. One of the graph theoretic problems studied in recent years is Tracking Paths: Given a graph, nd a set of vertices that can help uniquely distinguish all simple paths between a given source and destination in the input graph. The problem nds applications in secure facility object tracking, tracing data packets in network, identifying source of fake news on social media, and tracking objects in wireless sensor networks.
More formally, let !V(P ) be the sequence of vertices in a path P . A tracking set for a graph G with source s and destination t is a subset T of vertices such that for any two distinct s-t paths P1 and P2, !V(P1) 6= !V(P2), and the Tracking Paths problem is de ned as follows:
The problem was rst studied by Banik et al. [
Parameterization of a problem involves associating the problem with an integer
k. A parameterized problem is said to admit a xed-parameter tractable(FPT)
algorithm if there exists an algorithm with running time of the type f (k):nO(1),
where f is a computable function, k is the parameter and n is the input size.
Tracking Shortest Paths was proven to be FPT when parameterized by the
size of tracking set [
Tracking Paths (not just tracking shortest paths) was proven to be
NPhard for general graphs [
The problem was shown to be FPT when parameterized by the size of
tracking set, by showing the existence of a polynomial kernel [
For a parameterized problem, although output size is a natural parameter,
recent years have seen increasing attention on parameters related to structure of
the input [
Edgeless graphs do not need any trackers (since they lack s-t paths) and a tracking set can be found in polynomial time for cluster graphs (proven later in the paper). Hence, it is an interesting question to analyze whether there exists an FPT algorithm to solve Tracking Paths for graphs that are k vertices away from an edgeless graph or a cluster graph. Usually, the quest is to look for the smallest possible parameter for which the problem at hand is xed-parameter tractable. In general, the size of a minimum vertex cover can be both larger or smaller than the size of a tracking set for a graph. A graph with long paths of degree two vertices can have a vertex cover larger than the size of a tracking set. While a denser graph can have a tracking set bigger than the size of a vertex cover. See Figure 1. Here the circled vertices represent a vertex cover. However, all vertices except s; t need to be part of a tracking set.
s t Our Approach. The usual challenge with structural parameterization is that the parameter does not drop by rules that utilize properties of the output. We start by applying some known preprocessing rules and then use some structural properties to mark vertices as trackers that de nitely need to belong to any tracking set. Then we bound the number of vertices that are left unmarked as a function of the parameter. Finally we try all subsets of the unmarked vertices to nd which among them can be trackers.
To design FPT algorithms for the two parameterizations we consider in this paper, we rst de ne an intermediate parameter, and that is the size of what we call a Dual Connected Modulator. For a graph G = (V; E), a set of vertices S V is a dual connected modulator (DCM) if every vertex in V n S has at least two neighbours in S and has an additional property . For parameterization by the size of vertex cover or cluster vertex deletion set, it su ces that is a disjoint union of cliques.
We will rst give an FPT algorithm for Tracking Paths parameterized by the size of a dual connected modulator. Then we show how this algorithm can be used to give FPT algorithms for Tracking Paths parameterized by the size of vertex cover and cluster vertex deletion set.
Throughout the paper, we assume graphs to be simple (no self loops or
multiedges). We assume that the input graph contains a unique source s and a unique
destination t (s and t are known), and we aim to nd a tracking set that can
distinguish all simple paths between s and t. Here s and t are also referred as the
terminal vertices. If a; b 2 V , then unless otherwise stated, fa; bg represents the
set of vertices a; b, and (a; b) represents an edge between a and b. For a vertex
v 2 V , the neighbourhood of v is denoted by N (v) = fx j (x; v) 2 Eg. Degree of a
vertex v is denoted by deg(v) = jN (v)j. For set of vertices V 0, G(V 0) denotes the
graph induced by vertices in V 0. For a subgraph G0 of G, V (G0) represents the
vertex set of G0 and E(G0) represents those edges whose both endpoints belong to
V (G0). We use G0 G to denote that G0 is a subgraph of G. For a vertex v 2 V
and a subgraph G0, NG0 (v) = N (v) \ V (G0) and degG0 (v) = jN (v) \ V (G0)j. For
a subset of vertices V 0 V we use N (V 0) to denote Sv2V 0 N (v). For a graph
G and a set of vertices S V (G), G S denotes the subgraph induced by the
vertex set V (G) n V (S). For A; B V (G), A ] B denotes that A and B are vertex
disjoint partitions of graph G. Let P1 be a path between vertices a and b, and P2
be a path between vertices b and c, such that V (P1) \ V (P2) = fbg. By P1:P2, we
denote the path between a and c, formed by concatenating paths P1 and P2 at b.
Two paths P1 and P2 are said to be vertex disjoint if their vertex sets do not
intersect except possibly at the end points, i.e. V (P1) \ V (P2) fa; bg, where a
and b are the starting and end points of the paths. For details on parameterized
complexity please refer to [
In this section, we give an FPT algorithm for Tracking Paths parameterized by the size of a Dual Connected Modulator. Recall that for a graph G, a subset of vertices S V (G) is a DCM if every vertex in V (G) n S has at least two neighbours in S, and has an additional property .
Input: An undirected graph G = (V; E) with terminal vertices s and t, and a dual connected modulator S V (G) for G, such that jSj = k. Question: Find a minimum cardinality tracking set T for G.
The main idea of the algorithm is to rst guess how S intersects with a tracking set T in G, and then for each such guess, analyze the graph structures across the partition S ] (G S) and mark as many vertices as possible, as trackers. In the process, we give an upper bound for the number of vertices left unmarked in G S. Finally, we consider all possible subsets of unmarked vertices in G S as trackers, and together with the set of already marked vertices, we verify if they form a tracking set for the graph G using Theorem 1. Initially none of the vertices in V are marked as trackers. We start by recalling some preprocessing rules from previous work.
Reduction Rule 2 [
Reduction Rule 3 [
We apply above rules repeatedly as long as they are applicable. We refer to the graph obtained after applying the above rules as a reduced graph. Note that in the reduced graph, there is no vertex with degree less than or equal to 1, each vertex and edge participates in an s-t path and there are no long degree 2 paths (paths with consequent degree 2 vertices). Throughout the paper, after application of each reduction rule, we retain the notations of G; S and k to refer to the graph, modulator, and size of the modulator. For now, we assume that the application of above reduction rules does not destroy any properties of the modulator. Later, while analyzing speci c graph parameters, we shall tweak the rules in order to maintain the modulator properties.
T ′
S − T ′ = A S
IN OUT G − S
B
Let T be a minimum tracking set that will be output by the algorithm, and
T 0 = T \ S be the subset of T that belongs to S. We attempt to guess the vertices
that belong to T 0, and towards this we simply consider all possible subsets of S.
Hence, there are 2k possible choices for T 0. For each guess T 0, observe that the
vertices in S n T 0 cannot belong to T . Thus we need to nd a tracking set for G,
that is disjoint from S n T 0. We refer to this problem as disjoint tracking set. See
Figure 2. S represents a DCM for G that is received as a part of the input and
G S represents the graph formed after removal of S from G. Recall that each
vertex in G S has two neighbours in S. First we rule out those guesses for T 0
that can be easily discarded. It is known from [
vertices u; v 2 V (G0), u is a local source and v is a local destination if G, and 1. there exists a path in G from s to u, say Psu, 2. there exists a path from v to t, say Pvt, 3. V (Psu) \ V (Pvt) = ;, and 4. V (Psu) \ V (G0) = fug and V (Pvt) \ V (G0) = fvg.
For a subgraph G0, we can check if a pair of vertices a; b 2 V (G0) forms
a local source-destination pair if there exists disjoint paths from s to a and
b to t in the graph G n G0 [ fa; bg, in quadratic time using the disjoint path
algorithm from [
Note that a subgraph can have more than one local s-t pairs. Now we can analyze subgraphs in G and identify trackers with respect to the local s-t pairs in that subgraph. Next we give two rules that help mark some vertices as trackers, and thus reduce the number of unmarked vertices in a graph.
Reduction Rule 5 3 If abc is a triangle in G such that a; b is a local s-t pair for the triangle abc and c 2= S, then mark c as a tracker. While considering the disjoint version, if c 2 S n T 0, then reject the current guess for T 0.
with a; b 2 V (G0) as a local s-t pair for G0, then all vertices in V (G0) n fa; bg need to be marked as trackers. Further, if a; b is the only local s-t pair for G0, then delete all vertices in V (G0) n fa; bg. 3.1
Finding a Disjoint Tracking Set Let A = S n T 0 and B = V n S. Note that our aim is to nd a tracking set that is disjoint from A, i.e. T T 0 [ B. We rst look at some structures induced by vertices in S and B that tries to force some vertices in B as trackers and mark them. We start with the following reduction rule. 3 Proof of safeness and polynomial time application of Reduction Rules can be found in the full version of the paper. Reduction Rule 7 Let a; b 2 T 0. If a; b form a local s-t pair for a subgraph G0 G[fa; bg [ A] (the subgraph induced by A and a; b) and G0 induces a cycle, then reject T 0, and move to the next guess.
Since S is a DCM, each vertex in B is adjacent to at least 2 vertices in S. We categorize the vertices in B based on whether their neighbours lie in A or S A as follows: { V1: The set of vertices that have at least two neighbours in A. { V2: The set of vertices that have at least one neighbour in A and at least one in S A. { V3: The set of vertices that have at least two neighbours in S A.
Observe that B = V1 [ V2 [ V3. There can be vertices that belong to more than one category, but as we shall see, this does not a ect the outcome of the algorithm. Consider the case in which a pair of vertices u; v 2 S is adjacent to two vertices w; x 2 B. Observe that the vertices u; v; w; x induce a C4, say C. Due to Lemma 1, there exists a local s-t pair in the subgraph C. Now we analyze each of the above listed vertex sets in B, and we consider the possibility of each pair of vertices in a C4 being an local s-t pair for that C4. Then we mark all those vertices as trackers that necessarily need to belong to T , and we bound the number of unmarked vertices in V n S.
Bounding V1 T Consider a set of vertices in B that have two neighbours u; v in A, i.e. S n T 0. See Figure 3. Here, u; v cannot be trackers, as A \ T = ;. u w v x
A B Lemma 3. ~4 The number of vertices in V1 T can be bounded by k2 .
Bounding V2 T Here we consider the set of vertices in B that have one neighbour in S n A and one neighbour in A. Since u 2 S n A; v 2 A, u is already marked as a tracker and v cannot be a tracker.
Lemma 4. ~ The number of vertices in V2 T can be bounded by 2 k2 . 4 Proofs of Lemmas marked with ~ can be found in the full version of the paper. Bounding V3 T Here we consider the set of vertices in B that have two neighbours in S n A. Since u; v 2 S n A, both u and v are already marked as trackers. Since we have already analyzed the vertices in B that have at least one neighbour in A, here we restrict ourselves to only those vertices of B that are adjacent to only S A. Let G0 be the subgraph induced by (S n A) [ V3.
If a pair of vertices u; v 2 S n A are adjacent to a pair of vertices w; x 2 B, they induce a C4, say C. We create an empty set V 0, which will be used to 3 identify those vertices of V3 which might later be needed to be marked as trackers. We check for the possibility of each pair of vertices in V (C) being a local s-t pair in the following sequence: 1. If w; x form a local s-t pair: Here u; v already serve as trackers to distinguish the two paths in C between w and x. Even if (u; v) 2 E(G), we do not need any more trackers. 2. If u; w form a local s-t pair: Here v already serves as a tracker to distinguish the paths u:w and u:x:v:w. If (u; v) 2 E(G), then we mark x as a tracker to distinguish the paths u:v:w and u:x:v:w. 3. If u; v form a local s-t pair: If (u; v) 2 E(G), then we need to mark both w; x as trackers, in order to distinguish the paths u:v, u:w:v and u:x:v. If (w; x) 2 E(G), then also we need to mark both w; x as trackers, in order to distinguish the paths u:w:v, u:x:w:v and u:w:x:v. If (u; v); (w; x) 2= E(G), we arbitrarily mark one among w; x as a tracker, and add the other vertex to V30.
We add to V30 those vertices from V3 that are adjacent to a unique pair of vertices from T 0. Thus jV30j k2 . If V n S (hence V3) is an independent set, for any path in G0, at least every alternate vertex is a tracker. Hence, if a pair of paths between a local source and destination in G0, has the same sequence of trackers, then the cycle induced by the distinct portions of these paths is of length at most four. Else due to Reduction Rule 6, each component in G S has at most two unmarked vertices. Hence, if u; v 2 T 0, then there exists a path of length at most two between u and v, in G(V3 [ fu; vg), and all vertices in the path are unmarked. Thus if two such paths exist between a pair of vertices in T 0 that forms a local s-t pair, then we mark a vertex as a tracker. In k2 :nO(1) time we can nd if two such paths exist between a pair of vertices in T 0 that forms a local s-t pair. We arbitrarily mark one vertex on one of the paths as a tracker5, and the two vertices from the other subpath are added to V30. Hence jV30j 2 k2 .
Next we prove that we need not consider vertices from V3 n V30 as trackers. Lemma 5. ~ There exists a k sized tracking set for G if and only if there is one that is a subset of V1 [ V2 [ V30 [ T 0.
Now each pair of vertices in S is adjacent to at most one unmarked vertex or a vertex from V30. Note that jV1 [ V2 [ V30j 5 k2 . We consider all possible subsets of these O(k2) vertices, include them with the already marked trackers to form a tracking set, and check the validity of that tracking set using Theorem 1. 5 Proof of correctness can be found in the full version of the paper. Thus the overall algorithm takes 2O(k2):nO(1) time. While solving the disjoint problem, for each new guess for T 0, if the size of the tracking set found is less than that of the tracking set found with respect to the previous guess, we discard the previous disjoint solution, and retain the new one, else we discard the current one. Hence we have the following theorem.
Tracking Paths can be solved in 2O(k2):nO(1) time. 4
In this section we give an FPT algorithm for Tracking Paths when the parameter k is the size of a known vertex cover for the given graph.
Input: An undirected graph G = (V; E) with terminal vertices s and t, and a vertex cover S V (G) for G, such that jSj = k.
Question: Find a minimum cardinality tracking set T for G.
We start by applying Reduction Rules 1 and 2. Observe that these rules delete vertices/edges from the input graph, and hence do not tamper with the vertex cover S. Since Reduction Rule 3 introduces a new edge in the graph, we tweak the rule in order to maintain that S is a vertex cover of size at most k. Reduction Rule 8 Let u; v 2 V (G) such that deg(u) = deg(v) = 2, N (v) = fu; wg, then delete v and introduce an edge between u and w. If u; w 2= S, set S = S [ fug.
Note that if u; w 2= S, then v necessarily belongs to S. Since deletion of v reduces the size of S by one, we can safely add u (or w) to S without increasing the value of k.
Now observe that due to Reduction Rules 1 and 8, each vertex in G S has at least two neighbours in S. Hence S is a DCM for G. Thus we can apply the algorithm for DCM to derive an FPT algorithm for parameterization by the size of a vertex cover for a graph. Hence we have the following theorem.
Paths can be solved in 2O(k2):nO(1) time. 5
In this section we give an FPT algorithm for Tracking Paths when the parameter k is the size of a cluster vertex deletion set for the given graph.
Tracking Paths/Cluster Vertex Deletion Set (G; s; t; S; k) Input: An undirected graph G = (V; E) with terminal vertices s and t, and a cluster vertex deletion set S V (G) for G, such that jSj = k.
Question: Find a minimum cardinality tracking set T for G.
First we apply the Reduction Rules 1, 2 and 3 as explained below. { Reduction Rule 1: Observe that G S is a cluster graph. Thus for each component in G S, either all the vertices participate in an s-t path, or none of them do. Thus, when we apply Reduction Rule 1, it might lead to deletion of some vertices/edges from S, or some components from G S. Note that this operation does not a ect the properties of S or G S. { Reduction Rule 2: The application of this rule may delete vertices/edges from S and/or single vertex components from G S. Observe that this does not a ect the properties of S or G S. { Reduction Rule 3: Let u; v 2 V (G) be two vertices such that deg(u) = deg(v) = 2. If both u; v 2 S, we can apply the rule and its does not a ect properties of S or G S. Consider the case in which one vertex among u; v belongs to S while the other belongs to G S. In such a case, we necessarily delete the vertex that belongs to G S. Suppose u 2 S and v 2 G S. Then v must belong to a component in G S that comprises only a single edge. After application of the reduction rule, the component of v shall comprise of only a single vertex. Observe that this does not a ect the properties of S and G S.
We also apply Reduction Rules 5 and 6 to mark required vertices in G S as trackers. Note that while applying all above reduction rules, it has been maintained that G S is a cluster graph and jSj k.
Next, we try to mark as many vertices as possible as trackers in G S, such that for the unmarked vertices S is a DCM. We create two sets X = Y = ;. We use X to maintain the unmarked vertices in G S, while ensuring that they have two neighbours each in S, and we use Y to maintain some other vertices that might need to be marked as trackers. Now we identify local s-t pairs in each component. Due to Lemma 1, each component (having at least one edge) in G S has at least one local s-t pair. After the application of Reduction Rule 6, for each local s-t pair in a component, all the remaining vertices shall be marked as trackers.
First, we consider the components in G S that contain s or t, or both. Let G0 be a component in G S such that s 2 V (G0) (t 2 V (G0)). Due to Lemma 1, G0 contains a local s-t pair, say s; a (b; t). Due to Reduction Rule 6, all vertices in V (G0) n fs; ag (V (G0) n fb; tg) shall be marked as trackers. If degS(a) 2 (degS(b) 2), we add a (b) to the set X, else we add a (b) to the set Y . Note that jY j 2. Henceforth, by `components' we mean components in G S, and we assume that none of the components in G S contain s or t. Now we analyze di erent types of components in G S based on their sizes. 5.1
Components with at least three vertices Due to Lemma 1, each component has a local s-t pair. Since we already analyzed the components that contain s or t, a local s-t pair in a component necessarily needs to be adjacent to S in order to connect with the rest of the graph. Thus, each component that does not contain s; t, has at least two neighbours in S. We consider di erent cases based on the number of vertices in each component of G S that have neighbours in S.
Components with exactly two vertices with neighbours in S Let G0 G S be a component with exactly two vertices, say u; v, that have neighbours in S. Due to Lemma 1, G0 has at least one local s-t pair and since s; t 2= V (G0), u; v shall form an local s-t pair for G0 as these are the only vertices that connect G0 with rest of the graph. Due to application of Reduction Rule 6, all vertices in V (G0) n fu; vg shall have been deleted. Thus if a component has only two neighbours in S, it can consist of at most two vertices. The analysis for such components is explained in Section 5.2.
Components with three or more vertices with neighbours in S Let G0 be a component in G S. Due to Reduction Rule 6, if there are two disjoint local s-t pairs, then all vertices in that component shall be marked as trackers. We need not analyze such components further. Henceforth, we assume that if a component in G S has more than one local s-t pairs, then these pairs overlap. Consider a component G0 in G S, with two local s-t pairs. Since all local s-t pairs overlap, at most three vertices in G0, say a; b; c, form these two local s-t pairs. Consider the case in which a; b is a local s-t pair and b; c is another local s-t pair. Observe that both c and a shall be marked as trackers due to Reduction Rule 6. Since here all local s-t pairs in a component overlap, at most one vertex in the component will be left unmarked. If such unmarked vertices have at least two neighbours in S, we add them to X. Else, we prove that they need not be part of an optimum tracking set.
Lemma 6. ~ If there exists a component G0 G S with only one unmarked vertex v, and degS(v) = 1, then such a vertex need not be marked as a tracker.
Now we are left with components that have two unmarked vertices. Clearly a pair of unmarked vertices in a component shall be a local s-t pair for that component. Let G0 be a component with only one local s-t pair, say a; b, but more than two vertices with neighbours in S. Consider the following cases: 1. Both a and b have at least two neighbours in S: We add both a; b to X. 2. One among a; b, say b, has two neighbours in S, while a has only one neighbour in S: We add b to X. If b is marked as a tracker while application of the DCM algorithm, due to Lemma 6, a need not be considered as a tracker, and hence can be ignored. Else, if b is left unmarked in the DCM algorithm, we can account for a by doubling the bound obtained for unmarked vertices. 3. Both a and b have only one neighbour in S: Let c 2 NS(a) and d 2 NS(b). We introduce an additional vertex vab, and introduce edges (vab; c) and (vab; d) to E(G). We also add vab to X. If vab is eventually part of a solution, then we can arbitrarily mark either a or b, say a, as a tracker. Not that in order to distinguish paths by their vertex sequences, we can mark c along with a, thus ruling out the necessity of marking both a and b as trackers. 5.2
Single vertex and single edge components If a component in G S consists of a single vertex v, then due to Reduction Rules 1 and 2, v has at least two neighbours in S. We include v in X, i.e. X = X [ fvg.
If a component consists of a single edge (a; b) 2 E(G S), due to Reduction Rules 1 and 2, both a; b have a neighbour in S. Due to Reduction Rule 3, it is not possible that deg(a) = deg(b) = 2. Thus, at least one vertex in each single edge component has at least two neighbours in S. If both a; b have two neighbours each in S, then we set X = X [ fa; bg. Suppose (a; b) is an edge component and b has two neighbours in S, while a has only one neighbour in S. Observe that if while applying the algorithm for DCM, b is among the O(k2) bounded vertices that are left unmarked, then we can simply double this bound in order to account for vertices like a (Note that this does not change the asymptotic bound of the running time). Else, if while applying the algorithm for DCM, if b is marked as a tracker, we show that an optimum tracking set for G need not contain a. Lemma 7. ~ If there exists a component in G S that comprises an edge (a; b), and b belongs to an optimum tracking set for G, then it can be determined in polynomial time whether a needs be marked as a tracker.
Now all vertices in G S are either already marked as trackers, or need not be marked as trackers, or have been added to the set X. We consider all vertices in X, and apply the algorithm for DCM. In the nal step of the DCM algorithm, where we consider all subsets of unmarked vertices and verify if they form a tracking set (along with the marked ones), we include the vertices in Y along with the unmarked vertices. This does not a ect the bounds as jY j 2. Observe that we ignore all other vertices in G S, except the ones in X, while analyzing di erent cases in the DCM algorithm. Hence, we have the following theorem.
Tracking Paths can be solved in 2O(k2):nO(1) time. 6
In this paper, we study structural parameterizations of the Tracking Paths problem. We prove that Tracking Paths is FPT when parameterized by the size of vertex cover or the size of cluster vertex deletion set. We do so by giving a generalized algorithm for the case when the modulator has some speci c properties. It would be interesting to explore if the running time of our algorithms can be improved further. Future scope involves studying Tracking Paths structural parameterization with respect to more parameters like odd cycle traversal, feedback vertex set and distance to chordal graph.