Fixed-parameter tractable algorithms for tracking shortest paths
From MaRDI portal
Publication:2210499
Abstract: We consider the parameterized complexity of the problem of tracking shortest s-t paths in graphs, motivated by applications in security and wireless networks. Given an undirected and unweighted graph with a source s and a destination t, Tracking Shortest Paths asks if there exists a k-sized subset of vertices (referred to as tracking set) that intersects each shortest s-t path in a distinct set of vertices. We first generalize this problem for set systems, namely Tracking Set System, where given a family of subsets of a universe, we are required to find a subset of elements from the universe that has a unique intersection with each set in the family. Tracking Set System is shown to be fixed-parameter tractable due to its relation with a known problem, Test Cover. By a reduction to the well-studied d-hitting set problem, we give a polynomial (with respect to k) kernel for the case when the set sizes are bounded by d. This also helps solving Tracking Shortest Paths when the input graph diameter is bounded by d. While the results for Tracking Set System help to show that Tracking Shortest Paths is fixed-parameter tractable, we also give an independent algorithm by using some preprocessing rules, resulting in an improved running time.
Recommendations
- Polynomial time algorithms for tracking path problems
- Polynomial Time Algorithms for Tracking Path Problems
- Fixed-parameter tractable algorithms for tracking set problems
- A linear fixed parameter tractable algorithm for connected pathwidth
- scientific article; zbMATH DE number 7651203
- Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
- Structural parameterizations of Tracking Paths problem
- On dynamic shortest paths problems
- Algorithms – ESA 2004
- Shortest paths algorithms: Theory and experimental evaluation
Cites work
- (Non-)existence of polynomial kernels for the test cover problem
- A kernelization algorithm for \(d\)-hitting set
- An efficient fixed-parameter algorithm for 3-hitting set
- Approximation algorithms for the test cover problem
- Chain packing in graphs
- Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
- Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
- Fixed-parameter tractable algorithms for tracking set problems
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1947395 (Why is no real title available?)
- scientific article; zbMATH DE number 1504659 (Why is no real title available?)
- scientific article; zbMATH DE number 1875415 (Why is no real title available?)
- scientific article; zbMATH DE number 7650287 (Why is no real title available?)
- Identifying vertex covers in graphs
- Induced subsets
- On a new class of codes for identifying vertices in graphs
- Parameterizations of test cover with bounded test sizes
- Parameterized algorithms
- Parameterized algorithms for (r,l)-partization
- Parameterized study of the test cover problem
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterizing above or below guaranteed values
- Polynomial Time Algorithms for Tracking Path Problems
- Reducibility among combinatorial problems
- The Complexity of Enumeration and Reliability Problems
- Tracking paths
- Tracking routes in communication networks
Cited in
(15)- Structural parameterizations of Tracking Paths problem
- Polynomial kernels for tracking shortest paths
- Polynomial time algorithms for tracking path problems
- Tracking paths
- Fixed-parameter tractable algorithms for tracking set problems
- Improved kernels for tracking paths
- Tracking paths
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- Tracking routes in communication networks
- A polynomial sized kernel for tracking paths problem
- Tracking routes in communication networks
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- A polynomial sized kernel for tracking paths problem
- Parameterized algorithms and data reduction for safe convoy routing
- The parameterized complexity of maximum betweenness centrality
This page was built for publication: Fixed-parameter tractable algorithms for tracking shortest paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2210499)
