Abstract
Consider mitigating the effects of denial of service or of malicious traffic in networks by deleting edges. Edge deletion reduces the DoS or the number of the malicious flows, but it also inadvertently removes some of the desired flows. To model this important problem, we formulate two problems: (1) remove all the undesirable flows while minimizing the damage to the desirable ones and (2) balance removing the undesirable flows and not removing too many of the desirable flows. We prove these problems are equivalent to important theoretical problems, thereby being important not only practically but also theoretically, and very hard to approximate in a general network. We employ reductions to nonetheless approximate the problem and also provide a greedy approximation. When the network is a tree, the problems are still MAX SNP-hard, but we provide a greedy-based 2l-approximation algorithm, where l is the longest desirable flow. We also provide an algorithm, approximating the first and the second problem within \(2 \sqrt{ 2\left| E \right| }\) and \(2 \sqrt{2 (\left| E \right| + \left| \text {undesirable flows} \right| )}\), respectively, where E is the set of the edges of the network. We also provide a fixed-parameter tractable (FPT) algorithm. Finally, if the tree has a root such that every flow in the tree flows on the path from the root to a leaf, we solve the problem exactly using dynamic programming.
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 remind that for a set of flows D and a set of edges S, we denote by D(S) the flows from D removed by deleting S.
References
Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discret. Math. 12(3), 289–297 (1999)
Bondy, J., Murty, U.: Graph Theory with Applications. Elsevier Science Publishing Co., Inc., New York (1976)
Carr, R.D., Doddi, S., Konjevod, G., Marathe, M.: On the red-blue set cover problem. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000, pp. 345–353. Society for Industrial and Applied Mathematics, Philadelphia (2000)
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)
Cygan, M., et al.: Parameterized Algorithms, 1st edn. Springer Publishing Company, Incorporated, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3
Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873–921 (1995). https://doi.org/10.1137/S0097539792228228
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)
Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 671–680, October 2009
Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. J. Algorithms 14(2), 214–225 (1993)
Koning, R., de Graaff, B., de Laat, C., Meijer, R., Grosso, P.: Interactive analysis of SDN-driven defence against distributed denial of service attacks. In: 2016 IEEE NetSoft Conference and Workshops (NetSoft), pp. 483–488, June 2016
Miettinen, P.: On the positive-negative partial set cover problem. Inf. Process. Lett. 108(4), 219–221 (2008)
Mirkovic, J., Dietrich, S., Dittrich, D., Reiher, P.: Internet Denial of Service: Attack and Defense Mechanisms (Radia Perlman Computer Networking and Security). Prentice Hall PTR, Upper Saddle River (2004)
Mirkovic, J., Reiher, P.: A taxonomy of DDoS attack and DDoS defense mechanisms. SIGCOMM Comput. Commun. Rev. 34(2), 39–53 (2004)
Peleg, D.: Approximation algorithms for the label-covermax and red-blue set cover problems. J. Discret. Algorithms 5(1), 55–64 (2007)
Vazirani, V.: Approximation Algorithms. Springer, Heidelberg (2001). https://doi.org/10.1007/978-3-662-04565-7
Watanabe, T., Ae, T., Nakamura, A.: On the removal of forbidden graphs by edge-deletion or by edge-contraction. Discret. Appl. Math. 3(2), 151–153 (1981)
Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 253–264. ACM, New York (1978)
Zargar, S.T., Joshi, J., Tipper, D.: A survey of defense mechanisms against distributed denial of service (DDoS) flooding attacks. IEEE Commun. Surv. Tutor. 15(4), 2046–2069 (2013, Fourth)
Acknowledgments
This research is funded by the Dutch Science Foundation project SARNET (grant no: CYBSEC.14.003/618.001.016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Polevoy, G., Trajanovski, S., Grosso, P., de Laat, C. (2018). Removing Undesirable Flows by Edge Deletion. In: Kim, D., Uma, R., Zelikovsky, A. (eds) Combinatorial Optimization and Applications. COCOA 2018. Lecture Notes in Computer Science(), vol 11346. Springer, Cham. https://doi.org/10.1007/978-3-030-04651-4_15
Download citation
DOI: https://doi.org/10.1007/978-3-030-04651-4_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-04650-7
Online ISBN: 978-3-030-04651-4
eBook Packages: Computer ScienceComputer Science (R0)