Polynomial Kernels for Tracking Shortest Paths¹¹footnotemark: 1

Let $E_{x}$ be the set of edges with tails in $Z_{x}$. Then observe that $|E_{x}|=\sum_{z\in Z_{x}}\deg^{+}(z)$.

By the above claims and since $x\in Z_{x}$ is not a head of any edge in $E_{x}$, we have $\sum_{z\in Z_{x}}\deg^{+}(z)=|E_{x}|\leq|Z_{x}|-1+|B_{x}|$ and the lemma follows. ∎

We claim that $V\setminus\{t\}=\bigcup_{x\in T\cup\{s\}}Z_{x}$. For a vertex $z\in V\setminus\{t\}$, let $P_{z}$ be an $s$-$t$ path containing $z$. Let $x$ be the last vertex of $T\cup\{s\}$ on $P_{z}$. Then $z\in Z_{x}$. Hence,

Inequality (a) comes from Lemma 1 and Inequality (b) comes from the fact that $B_{x}\subseteq T\cup\{t\}$. ∎

Let $T$ be a tracking set of size at most $k$ in $G$. Let $V_{2}$ be the set of vertices with out-degree at least $2$. Note that all other vertices have out-degree at least $1$, except for $t$, which has out-degree $0$. We have

Inequality (a) comes from $V_{2}\subseteq V$ and adds $1$ for vertex $t$, (b) comes from Lemma 2. Therefore, there are at most $\sum_{z\in V_{2}}(\deg^{+}(z))=|V_{2}|+\sum_{z\in V_{2}}(\deg^{+}(z)-1)\leq|V_{2}|+1+\sum_{z\in V}(\deg^{+}(z)-1)\leq 2{(|T|+1)}^{2}$ edges with tails in vertices with out-degree at least $2$. There are at most $|V_{2}|\leq{(|T|+1)}^{2}$ edges with heads in vertices with out-degree at least $2$ and in-degree $1$. By a symmetrical argument, there are at most $2{(|T|+1)}^{2}$ edges with heads in vertices with in-degree at least $2$ and at most ${(|T|+1)}^{2}$ edges with tails in vertices with in-degree at least $2$ and out-degree $1$.

As the graph is reduced by Reduction Rules 1–3 every edge is incident to a vertex with in-degree at least $2$ or out-degree at least $2$. Hence, there are at most $6{(|T|+1)}^{2}\leq 6{(k+1)}^{2}$ edges in total. Each vertex with in-degree $1$ and out-degree $1$ is incident to an edge with tail in vertex with total degree at least $3$. Therefore, there are at most $3{(|T|+1)}^{2}$ vertices with in-degree $1$ and out-degree $1$ and, hence, at most $5{(|T|+1)}^{2}\leq 5{(k+1)}^{2}$ vertices in total. ∎

Let $G$ be a reduced planar DAG and $F$ be the set of faces in some planar drawing of $G$. Note that, since the instance is reduced with respect to Reduction Rule 4, we have $|F|\leq 2k$. Let $V_{\geq 3}$ be the set of vertices with degree at least $3$ and $V_{2}$ be the set of vertices with degree equal to $2$. Recall that after exhaustive application of Reduction Rules 1–3 there are no vertices with degree $1$ in $G$ and each vertex with degree $2$ has vertices with degree $3$ or more as its neighbors.

First we construct an auxiliary graph $G^{\prime}=(V^{\prime},E^{\prime})$ by short-circuiting all vertices in $V_{2}$ (the vertex is deleted and an edge is introduced between its neighbors). Due to Reduction Rules 5 and 6, the short-circuiting does not create parallel edges. Note that the number of faces $|F|$ in $G$ is the same as that in $G^{\prime}$, that is, at most $2k$. Further, $|V^{\prime}|=|V_{\geq 3}|$, $|V_{2}|\leq|E^{\prime}|$, and $|E|\leq 2|E^{\prime}|$.

We now bound the size of $V_{\geq 3}$. Due to the Handshaking lemma and the fact that degree of all vertices in $G^{\prime}$ is at least $3$, we get

Due to Euler’s formula, we have

Hence,

Thus, $|V_{2}|\leq|E^{\prime}|=|F|+|V^{\prime}|-2\leq 2k+4k-4-2=6k-6$. The total number of vertices in $G$ is $|V|=|V_{2}|+|V_{\geq 3}|\leq 6k-6+4k-4=10k-10$. Since $|E|\leq 2|E^{\prime}|$, $|E|\leq 12k-12$. ∎

There is a one-to-one correspondence between the directed $s$-$t$ paths in $G$ and the directed $s$-$t$ paths in $G^{\prime}$. Hence, if $T$ is a solution for $(G,s,t,k)$, then it is also a solution for $(G^{\prime},s,t,k)$. Similarly, if $T$ is a solution for $(G^{\prime},s,t,k)$ that does not contain $v$, then it is also a solution for $(G,s,t,k)$. Hence, assume that there is a solution $T$ for $(G^{\prime},s,t,k)$ which contains $v$. Our aim is to show that there is also a solution $T^{\prime}$ for $(G^{\prime},s,t,k)$ which does not contain $v$ and hence is also a solution for $(G,s,t,k)$.

Suppose first that there is a directed $u$-$w$ path $Q$ in $G^{\prime}$ which does not contain vertices of $T$ as internal vertices. Note that, as $v\in T$, this path does not contain $v$. If $Q$ is the single edge $(u,w)$, then there are parallel edges in $G$ that contradict our assumptions. Hence, $Q$ contains at least one internal vertex. Let $v^{\prime}$ be an arbitrary internal vertex of $Q$. We claim that $T^{\prime}=(T\setminus\{v\})\cup\{v^{\prime}\}$ is a solution for $(G^{\prime},s,t,k)$.

Assume it is not and let $P_{1}$ and $P_{2}$ be two different $s$-$t$ paths such that $V(P_{1})\cap T^{\prime}=V(P_{2})\cap T^{\prime}$, see Figure 1. Since $V(P_{1})\cap T\neq V(P_{2})\cap T$, exactly one of the paths contains $v$. Without loss of generality, assume that $v\in V(P_{1})$ and $v\notin V(P_{2})$. Note that $v^{\prime}\notin V(P_{1})$ since the graph does not have directed cycles. Hence, $v^{\prime}\notin V(P_{2})$ as $V(P_{1})\cap T^{\prime}=V(P_{2})\cap T^{\prime}$. Therefore $V(P_{2})\cap T=V(P_{2})\cap T^{\prime}$. Now consider the path $P^{\prime}_{1}$ obtained from $P_{1}$ by replacing the subpath $u,v,w$ with $Q$. Since $Q$ does not contain vertices of $T$ as internal vertices, we have $V(P^{\prime}_{1})\cap T=V(P_{1})\cap T^{\prime}$. It follows that

which contradicts that $T$ is a solution for $(G^{\prime},s,t,k)$.

Now assume that there is no directed $u$-$w$ path in $G^{\prime}$ that does not contain vertices of $T$ as internal vertices, see Figure 2. Consider the set $T_{u}=(T\setminus\{v\})\cup\{u\}$ and the set $T_{w}=(T\setminus\{v\})\cup\{w\}$. We will show that if neither $T_{u}$ nor $T_{v}$ is a solution in $(G^{\prime},s,t,k)$, then $T$ is not a solution in $(G^{\prime},s,t,k)$, a contradiction.

If $T_{u}$ is not a solution, then there are two $s$-$t$ paths $P_{1}$ and $P_{2}$ such that $V(P_{1})\cap T_{u}=V(P_{2})\cap T_{u}$. Since $V(P_{1})\cap T\neq V(P_{2})\cap T$, exactly one of the paths, say $P_{1}$, contains $v$. This implies $u\in V(P_{1})$ and, as $u\in T_{u}$, also $u\in V(P_{2})$. Let $t^{\prime}$ be the first common vertex of the paths $P_{1}$ and $P_{2}$ after $u$. Let $P^{\prime}_{1}$ be the part of the path $P_{1}$ between $w$ and $t^{\prime}$, $P^{\prime}_{2}$ be the part of the path $P_{2}$ between $u$ and $t^{\prime}$ (note the slight asymmetry). Since $V(P_{1})\cap T_{u}=V(P_{2})\cap T_{u}$, neither $P^{\prime}_{1}$ nor $P^{\prime}_{2}$ contains vertices of $T$ as internal vertices. By assumption, this implies $t^{\prime}\neq w$, as otherwise $P^{\prime}_{2}$ would be a $u$-$w$ path. This, in turn, implies $w\notin T$.

Now, the same argument could be repeated on a graph with swapped labels $u$ and $w$, $s$ and $t$, and where direction of all edges is reversed. We present it for completeness. If $T_{w}$ is not a solution, then there are two $s$-$t$ paths $Q_{1}$ and $Q_{2}$ such that $V(Q_{1})\cap T_{w}=V(Q_{2})\cap T_{w}$. Since $V(Q_{1})\cap T\neq V(Q_{2})\cap T$, exactly one of the paths, say $Q_{1}$, contains $v$. This implies $w\in V(Q_{1})$ and, as $w\in T_{w}$, also $w\in V(Q_{2})$. Let $s^{\prime}$ be the last common vertex of the paths $Q_{1}$ and $Q_{2}$ before $w$. Let $Q^{\prime}_{1}$ be the part of the path $Q_{1}$ between $s^{\prime}$ and $u$, $Q^{\prime}_{2}$ be the part of the path $Q_{2}$ between $s^{\prime}$ and $w$ (again the slight asymmetry). Since $V(Q_{1})\cap T_{w}=V(Q_{2})\cap T_{w}$, neither $Q^{\prime}_{1}$ nor $Q^{\prime}_{2}$ contains vertices of $T$ as internal vertices. By assumption, this implies $s^{\prime}\neq u$. This, in turn, implies $u\notin T$.

Let $P_{s}$ be any path from $s$ to $s^{\prime}$, e.g., a part of $Q_{1}$ and let $P_{t}$ be any path from $t^{\prime}$ to $t$, e.g., a part of $P_{1}$. Let $R_{1}$ be the $s$-$t$ path formed by the concatenation of $P_{s}$, $Q^{\prime}_{1}$, $P^{\prime}_{2}$, and $P_{t}$; also let $R_{2}$ be formed by the concatenation of $P_{s}$, $Q^{\prime}_{2}$, $P^{\prime}_{1}$, and $P_{t}$. Note that $R_{1}$ goes through $u$ and $R_{2}$ goes through $w$, but neither of them contains $v$. These paths only differ in the part between $s^{\prime}$ and $t^{\prime}$. Namely, $R_{1}$ contains $Q^{\prime}_{1}$ and $P^{\prime}_{2}$ while $R_{2}$ contains $Q^{\prime}_{2}$ and $P^{\prime}_{1}$. As argued above, neither of $P^{\prime}_{1},P^{\prime}_{2},Q^{\prime}_{1},Q^{\prime}_{2}$ contains a vertex of $T$ as an internal vertex. Moreover, neither $u$ nor $w$ is in $T$. It follows that $V(R_{1})\cap T=V(R_{2})\cap T$ which contradicts that $T$ is a solution for $(G^{\prime},s,t,k)$. Therefore, $T_{u}$ or $T_{w}$ is a solution for $(G^{\prime},s,t,k)$ which finishes the proof. ∎

Let $(G=(V,E),s,t,k)$ be an instance of Tracking Paths in DAG. We first compute the prospective layer $L(v)$ for each vertex $v$ by the following procedure. Start by assigning $L(s)=0$ for $s$ (and all other sources if there are any; there are none in our kernels). For all other vertices $v$ in topological order, assign $L(v)=1+\max\{L(u)\mid u\in N^{-}(v)\}$. Note that, as we always only add $1$ for each vertex, we have $\max\{L(v)\mid v\in V\}\leq|V|-1$.

Next, we create an auxiliary directed graph $G^{\prime\prime}$ from $G$ as follows. For each edge $(u,v)$ with $L(u)+1<L(v)$ we subdivide the edge $L(v)-L(u)-1$ times to obtain a path with $L(v)-L(u)-1$ internal vertices. In $G^{\prime\prime}$ every directed $s$-$t$ path has length exactly $L(t)$. Also it follows from Lemma 6 that $(G^{\prime\prime},s,t,k)$ is a YES instance of Tracking Paths in DAG if and only if $(G,s,t,k)$ is a YES instance of Tracking Paths in DAG.

Let $G^{\prime}$ be the underlying undirected graph of $G^{\prime\prime}$. Every $s$-$t$ path in $G^{\prime}$ is of length at least $L(t)$ and all paths of length exactly $L(t)$ are actually directed paths in $G^{\prime\prime}$, since the edges of $G^{\prime\prime}$ only connect consecutive layers. Hence, the shortest $s$-$t$ paths in $G^{\prime}$ are exactly the directed $s$-$t$ paths in $G^{\prime\prime}$.

Hence, $(G^{\prime},s,t,k)$ is a YES instance of Tracking Shortest Paths if and only if $(G,s,t,k)$ is a YES instance of Tracking Paths in DAG. Observe that for each edge of $G$ the corresponding path in $G^{\prime}$ contains at most $|V|-2$ new vertices and edges. Since each path can be of length at most $V(G)$, the number of vertices and edges in $G^{\prime}$ is at most $|E(G)|\cdot|V(G)|$. ∎

Lemma 7 implies that if there exists a kernel of size $X$ for an instance of Tracking Paths in DAG, then there exists a kernel of size $X^{2}$ for the corresponding instance of Tracking Shortest Paths. Theorem 1 gives a kernel for Tracking Paths in DAG with $\mathcal{O}(k^{2})$ vertices and edges, and Theorem 2 gives a kernel with $\mathcal{O}(k)$ vertices and edges in planar graphs. Applying the implied bound to these kernels for Tracking Paths in DAG yields the desired kernels for Tracking Shortest Paths. ∎