Graph theory and combinatorics
Provisional editorial order for Top Open Problems: Millennium Prize Problems first, followed by assessed difficulty tiers; the unassessed remainder keeps its previous catalogue order. About rankings
Browse by subject
Search this collection by problem ID, title, classification, subject, provider, or model.
Search results
No matching problems. Try another search or clear a filter.
93 records · Search and filter
- Math-105 Planted Clique Conjecture
- Math-134 Graph Isomorphism in Polynomial Time
- Math-231 Perfect-Matching Search in Deterministic NC (General Graphs)
- Math-284 Polynomial-time explicit logarithmic Ramsey graphs
- Math-293 Deterministic polynomial-time exact bipartite matching
- Math-381 NP-Hardness of Constant-Factor Approximation for Densest k-Subgraph
- Math-412 Computability of the Shannon Capacity of Finite Graphs
- Math-436 Matroid Secretary Conjecture
- Math-441 Deterministic Linear-Time Minimum Spanning Tree Problem
- Math-484 Combinatorial Boolean Matrix Multiplication in Near-Linear Time
- Math-1660 Flip Graph Connectivity in 3D
- Math-2073 10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut
- Math-2960 Polynomial switch-chain mixing for all degree sequences
- Math-2965 FPRAS for common integer polymatroid bases
- Math-2966 FPRAS for common matroid bases
- Math-2971 Constant-factor hardness of directed feedback vertex set
- Math-2977 FPRAS for perfect matchings in general graphs
- Math-2981 Exponential semidefinite complexity for perfect matching
- Math-2982 Optimal Max-Cut approximation hardness
- Math-2986 Constant-factor hardness of Min-UnCut
- Math-2988 One-sample matroid prophet selection
- Math-2993 Entropy bounds at perfect-matching marginals
- Math-2999 Almost-linear maximum-cardinality matching
- Math-3006 Independent-set hardness with a three-colorability promise
- Math-3011 Constant-factor hardness of uniform sparsest cut
- Math-3012 Large Goemans–Linial gaps for uniform sparsest cut
- Math-3014 Factor-two hardness of Vertex Cover
- Math-3016 Complexity of Weisfeiler–Leman graph identification
- Math-3017 Parity witnesses for Weisfeiler–Leman equivalence
- Math-4375 10 Lectures and 42 Open Problems — The Paley Clique Problem
- Math-4376 10 Lectures and 42 Open Problems — Maximum and minimum bisections on random regular graphs
- Math-4391 Componentwise entropy rigidity and a reduced search for a non-multilinear matroid
- Math-4456 Approximability and Parameterized Complexity of Steiner Forest
- Math-4457 Hardness of the $\varepsilon-Dense$ Steiner Tree Problem
- Math-4458 Complexity and Approximation of Planar Min-Bisection
- Math-4459 An FPAS for Constrained Bicriteria Spanning Trees
- Math-4460 Output-Polynomial Enumeration of Bicriteria Spanning Trees
- Math-4472 Integral Primal Certificates for Submodular Minimization
- Math-4473 Recognition and Characterization of Leaf Powers
- Math-4474 Sampling Algorithms for Maximum-Cut Density
- Math-4475 Codegree Thresholds for Hypergraph Matchings
- Math-4476 Complexity of Dense Perfect Hypergraph Matching
- Math-4486 Rotational Matching Complexity for Planar Point Sets
- Math-4488 Alcuin Numbers and Recognition of Small Boat Graphs
- Math-4499 Integer Carathéodory Property for Intersecting Matroid Base Polytopes
- Math-4500 Integer Carathéodory Property for Arborescence Polytopes
- Math-4501 Greedy Decomposition of the Spanning-Tree Polytope
- Math-4502 Density and Geometry Recovery from Nearest-Neighbor Graphs
- Math-4504 Multicolored Sunflower Conjecture over Ternary Vector Spaces
- Math-4511 Polynomial-Time Minimization of K-Submodular Functions