---
_id: '17651'
abstract:
- lang: eng
  text: '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 {\backslash}sqrt{\{}
    2{\backslash}left| E {\backslash}right| {\}}{\$}{\$}and {\$}{\$}2 {\backslash}sqrt{\{}2
    ({\backslash}left| E {\backslash}right| + {\backslash}left| {\backslash}text {\{}undesirable
    flows{\}} {\backslash}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.'
author:
- first_name: Gleb
  full_name: Polevoy, Gleb
  id: '83983'
  last_name: Polevoy
- first_name: Stojan
  full_name: Trajanovski, Stojan
  last_name: Trajanovski
- first_name: Paola
  full_name: Grosso, Paola
  last_name: Grosso
- first_name: Cees
  full_name: de Laat, Cees
  last_name: de Laat
citation:
  ama: 'Polevoy G, Trajanovski S, Grosso P, de Laat C. Removing Undesirable Flows
    by Edge Deletion. In: Kim D, Uma RN, Zelikovsky A, eds. <i>Combinatorial Optimization
    and Applications</i>. Cham: Springer International Publishing; 2018:217-232.'
  apa: 'Polevoy, G., Trajanovski, S., Grosso, P., &#38; de Laat, C. (2018). Removing
    Undesirable Flows by Edge Deletion. In D. Kim, R. N. Uma, &#38; A. Zelikovsky
    (Eds.), <i>Combinatorial Optimization and Applications</i> (pp. 217–232). Cham:
    Springer International Publishing.'
  bibtex: '@inproceedings{Polevoy_Trajanovski_Grosso_de Laat_2018, place={Cham}, title={Removing
    Undesirable Flows by Edge Deletion}, booktitle={Combinatorial Optimization and
    Applications}, publisher={Springer International Publishing}, author={Polevoy,
    Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees}, editor={Kim,
    Donghyun and Uma, R. N. and Zelikovsky, AlexanderEditors}, year={2018}, pages={217–232}
    }'
  chicago: 'Polevoy, Gleb, Stojan Trajanovski, Paola Grosso, and Cees de Laat. “Removing
    Undesirable Flows by Edge Deletion.” In <i>Combinatorial Optimization and Applications</i>,
    edited by Donghyun Kim, R. N. Uma, and Alexander Zelikovsky, 217–32. Cham: Springer
    International Publishing, 2018.'
  ieee: G. Polevoy, S. Trajanovski, P. Grosso, and C. de Laat, “Removing Undesirable
    Flows by Edge Deletion,” in <i>Combinatorial Optimization and Applications</i>,
    2018, pp. 217–232.
  mla: Polevoy, Gleb, et al. “Removing Undesirable Flows by Edge Deletion.” <i>Combinatorial
    Optimization and Applications</i>, edited by Donghyun Kim et al., Springer International
    Publishing, 2018, pp. 217–32.
  short: 'G. Polevoy, S. Trajanovski, P. Grosso, C. de Laat, in: D. Kim, R.N. Uma,
    A. Zelikovsky (Eds.), Combinatorial Optimization and Applications, Springer International
    Publishing, Cham, 2018, pp. 217–232.'
date_created: 2020-08-06T15:19:36Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
editor:
- first_name: Donghyun
  full_name: Kim, Donghyun
  last_name: Kim
- first_name: R. N.
  full_name: Uma, R. N.
  last_name: Uma
- first_name: Alexander
  full_name: Zelikovsky, Alexander
  last_name: Zelikovsky
extern: '1'
keyword:
- flow
- Red-Blue Set Cover
- Positive-Negative Partial Set Cover
- approximation
- tree
- MAX SNP-hard
- root
- leaf
- dynamic programming
- FPT
language:
- iso: eng
page: 217-232
place: Cham
publication: Combinatorial Optimization and Applications
publication_identifier:
  isbn:
  - 978-3-030-04651-4
publisher: Springer International Publishing
status: public
title: Removing Undesirable Flows by Edge Deletion
type: conference
user_id: '83983'
year: '2018'
...