Adaptive network flow with $k$-Arc Destruction

Thomas Ridremont (1) , Dimitri Watel (2, 3) , Pierre-Louis Poirion (4) , Christophe Picouleau (1)

1 CEDRIC - OC - CEDRIC. Optimisation Combinatoire
2 METHODES-SAMOVAR - Méthodes et modèles pour les réseaux
3 ENSIIE - Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise
4 Huawei Technologies France

When a flow is not allowed to be reoriented the Maximum Residual Flow Problem with $k$-Arc Destruction is known to be $NP$-hard for $k=2$. We show that when a flow is allowed to be adaptive the problem becomes polynomial for every fixed $k$.

Mots clés: Adaptive flow; Maximum flow; Linear program; Complexity

Domaines: Algorithme et structure de données [cs.DS]; Mathématique discrète [cs.DM]; Combinatoire [math.CO]; Informatique [cs]

Thomas Ridremont, Dimitri Watel, Pierre-Louis Poirion, Christophe Picouleau. Adaptive network flow with $k$-Arc Destruction. 2020. ⟨hal-02440948⟩