Graph theory and combinatorics
The Top Open Problems editorial order restricted to Computer Science, followed by cross-listed economics entries. Existing relative order is retained, with provisional placements for new game-learning questions; most entries have no individual difficulty assessment. 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
- CS-17 Planted Clique Conjecture
- CS-32 Graph Isomorphism in Polynomial Time
- CS-52 Perfect-Matching Search in Deterministic NC (General Graphs)
- CS-63 Polynomial-time explicit logarithmic Ramsey graphs
- CS-64 Deterministic polynomial-time exact bipartite matching
- CS-74 NP-Hardness of Constant-Factor Approximation for Densest k-Subgraph
- CS-76 Computability of the Shannon Capacity of Finite Graphs
- CS-79 Matroid Secretary Conjecture
- CS-80 Deterministic Linear-Time Minimum Spanning Tree Problem
- CS-84 Combinatorial Boolean Matrix Multiplication in Near-Linear Time
- CS-95 Flip Graph Connectivity in 3D
- CS-105 10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut
- CS-118 Polynomial switch-chain mixing for all degree sequences
- CS-123 FPRAS for common integer polymatroid bases
- CS-124 FPRAS for common matroid bases
- CS-129 Constant-factor hardness of directed feedback vertex set
- CS-135 FPRAS for perfect matchings in general graphs
- CS-139 Exponential semidefinite complexity for perfect matching
- CS-140 Optimal Max-Cut approximation hardness
- CS-144 Constant-factor hardness of Min-UnCut
- CS-146 One-sample matroid prophet selection
- CS-151 Entropy bounds at perfect-matching marginals
- CS-157 Almost-linear maximum-cardinality matching
- CS-164 Independent-set hardness with a three-colorability promise
- CS-169 Constant-factor hardness of uniform sparsest cut
- CS-170 Large Goemans–Linial gaps for uniform sparsest cut
- CS-172 Factor-two hardness of Vertex Cover
- CS-174 Complexity of Weisfeiler–Leman graph identification
- CS-175 Parity witnesses for Weisfeiler–Leman equivalence
- CS-186 10 Lectures and 42 Open Problems — The Paley Clique Problem
- CS-187 10 Lectures and 42 Open Problems — Maximum and minimum bisections on random regular graphs
- CS-202 Componentwise entropy rigidity and a reduced search for a non-multilinear matroid
- CS-267 Approximability and Parameterized Complexity of Steiner Forest
- CS-268 Hardness of the $\varepsilon-Dense$ Steiner Tree Problem
- CS-269 Complexity and Approximation of Planar Min-Bisection
- CS-270 An FPAS for Constrained Bicriteria Spanning Trees
- CS-271 Output-Polynomial Enumeration of Bicriteria Spanning Trees
- CS-283 Integral Primal Certificates for Submodular Minimization
- CS-284 Recognition and Characterization of Leaf Powers
- CS-285 Sampling Algorithms for Maximum-Cut Density
- CS-286 Codegree Thresholds for Hypergraph Matchings
- CS-287 Complexity of Dense Perfect Hypergraph Matching
- CS-297 Rotational Matching Complexity for Planar Point Sets
- CS-299 Alcuin Numbers and Recognition of Small Boat Graphs
- CS-310 Integer Carathéodory Property for Intersecting Matroid Base Polytopes
- CS-311 Integer Carathéodory Property for Arborescence Polytopes
- CS-312 Greedy Decomposition of the Spanning-Tree Polytope
- CS-313 Density and Geometry Recovery from Nearest-Neighbor Graphs
- CS-315 Multicolored Sunflower Conjecture over Ternary Vector Spaces
- CS-322 Polynomial-Time Minimization of K-Submodular Functions