Fixed-parameter tractable algorithms for tracking shortest paths. (English) Zbl 1464.68274
Summary: 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 in solving Tracking Shortest Paths when the input graph diameter is bounded by \(d\). While the results for Tracking Set System 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.
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 in solving Tracking Shortest Paths when the input graph diameter is bounded by \(d\). While the results for Tracking Set System 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.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C38 | Paths and cycles |
| 68Q27 | Parameterized complexity, tractability and kernelization |
Keywords:
graphs; shortest \(s\)-\(t\) paths; tracking paths; fixed-parameter tractable; kernel; set systemsReferences:
| [1] | Banik, A.; Choudhary, P., Fixed-parameter tractable algorithms for tracking set problems, (Algorithms and Discrete Applied Mathematics - Proceedings of 4th International Conference. Algorithms and Discrete Applied Mathematics - Proceedings of 4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018 (2018)), 93-104 · Zbl 1497.68364 |
| [2] | Bhatti, S.; Xu, J., Survey of target tracking protocols using wireless sensor network, (Proceedings of the 2009 Fifth International Conference on Wireless and Mobile Communications. Proceedings of the 2009 Fifth International Conference on Wireless and Mobile Communications, ICWMC ’09 (2009), IEEE Computer Society), 110-115 |
| [3] | 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) |
| [4] | Banik, A.; Katz, M. J.; Packer, E.; Simakov, M., Tracking paths, (10th International Conference on Algorithms and Complexity (2017)), 67-79 · Zbl 1468.68144 |
| [5] | Banik, A.; Choudhary, P.; Lokshtanov, D.; Raman, V.; Saurabh, S., A polynomial sized kernel for tracking paths problem, Algorithmica, 2019 (Jul. 2019) |
| [6] | Choudhary, P.; Raman, V., Improved kernels for tracking path problems (2020), CoRR |
| [7] | Karp, R. M., Reducibility among combinatorial problems, (Proceedings of a Symposium on the Complexity of Computer Computations, Held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA (1972)), 85-103 · Zbl 1467.68065 |
| [8] | Henning, M. A.; Yeo, A., Identifying vertex covers in graphs, Electron. J. Comb., 19, 4, P32 (2012) · Zbl 1266.05118 |
| [9] | Masuyama, S.; Ibaraki, T., Chain packing in graphs, Algorithmica, 6, 6, 826-839 (1991) · Zbl 0731.68088 |
| [10] | Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer Publishing Company, Incorporated · Zbl 1334.90001 |
| [11] | Bazgan, C.; Foucaud, F.; Sikora, F., Parameterized and approximation complexity of partial VC dimension, Theor. Comput. Sci., 766, 1-15 (2019) · Zbl 1417.68059 |
| [12] | Crowston, R.; Gutin, G. Z.; Jones, M.; Saurabh, S.; Yeo, A., Parameterized study of the test cover problem, (Mathematical Foundations of Computer Science 2012 - Proceedings of 37th International Symposium. Mathematical Foundations of Computer Science 2012 - Proceedings of 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012 (2012)), 283-295 · Zbl 1365.68275 |
| [13] | Henning, M. A.; Yeo, A., Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs, Graphs Comb., 30, 4, 909-932 (2014) · Zbl 1298.05236 |
| [14] | Charbit, E.; Charon, I.; Cohen, G. D.; Hudry, O.; Lobstein, A., Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity, Adv. Math. Commun., 2, 403-420 (2008) · Zbl 1180.05055 |
| [15] | Blass, U.; Honkala, I. S.; Litsyn, S., On the size of identifying codes, (Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proceedings of 13th International Symposium. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proceedings of 13th International Symposium, AAECC-13, Honolulu, Hawaii, USA, November 15-19, 1999 (1999)), 142-147 · Zbl 0981.94048 |
| [16] | Karpovsky, M. G.; Chakrabarty, K.; Levitin, L. B., On a new class of codes for identifying vertices in graphs, IEEE Trans. Inf. Theory, 44, 2, 599-611 (1998) · Zbl 1105.94342 |
| [17] | Moncel, J., Codes Identifants dans les Graphes (2005), Universite Joseph Fourier Grenoble I, France, Ph.D. thesis |
| [18] | Eppstein, D.; Goodrich, M. T.; Liu, J. A.; Matias, P., Tracking paths in planar graphs, (30th International Symposium on Algorithms and Computation. 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019 (2019), Shanghai University of Finance and Economics: Shanghai University of Finance and Economics Shanghai, China), 54:1-54:17 · Zbl 07650287 |
| [19] | Bilò, D.; Gualà, L.; Leucci, S.; Proietti, G., Tracking routes in communication networks, (Censor-Hillel, K.; Flammini, M., Structural Information and Communication Complexity (2019), Springer International Publishing: Springer International Publishing Cham), 81-93 · Zbl 1534.68012 |
| [20] | Choudhary, P., Polynomial time algorithms for tracking path problems, (Combinatorial Algorithms - Proceedings of 31st International Workshop. Combinatorial Algorithms - Proceedings of 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020. Combinatorial Algorithms - Proceedings of 31st International Workshop. Combinatorial Algorithms - Proceedings of 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020, Lecture Notes in Computer Science, vol. 12126 (2020), Springer), 166-179 · Zbl 1537.68127 |
| [21] | Choudhary, P., Polynomial time algorithms for tracking path problems (2020), CoRR · Zbl 1537.68127 |
| [22] | Abu-Khzam, F. N., A kernelization algorithm for d-hitting set, J. Comput. Syst. Sci., 76, 7, 524-531 (2010) · Zbl 1197.68083 |
| [23] | Niedermeier, R.; Rossmanith, P., An efficient fixed-parameter algorithm for 3-hitting set, J. Discret. Algorithms, 1, 1, 89-102 (2003) · Zbl 1118.68511 |
| [24] | Downey, R. G.; Fellows, M. R., Parameterized Complexity, Monographs in Computer Science (1999), Springer · Zbl 0914.68076 |
| [25] | Bontridder, K. M.J. D.; Lageweg, B. J.; Lenstra, J. K.; Orlin, J. B.; Stougie, L., Branch-and-bound algorithms for the test cover problem, (Algorithms - ESA 2002, Proceedings of 10th Annual European Symposium. Algorithms - ESA 2002, Proceedings of 10th Annual European Symposium, Rome, Italy, September 17-21, 2002 (2002)), 223-233 · Zbl 1019.68807 |
| [26] | Bontridder, K. M.J. D.; 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) · Zbl 1160.90646 |
| [27] | Halldórsson, B. V.; Halldórsson, M. M.; Ravi, R., On the approximability of the minimum test collection problem, (Algorithms - ESA 2001, Proceedings of 9th Annual European Symposium. Algorithms - ESA 2001, Proceedings of 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001 (2001)), 158-169 · Zbl 1006.68958 |
| [28] | Moret, B. M.E.; Shapiro, H. D., On minimizing a set of tests, SIAM J. Sci. Stat. Comput., 6, 4, 983-1003 (1985) |
| [29] | Gutin, G.; Muciaccia, G.; Yeo, A., (Non-)existence of polynomial kernels for the test cover problem, Inf. Process. Lett., 113, 4, 123-126 (2013) · Zbl 1259.68093 |
| [30] | Crowston, R.; Gutin, G.; Jones, M.; Muciaccia, G.; Yeo, A., Parameterizations of test cover with bounded test sizes, Algorithmica, 74, 1, 367-384 (2016) · Zbl 1336.68120 |
| [31] | Bondy, J., Induced subsets, J. Comb. Theory, Ser. B, 12, 2, 201-202 (1972) · Zbl 0211.56901 |
| [32] | Mahajan, M.; Raman, V., Parameterizing above guaranteed values: maxsat and maxcut, J. Algorithms, 31, 2, 335-354 (1999) · Zbl 0921.68052 |
| [33] | Mahajan, M.; Raman, V.; Sikdar, S., Parameterizing above or below guaranteed values, J. Comput. Syst. Sci., 75, 2, 137-153 (2009) · Zbl 1155.68400 |
| [34] | Krithika, R.; Narayanaswamy, N. S., Parameterized algorithms for (r, l)-partization, J. Graph Algorithms Appl., 17, 2, 129-146 (2013) · Zbl 1260.05164 |
| [35] | Valiant, L. G., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 3, 410-421 (1979) · Zbl 0419.68082 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
