## May 18, 2018:

# A Polynomial Sized Kernel for Tracking Paths Problem

## Pedro Matias, UCI

Consider a secure environment (say an airport) that has a unique entry and
exit point with multiple paths between them. We want to place (minimum number
of) trackers (or check points) at some specific intersections so that based
on the sequence of trackers a person has encountered, we can identify the
exact path traversed by the person. Motivated by such applications, we study
the Tracking Paths problem in this paper. Given an undirected graph with a
source s, a destination t and a non-negative integer k, the goal is to find a
set of vertices of size at most k, a tracking set, that intersects each s-t
path in a unique sequence. Such a set enables a central controller to track
all the paths from s to t. We first show that the problem is NP-complete.
Then we show that the finding a tracking set of size at most k is
fixed-parameter tractable (FPT) when parameterized by the solution size. More
specifically, given an undirected graph on n vertices and an integer k, we
give a polynomial time algorithm that either determines that the graph can
not be tracked by k trackers or produces an equivalent instance of size
O(k^7).

Paper by Aritra Banik, Pratibha Choudhary, Daniel Lokshtanov, Venkatesh
Raman, and Saket Saurabh.
https://www.ii.uib.no/~daniello/papers/trackingPathsLATIN18.pdf