Options
A polynomial sized kernel for tracking paths problem
ISSN
03029743
Date Issued
2018-01-01
Author(s)
Banik, Aritra
Choudhary, Pratibha
Lokshtanov, Daniel
Raman, Venkatesh
Saurabh, Saket
DOI
10.1007/978-3-319-77404-6_8
Abstract
Consider a secure environment (say an airport) that has a unique entry and exit point with multiple inter-crossing 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 at most k vertices, 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 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 cannot be tracked by k trackers or produces an equivalent instance of size O(k7).