2017/11/02 by Thomas Ridremont, Ridremont, Thomas, Dimitri Watel +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1711.00831
openalex publication_date 2017/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.