Parameterized Complexity of Tracking Paths.
Loading...
Date
2020-07
Researcher
Choudhary, Pratibha
Supervisor
Banik, Aritra
Journal Title
Journal ISSN
Volume Title
Publisher
Indian Institute of Technology Jodhpur
Abstract
Tracking of moving objects has been a subject of study in fields like networking, security and machine learning. While a majority of research carried out in this regard is heuristics based,in this thesis we study the problem from a graph theoretic perspective. Tracking/Distinguishing problems aim at identifying a preferably small set of entities that can help distinguish between objects in a family. The focus of this thesis is on distinguishing paths between a designated source-destination pair in a graph. The goal is to identify a small set of vertices that can help distinguish simple paths between a source and a destination in a graph. We study two variants of the problem, namely Tracking Paths and Tracking Shortest Paths. While the first focuses on distinguishing all source-destination paths in a graph, the latter deals with distinguishing all shortest source-destination paths in a graph. Formally, Tracking Paths (resp. Tracking Shortest Paths) requires finding a small set of vertices (referred to as tracking set), such that the intersection with each source-destination path (resp. shortest source-destination path) with this set results in a unique sequence (resp. set).Both Tracking Paths and Tracking Shortest Paths are NP-hard problems, i.e.,under standard complexity theoretic assumptions, it is not expected to find polynomial time algorithms for these problems. Parameterized complexity is one of the many approaches used to tackle NP-hard problems. While classical complexity judges the hardness of a problem by the dependence of its algorithm on the input size of the problem alone, parameterized complexity does a multivariate analysis of the problem by studying the dependence of algorithms for solving problems on other parameters as well would be related to the problem at hand. Thus, in general parameterized analysis of a problem involves studying the problem with respect to its input size as well as some parameter(s). The algorithms whose running time is a function of some parameter (related to the problem) and have a polynomial dependence on the input size are known as fixed-parameter tractable (FPT) algorithms, and problems that admit such algorithms are said to belong to the complexity class FPT. A common approach to derive an FPT algorithm is through kernelization, which involves reducing a problem to an equivalent instance such that the size of the reduced instance is a function of the parameter alone. This thesis provides results for Tracking Shortest Paths and Tracking Paths that involve parameterized analysis of these problems along with polynomial time solutions for some restricted cases of the problem.Prior to our work, Tracking Shortest Paths was known to be NP-hard and APX-hard.We prove that Tracking Shortest Paths is fixed parameter tractable when parameterized by the output size, that is the size of a desired tracking set, by providing a kernel for the problem. While doing so, we also prove that Tracking Paths is FPT for directed acyclic graphs. We provide an improved FPT algorithm for Tracking Shortest Paths for the case when the graph diameter is bounded by a constant. While studying Tracking Shortest Paths, it was found that the problem is closely related to a combinatorial generalization, where the goal is to distinguish between sets of a family. Given a set system consisting of a set of elements and a family of subsets of these elements, the Tracking Set System problem asks for a set of elements that has a unique intersection with each set in the family. The problem was proven to be FPT, and we also provide an improved algorithm for the case when the set sizes are upper bounded by a constant.We initiate the study of Tracking Paths. The analysis of the problem starts by first showing it NP-complete by proving it NP-hard and by providing a polynomial time verification algorithm for a solution. We prove the problem fixed-parameter tractable by giving a polynomial kernel when the parameter is the output size. This is achieved by proving the connection of Tracking Paths with the problem of finding a feedback vertex set (set of vertices whose removal makes a graph acyclic), and some observations related to vertex disjoint paths. Next we improve this result by showing the existence of a quadratic kernel, through a more involved analysis of the problem. We also show that planar graphs admit a linear kernel when parameterized by the output size. For a graph, the set of all vertices forms a tracking set. Thus for a graph with n vertices, the size of a tracking set is upper bounded by n. In order to analyze solutions with respect to distance to triviality, we study the problem of finding a tracking set of n−k where n is the number of vertices in the graph and k is a positive integer. We show that it is W[1]-hard to solve this problem.In parameterized complexity, it is natural to study problems with respect to multiple parameters. Studying parameterized problems in graphs with respect to parameters related to the graph structure is known as Structural Parameterization. Moving beyond the intuitive parameter,that is the size of output, we also analyze Tracking Paths with respect to other graph parameters,namely, the size of a minimum vertex cover and the size of a minimum cluster vertex deletion set.We show that Tracking Paths is FPT when parameterized by these parameters. We also give some polynomial time results for the problem. We prove that Tracking Paths is polynomial time solvable for chordal graphs (graphs in which each cycle of length more than 4 has a chord). We also give a 2(! +1)-approximate algorithm for the case when the degree of vertices in a graph is upper bounded by a constant ! . Finally, as an alternative to using vertices as trackers, we consider the problem for the case when edges are to be used as trackers. Towards this, we show that Tracking Paths is polynomial time solvable when edges are used as trackers instead of vertices.
Description
Keywords
Citation
Choudhary, Pratibha. (2020). Parameterized Complexity of Tracking Paths (Doctor's thesis). Indian Institute of Technology Jodhpur, Jodhpur.