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-345 Resolution Lower Bounds for Clique Certification
- CS-350 Local Approximation of Random-Graph Semidefinite Programs
- CS-356 Hardness of Root-Dependent Spanning-Tree Optimization
- CS-357 Hardness of Path-Cost Arborescence Optimization
- CS-359 Degree-Utility Optimization in Graphs
- CS-368 Sample Complexity of Vertex-Distribution-Free Graph Testing
- CS-376 Complexity of Submodular $k$-Partition
- CS-379 Arborescences Induced by Linear-Programming Pivot Rules
- CS-383 Better-Than-Two Approximation for Multiplicative Connectivity Augmentation
- CS-385 Compact Representations of Four-Thirds Near-Mincuts
- CS-386 Better Approximations for Unrelated Graph Balancing
- CS-387 Deterministic Optimization of Top-$k$ Perfect-Matching Edges
- CS-389 Algebraic and Graph-Property Tests for Quantum Functions
- CS-395 LOCAL Coloring Complexity and Constant-Round Decidability on Trees
- CS-397 Determinacy Methods in LOCAL and Borel Coloring
- CS-404 Convex Relaxations for Planted Graph Matching
- CS-423 Near-Linear Subgraph Isomorphism for Acyclic Patterns
- CS-433 Approximating Fare-Zone Assignment on Trees
- CS-488 Vertex flattenings generate the phylogenetic ideal
- CS-521 Dominating sets as marked centralizer covers in graph groups
- CS-626 Duplicate Planar Min-Bisection and Bicriteria Extraction
- CS-627 Duplicate Bicriteria Spanning-Tree Enumeration
- CS-658 Capacity-Preserving Conversion to Unsplittable Flows
- CS-672 Composite Repetition of Three Matroid Questions
- CS-677 Polynomial Freiman–Ruzsa Conjecture over Binary Vector Spaces
- CS-686 Combinatorial Decompositions of the All-Ones Vector
- CS-715 Defining High-Dimensional Expanders Through Local Spectra
- CS-719 Restricted Models of Vertex-Distribution-Free Testing
- CS-732 Unspecified Combinatorial Optimization Problem
- CS-733 Half-Integral Extreme Points for Feedback Vertex Set
- CS-734 Approximating Submodular Functions by Matroid Rank Functions
- CS-743 Open Problems in Local Graph Complexity
- CS-749 Unspecified Flag Algebra Extremal Problem
- CS-755 Stable Algorithms and Overlap Gaps for Friendly Bisections
- CS-764 Average-Case Complexity of Clique on Sparse Graphs
- CS-765 Spreadness as a Replacement for Sunflower Structure
- CS-772 Mixing of Random Colorings on General Graphs
- CS-781 Workshop Contents Listing for Combinatorial Optimization
- CS-784 Duplicate Fare-Zone Approximation Question
- CS-785 Two-Coloring Light Tournaments
- CS-786 Duplicate Light-Tournament Two-Coloring Question
- CS-787 Half-Integral Extreme Points for a Feedback-Vertex-Set Relaxation
- CS-788 Duplicate Fiorini Feedback-Vertex-Set Question