Cover Image

Stronger Hardness for Maximum Robust Flow and Randomized Network Interdiction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Matuschke, Jannik
Format:	Preprint
Published:	2025
Subjects:	Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Robust Deterministic Policies for Markov Decision Processes under Budgeted Uncertainty
by: Wu, Fei, et al.
Published: (2024)

Randomized Max-Vertex-Cover Interdiction with Matroid Constraints
by: Wang, Changjun, et al.
Published: (2026)

Simultaneous Network Design with Restricted Link Usage
by: Kakimura, Naonori, et al.
Published: (2025)

Contribution to Blocker and Interdiction optimization problems in networks
by: Martin, Sébastien
Published: (2024)

Who Should Have a Place on the Ark? Parameterized Algorithms for the Maximization of Phylogenetic Diversity
by: Schestag, Jannik
Published: (2025)

Interdiction of minimum spanning trees and other matroid bases
by: Weninger, Noah, et al.
Published: (2024)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
by: Abbasi, Ali, et al.
Published: (2026)

Finding a Sparse Connected Spanning Subgraph in a non-Uniform Failure Model
by: Bentert, Matthias, et al.
Published: (2023)

Weighted Food Webs Make Computing Phylogenetic Diversity So Much Harder
by: Schestag, Jannik
Published: (2025)

On the Hardness of Gray Code Problems for Combinatorial Objects
by: Merino, Arturo, et al.
Published: (2024)

Semi-Random Graphs, Robust Asymmetry, and Reconstruction
by: Asilis, Julian, et al.
Published: (2025)

Constrained Flows in Networks
by: Bessy, Stéphane, et al.
Published: (2023)

A Scalable Lift-and-Project Differentiable Approach For the Maximum Cut Problem
by: Alkhouri, Ismail, et al.
Published: (2025)

Ensuring connectedness for the Maximum Quasi-clique and Densest $k$-subgraph problems
by: Santos, Daniela Scherer dos, et al.
Published: (2024)

Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach
by: Proença, Nathan Benedetto, et al.
Published: (2026)

Lower Bounds for Maximum Weighted Cut
by: Gutin, Gregory, et al.
Published: (2021)

Fast Reroute with Highly Connected Routes Based on Maximum Flow Evaluation
by: Okida, Leon, et al.
Published: (2024)

Chorded cycle facets of the clique partitioning polytope
by: Irmai, Jannik, et al.
Published: (2024)

Approximating the Network Design Problem for Potential-Based Flows
by: Klimm, Max, et al.
Published: (2026)

Pushing Cops and Robber on Graphs of Maximum Degree 4
by: Gahlawat, Harmender
Published: (2025)

Critical Thresholds for Maximum Cardinality Matching on General Hypergraphs
by: Sumnicht, Christopher, et al.
Published: (2024)

Maximum Eccentric Connectivity Index for Graphs with Given Diameter
by: Hauweele, Pierre, et al.
Published: (2018)

Flipping Matchings is Hard
by: Binucci, Carla, et al.
Published: (2025)

Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees
by: Gerke, Stefanie, et al.
Published: (2024)

RDNF Oriented Analytics to Random Boolean Functions
by: Aslanyan, Levon, et al.
Published: (2024)

Maximum rectilinear convex subsets
by: González-Aguilar, Hernán, et al.
Published: (2019)

Finding Minimum Matching Cuts in $H$-free Graphs
by: Lucke, Felicia, et al.
Published: (2025)

Box Facets and Cut Facets of Lifted Multicut Polytopes
by: Naumann, Lucas Fabian, et al.
Published: (2024)

First-Fit Coloring of Forests in Random Arrival Model
by: Bosek, Bartłomiej, et al.
Published: (2024)

Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
by: Friedrich, Tobias, et al.
Published: (2023)

On Euler Paths and the Maximum Degree Growth of Iterated Higher Order Line Graphs
by: Sanghi, Aryan, et al.
Published: (2026)

Tournament Robustness via Redundancy
by: Efremenko, Klim, et al.
Published: (2025)

Maximum Reachability Orientation of Mixed Graphs
by: Hörsch, Florian
Published: (2025)

The Labeled Coupon Collector Problem with Random Sample Sizes and Partial Recovery
by: Berrebi, Shoham Shimon, et al.
Published: (2025)

Robust Filter Design for Graph Signals
by: Testa, Lucia, et al.
Published: (2024)

Logarithmic Mixing of Random Walks on Dynamical Random Cluster Models
by: Galanis, Andreas, et al.
Published: (2026)

Three Hardness Results for Graph Similarity Problems
by: Sun, He, et al.
Published: (2023)

Euclidean Maximum Matchings in the Plane---Local to Global
by: Biniaz, Ahmad, et al.
Published: (2024)

Binomial Random Matroids
by: Bennett, Patrick, et al.
Published: (2026)

Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes
by: Choi, Mujin, et al.
Published: (2025)