Abstract
We consider parameterized complexity of the recently introduced problem of tracking paths in graphs, motivated by applications in security and wireless networks. Given an undirected and unweighted graph with a specified source s and a terminal t, the goal is to find a k-sized subset of vertices that intersect with each s-t path (or s-t shortest) path in a distinct sequence (or set).
We first generalize this problem to a problem on set systems with a universe of size n and a m sized family of subsets of the universe. Using a correspondence with the well-studied Test Cover Problem, we give a lower bound of \(\lg m\) for the solution size and show the problem fixed-parameter tractable. We also show that when k is the parameter, then for such a set system
-
finding a Tracking Set for such a set system of size at most \(\lg m +k\) is hard for parameterized complexity class W[2];
-
finding a Tracking Set of size at most \(m-k\) is fixed parameter tractable;
-
finding a Tracking Set of size at most \(n-k\) is complete for parameterized complexity class W[1].
Using the solution for the set system generalization, we show the main result of the paper that finding a Tracking Set of size at most k for shortest paths is fixed-parameter tractable. We first give an \(O^*(2^{k2^k})\) algorithm using the set system solution, which we later improve to \(O^*(2^{k^2})\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We use lg to denote logarithm to the base 2.
- 2.
\(O^*\) notation ignores polynomial factors.
References
Banik, A., Katz, M.J., Packer, E., Simakov, M.: Tracking paths. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 67–79. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57586-5_7
Bhatti, S., Xu, J.: Survey of target tracking protocols using wireless sensor network. In: Proceedings of the 2009 Fifth International Conference on Wireless and Mobile Communications, ICWMC 2009, Washington, D.C., pp. 110–115. IEEE Computer Society (2009)
De Bontridder, K.M.J., Halldórsson, B.V., Halldórsson, M.M., Hurkens, C.A.J., Lenstra, J.K., Ravi, R., Stougie, L.: Approximation algorithms for the test cover problem. Math. Program. 98(1–3), 477–491 (2003)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)
Crowston, R., Gutin, G., Jones, M., Muciaccia, G., Yeo, A.: Parameterizations of test cover with bounded test sizes. Algorithmica 74(1), 367–384 (2016)
Crowston, R., Gutin, G., Jones, M., Saurabh, S., Yeo, A.: Parameterized study of the test cover problem. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 283–295. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32589-2_27
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, 1st edn. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3
De Bontridder, K.M.J., Lageweg, B.J., Lenstra, J.K., Orlin, J.B., Stougie, L.: Branch-and-bound algorithms for the test cover problem. In: Möhring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 223–233. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45749-6_23
Ganesan, D., Cristescu, R., Beferull-Lozano, B.: Power-efficient sensor placement and transmission structure for data gathering under distortion constraints. ACM Trans. Sens. Netw. 2(2), 155–181 (2006)
Gutin, G., Muciaccia, G., Yeo, A.: (Non-)existence of polynomial kernels for the test cover problem. Inf. Process. Lett. 113(4), 123–126 (2013)
Halldórsson, B.V., Halldórsson, M.M., Ravi, R.: On the approximability of the minimum test collection problem. In: auf der Heide, F.M. (ed.) ESA 2001. LNCS, vol. 2161, pp. 158–169. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44676-1_13
Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335–354 (1999)
Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. Syst. Sci. 75(2), 137–153 (2009)
Moret, B.M.E., Shapiro, H.D.: On minimizing a set of tests. SIAM J. Sci. Stat. Comput. 6(4), 983–1003 (1985)
Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410–421 (1979)
Acknowledgments
We thank Venkatesh Raman and Saket Saurabh for fruitful discussions and valuable suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Banik, A., Choudhary, P. (2018). Fixed-Parameter Tractable Algorithms for Tracking Set Problems. In: Panda, B., Goswami, P. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2018. Lecture Notes in Computer Science(), vol 10743. Springer, Cham. https://doi.org/10.1007/978-3-319-74180-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-74180-2_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-74179-6
Online ISBN: 978-3-319-74180-2
eBook Packages: Computer ScienceComputer Science (R0)