Open
0–1 Maximum Flow (0–1 MaxFlow)
Category: Network Flows
Problem List
All 192 problems, searchable and filterable.
Category
Status
Tags
Showing 192 of 192 problems
Open
One Left-linear Semi-unification (1LLSU)
Category: Searching Graphs
P-complete
Two-way DPDA Acceptance (2DPDA)
Category: Formal Languages
Open
2-Oriented Weighted Planar Partitioning (2OWPP)
Category: Logic
P-complete
3-Oriented Weighted Planar Partitioning (3OWPP)
Category: Geometry
P-complete
Alternating Breadth-first Search (ABFS)
Category: Searching Graphs
P-complete
Average Cost Markov Decision Process (ACMDP)
Category: Algebra
P-complete
Alternating Graph Accessibility Problem (AGAP)
Category: Graph Theory
P-complete
Acyclic Geography Game (AGG)
Category: Games
P-complete
Alternating Monotone Fanin 2, Fanout 2 CVP (AM2CVP)
Category: Circuit Complexity
P-complete
Aperiodic Monoid Membership Variety $B_2$ (AMonMEMB)
Category: Algebra
P-complete
Andersen's Pointer Analysis (APA)
Category: Formal Languages
P-hard
Arithmetic Circuit Value Problem (ArithCVP)
Category: Circuit Complexity
Open
Bounded Degree Graph Isomorphism (BDGI)
Category: Circuit Complexity
P-complete
Breadth-depth Search (BDS)
Category: Searching Graphs
Open
Blocking Flow in a Three Layered Network (BF3)
Category: Network Flows
P-complete
Boolean Recurrence Equation (BRE)
Category: Algebra
P-complete
One Dimensional Cellular Automata (CA)
Category: Miscellaneous
Open
Comparator Circuit Value Problem (CCVP)
Category: Matching
P-complete
Circuit Evaluation over Monoids (CEM)
Category: Circuit Complexity
P-complete
Context-free Grammar Empty (CFGempty)
Category: Formal Languages
P-complete
Context-free Grammar Infinite (CFGinf)
Category: Formal Languages
P-complete
Context-free Grammar Membership (CFGmem)
Category: Formal Languages
P-complete
Context-free Grammar ϵ-Membership (CFGϵmem)
Category: Formal Languages
Open
Canonical Labeling Well-founded Extensional Relation (CLWER)
Category: Searching Graphs
P-complete
Cat and Mouse (CM)
Category: Games
P-hard
Two Layer Channel Router Column-swap Heuristic (COLUMNS)
Category: Local Optimality
P-complete
Conjugate Subgroups (CS)
Category: Algebra
P-complete
Forward Deterministic Growing Context-sensitive Grammar Membership (CSGmem)
Category: Formal Languages
P-hard
Cellular Tree Automaton Acceptance (CTAA)
Category: Formal Languages
P-complete
Corporate Takeover Query (CTQ)
Category: Logic
P-complete
Circuit Value Problem (CVP)
Category: Circuit Complexity
Open
Directed or Undirected Depth-first Search (DFS)
Category: Network Flows
P-complete
Discounted Markov Decision Process (DMDP)
Category: Algebra
Open
Edge Coloring (EC)
Category: Network Flows
P-complete
Eden Growth (EG)
Category: Miscellaneous
P-complete
Edge Maximal Acyclic Subgraph (EMAS)
Category: Graph Theory
Open
Edge Ranking (ER)
Category: Circuit Complexity
Open
Edge-weighted Matching (EWM)
Category: Circuit Complexity
Open
Extended Euclidean Algorithm (ExtendedGCD)
Category: Local Optimality
P-complete
First Fit Decreasing Bin Packing (FFDBP)
Category: Combinatorial Optimization
P-complete
Finitely Generated Subalgebra (FGS)
Category: Algebra
P-complete
Finite Horizon Markov Decision Process (FHMDP)
Category: Algebra
P-complete
Fill Slots (FILL)
Category: Algebra
P-complete
Fluid Invasion (FLUID)
Category: Miscellaneous
P-complete
Finitely Presented Algebras Finiteness (FPAF)
Category: Algebra
P-complete
Finitely Presented Algebras Triviality (FPAT)
Category: Algebra
P-hard
Fixed Points of Contraction Mappings (FPCM)
Category: Real Analysis
P-complete
Two Player Game (GAME)
Category: Games
P-complete
Greedy Alphabet Reducing (GAR)
Category: Miscellaneous
P-complete
Graph Closure (GC)
Category: Circuit Complexity
P-complete
Group Coset Equality (GCE)
Category: Algebra
P-complete
General Deadlock Detection (GDD)
Category: Miscellaneous
P-complete
Greedy Dominating Set (GDS)
Category: Graph Theory
P-complete
Generability (GEN)
Category: Logic
P-complete
Gaussian Elimination with Partial Pivoting (GEPP)
Category: Algebra
Open
Gaussian Elimination with Partial Pivoting over Finite Fields (GEPPFF)
Category: Local Optimality
P-complete
General Graph Closure (GGC)
Category: Graph Theory
P-complete
Group Independence (GI)
Category: Algebra
P-complete
Group Induced Isomorphism (GII)
Category: Algebra
P-complete
General List Scheduling (GLS)
Category: Combinatorial Optimization
P-complete
Generic Machine Simulation Problem (GMSP)
Category: Miscellaneous
P-complete
Group Rank (GR)
Category: Algebra
P-complete
Generating Random Matchings (GRM)
Category: Graph Theory
P-complete
Generalized Word Problem (GWP)
Category: Algebra
P-complete
High Connectivity Subgraph (HCS)
Category: Graph Theory
P-complete
Homologous Flow (HF)
Category: Combinatorial Optimization
P-complete
Hierarchical Graph Accessibility Problem (HGAP)
Category: Graph Theory
P-complete
Horn Unit Resolution (HORN)
Category: Logic
P-complete
Height-priority Schedule (HPS)
Category: Combinatorial Optimization
P-complete
Intersection of Cosets (IC)
Category: Algebra
P-hard
Inverting An Injective Real Function (IIRF)
Category: Real Analysis
P-complete
Iterated Mod (IM)
Category: Algebra
Open
Integer Greatest Common Divisor (IntegerGCD)
Category: Local Optimality
P-hard
Inverting An NC⁰ Permutation (InvNC0Perm)
Category: Circuit Complexity
P-complete
Intersection of Subgroups (IS)
Category: Algebra
P-hard
Iterative Tree Array Acceptance (ITAA)
Category: Formal Languages
P-complete
Incomplete Table Recovery (ITR)
Category: Logic
P-complete
k-Core (k-Core)
Category: Graph Theory
P-complete
k-Truss (k-Truss)
Category: Graph Theory
P-complete
KL-Dcore (KL-Dcore)
Category: Graph Theory
Open
Low Degree Subgraph (LDS)
Category: Circuit Complexity
P-complete
Linear Equalities (LE)
Category: Combinatorial Optimization
Open
Lexicographically First Maximal Three-cycle Free Edge Induced Subgraph (LF3Edge)
Category: Circuit Complexity
P-complete
Lexicographically First Blocking Flow (LFBF)
Category: Combinatorial Optimization
P-complete
Lexicographically First Depth-first Search Ordering (LFDFS)
Category: Searching Graphs
P-complete
Lexicographically First Different Than Majority Labeling (LFDTML)
Category: Local Optimality
P-complete
Lexicographically First ∆ + 1 Vertex Coloring (LFDVC)
Category: Graph Theory
P-complete
Lexicographically First Maximal k-cycle Free Edge Induced Subgraph (LFEdge)
Category: Graph Theory
P-hard
Lexicographically First Maximal 3 Sums (LFM3S)
Category: Combinatorial Optimization
P-complete
Lexicographically First Maximal Clique (LFMC)
Category: Graph Theory
P-complete
Lexicographically First Maximal Independent Set (LFMIS)
Category: Graph Theory
Open
Lexicographically First Maximal Matching (LFMM)
Category: Matching
P-complete
Lexicographically First Maximal Path (LFMP)
Category: Searching Graphs
P-complete
Lexicographically First Maximal Subgraph for π (LFMS(π))
Category: Graph Theory
Open
Witness for Unambiguous Finite Automata (LFWITNESS)
Category: Combinatorial Optimization
P-complete
Lattice Generators (LG)
Category: Algebra
P-complete
Labeled GAP (LGAP)
Category: Formal Languages
P-complete
Linear Inequalities (LI)
Category: Combinatorial Optimization
P-complete
Game of Life (LIFE)
Category: Games
P-complete
Left-linear Semi-unification (LLSU)
Category: Logic
P-complete
Local Optimality Kernighan-Lin Verification (LOKL V)
Category: Local Optimality
P-complete
Longcake (LONGCAKE)
Category: Games
P-hard
Linear Programming (LP)
Category: Combinatorial Optimization
P-complete
Logical Query Program (LQP)
Category: Logic
Open
Limited Reflection Ray Tracing (LRRT)
Category: Logic
Open
LU Decomposition (LUD)
Category: Local Optimality
P-complete
Lempel-Ziv Data Compression (LZDC)
Category: Miscellaneous
P-complete
MAXFLIP Verification (MAXFLIPV)
Category: Local Optimality
P-complete
Maximum Flow (MaxFlow)
Category: Combinatorial Optimization
P-complete
Monotone Circuit Value Problem (MCVP)
Category: Circuit Complexity
Open
Maximum Disjoint Paths (MDP)
Category: Network Flows
P-complete
Minimum Feedback Vertex Set (MFVS)
Category: Graph Theory
P-complete
Min-plus Circuit Value Problem (MinPlusCVP)
Category: Circuit Complexity
Open
Maximal Independent Set Hypergraph (MISH)
Category: Circuit Complexity
P-complete
Monadic Krom Satisfiability (MKS)
Category: Logic
P-complete
Multi-list Ranking (MLR)
Category: Algebra
Open
Maximum Matching (MM)
Category: Network Flows
Open
Modular Inversion (ModInverse)
Category: Local Optimality
Open
Modular Powering (ModPower)
Category: Local Optimality
P-complete
Mostowski Epimorphism (MostEpi)
Category: Logic
Open
Maximal Path (MP)
Category: Network Flows
P-complete
Maximum Satisfiability Approximation (MSA)
Category: Local Optimality
P-complete
Minimum Set Cover Approximation (MSCA)
Category: Local Optimality
P-complete
Multivalued Dependency (MVD)
Category: Logic
P-complete
NAND Circuit Value Problem (NANDCVP)
Category: Circuit Complexity
P-complete
Nonempty k-Core (NE-k-Core)
Category: Graph Theory
P-complete
Network Simulation (NetSim)
Category: Miscellaneous
P-complete
Nearest Neighbor Traveling Salesman Heuristic (NNTSH)
Category: Graph Theory
P-complete
Neighborhood Removal (NR)
Category: Graph Theory
P-complete
Ordered High Degree Vertex Removal (OHDVR)
Category: Graph Theory
P-complete
Ordered Low Degree Vertex Removal (OLDVR)
Category: Graph Theory
Open
Optimal Two Variable Integer Linear Programming (Opt2ILP)
Category: Graph Theory
P-complete
Ordered Vertices Remaining (OVR)
Category: Graph Theory
P-complete
Path Systems (PATH)
Category: Logic
P-complete
Maximal Vertex Disjoint Paths (PATHS)
Category: Searching Graphs
P-complete
Planar Circuit Value Problem (PCVP)
Category: Circuit Complexity
P-complete
Two-person Pebble Game Fixed Rank (PEBBLE)
Category: Games
P-complete
Propositional Horn Clause Satisfiability (PHCS)
Category: Logic
P-complete
Point Location on A Convex Hull (PHULL)
Category: Geometry
Open
Perfect Matching Existence (PME)
Category: Network Flows
Open
Polynomial Root Approximation (PRA)
Category: Formal Languages
P-complete
Propagating Set Systems (PSS)
Category: Formal Languages
P-complete
Plane Sweep Triangulation (PST)
Category: Geometry
P-complete
Restricted Chromatic Alternating Graph Accessibility Problem (RCAGAP)
Category: Graph Theory
P-complete
Reliable Connectivity for Failures of Incoming Edges (RCIN)
Category: Graph Theory
P-complete
Relaxed Consistent Labeling (RCL)
Category: Logic
P-complete
Relation Coarsest Set Partition (RCSP)
Category: Formal Languages
P-hard
Real Analogue to CVP (RealCVP)
Category: Real Analysis
Open
Relative Primeness (RelPrime)
Category: Local Optimality
Open
Restricted Lexicographically First Maximal Independent Set (RLFMIS)
Category: Circuit Complexity
P-complete
Synchronous Alternating Monotone Fanout 2 CVP (SAM2CVP)
Category: Circuit Complexity
Open
Strong Bisimilarity in Deterministic Transition Systems (SBDTS)
Category: Combinatorial Optimization
P-complete
Stack Breadth-first Search (SBFS)
Category: Searching Graphs
P-complete
Strong Bisimilarity in Transition Systems (SBTS)
Category: Formal Languages
P-complete
Subgroup Containment (SC)
Category: Algebra
P-hard
Stable Configuration in Connectionist Model (SCCM)
Category: Local Optimality
P-complete
Successive Convex Hulls (SCH)
Category: Geometry
P-complete
Subgroup Equality (SE)
Category: Algebra
P-complete
Subgroup Finite Index (SFI)
Category: Algebra
P-complete
Iterated Shuffle (SHUF)
Category: Formal Languages
P-complete
Group Isomorphism (SI)
Category: Algebra
P-complete
Straight-line Program Membership (SLPmem)
Category: Formal Languages
P-complete
Straight-line Program Nonempty (SLPnonempty)
Category: Formal Languages
Open
Stable Marriage (SM)
Category: Matching
Open
Stable Marriage Fixed Pair (SMFP)
Category: Matching
Open
Stable Marriage Minimum Regret (SMMR)
Category: Matching
Open
Stable Marriage Stable Pair (SMSP)
Category: Matching
Open
Subtree Isomorphism (STI)
Category: Network Flows
Open
Short Vectors (SV)
Category: Formal Languages
Open
Short Vectors Dimension 2 (SV2)
Category: Formal Languages
Open
Restricted Plane Sweep Triangulation (SWEEP)
Category: Logic
Open
Sylow Subgroups (SylowSub)
Category: Local Optimality
Open
Telephone Connection (TC)
Category: Matching
P-complete
Topologically Ordered Circuit Value Problem (TopCVP)
Category: Circuit Complexity
P-hard
Traveling Salesman 2-Opt (TS2Opt)
Category: Local Optimality
Open
Two Variable Linear Programming (TVLP)
Category: Graph Theory
P-hard
Unweighted Two Satisfiability FLIP (U2SATFLIP)
Category: Local Optimality
P-hard
Unweighted Graph Partitioning SWAP (UGPS)
Category: Local Optimality
Open
Unit Length Visibility Layers (UL VL)
Category: Logic
P-hard
Unweighted Maximum Cut SWAP (UMCS)
Category: Local Optimality
P-hard
Unweighted, Not-all-equal Clauses, 3SAT FLIP (UNAE3SAT)
Category: Local Optimality
P-complete
Unification (UNIF)
Category: Logic
P-complete
Unit Resolution (UNIT)
Category: Logic
Open
Univariate Polynomial Factorization over Q (UPFQ)
Category: Formal Languages
P-complete
Uniform Word Problem for Finitely Presented Algebras (UWPFPA)
Category: Algebra
P-complete
Uniform Word Problem for Lattices (UWPL)
Category: Algebra
P-complete
Visibility Layers (VL)
Category: Geometry
P-complete
Zero-sum Bimatrix Game (ZSBG)
Category: Games
P-complete
αβ-Bcore (αβ-Bcore)
Category: Graph Theory
P-hard
ϵ-Circuit Depth Ones (ϵCDO)
Category: Circuit Complexity
P-hard
ϵ-Circuit true Gates (ϵCTG)
Category: Circuit Complexity