mlsanityData to 14 Oct 2026

ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation

arXiv 2102.06635 ↗First posted 12 Feb 2021cs.LG cs.CC cs.DScited by 12

Not on the map. Why?

Abstract (arXiv)

This paper studies the expressive power of artificial neural networks with rectified linear units. In order to study them as a model of real-valued computation, we introduce the concept of Max-Affine Arithmetic Programs and show equivalence between them and neural networks concerning natural complexity measures. We then use this result to show that two fundamental combinatorial optimization problems can be solved with polynomial-size neural networks. First, we show that for any undirected graph with n nodes, there is a neural network (with fixed weights and biases) of size O(n3) that takes the edge weights as input and computes the value of a minimum spanning tree of the graph. Second, we show that for any directed graph with n nodes and m arcs, there is a neural network of size O(m2n2) that takes the arc capacities as input and computes a maximum flow. Our results imply that these two problems can be solved with strongly polynomial time algorithms that solely use affine transformations and maxima computations, but no comparison-based branchings.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 24 of its 83 references that are in the map. First posted on arXiv 12 Feb 2021.

Builds on

24 of 83 references.

References · 24

  1. 2015Pointer Networkscited by 895
  2. 2018Attention, Learn to Solve Routing Problems!cited by 656
  3. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  4. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  5. 2016Error bounds for approximations with deep ReLU networkscited by 574
  6. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  7. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  8. 2016On the Expressive Power of Deep Neural Networkscited by 306
  9. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  10. 2016Benefits of depth in neural networkscited by 250
  11. 2015The Power of Depth for Feedforward Neural Networkscited by 183
  12. 2019Complexity of Linear Regions in Deep Networkscited by 167
12 more
  1. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  2. 2017Approximating Continuous Functions by ReLU Nets of Minimal Widthcited by 122
  3. 2017Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activationscited by 104
  4. 2015Representation Benefits of Deep Feedforward Networkscited by 86
  5. 2016Why Deep Neural Networks for Function Approximation?cited by 82
  6. 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 59
  7. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  8. 2018Learning Permutations with Sinkhorn Policy Gradientcited by 26
  9. 2017Lower bounds over Boolean inputs for deep neural networks with ReLU gatescited by 21
  10. 2018Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regionscited by 17
  11. 2020Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Sizecited by 16
  12. 2019Smoothing the gap between NP and ERcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 3; 2025: 4; 2026: 2.

12 papers.

  1. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  2. 2024Looped ReLU MLPs May Be All You Need as Practical Programmable Computerscited by 19
  3. 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
  4. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  5. 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
  6. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  7. 2024Neural Networks and (Virtual) Extended Formulationscited by 9
  8. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  9. 2025Arithmetic Circuits and Neural Networks for Regular Matroidscited by 2
  10. 2025On the expressivity of sparse maxout networkscited by 0
  11. 2026Tropical Circuits with Scalar Multiplication Gatescited by 0
  12. 2026Two Linear Programs are Better than Onecited by 0