Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Graph Theory

699 missions · 311 completed

Missions

Open388Completed311All699
Computational GeometryDiscrete Geometry·Captain: hao jia

Uniform Obstacle Bounds for Planar Graphs (OPG-37357)Open Problem

An obstacle representation turns a graph into a visibility system: vertices are points in the plane, and nonedges are blocked by polygonal obstacles. The obstacle number asks for the minimum number of obstacles needed. OPG-37357 records two different questions for planar graphs. The first asks whether one obstacle can ever be insufficient. The second asks…

6 thms4 active usersReviewed
CombinatoricsOptimization·Captain: hao jia

Clique Partitions of Chordal Graphs (Erdos Problem 81)Open Problem

An edge partition into cliques compresses the adjacency structure of a graph into complete pieces without allowing any edge to be counted twice. Erdős Problem 81 asks for the asymptotically sharp upper bound on the number of pieces needed when the graph is chordal. Chordal graphs have strong elimination structure, but that structure does not make the…

16 thms4 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Linear-Space Exact Distance Oracle for Minor-Free GraphsResearch Paper

A distance oracle preprocesses a weighted graph so that later queries can ask for the shortest distance between two vertices. Storing every answer takes quadratic space. Storing only the input uses linear space on sparse graphs, but computing a shortest path from scratch can take almost linear time for each query. The question addressed here is whether the…

10 thms3 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLLResearch Paper

Vizing's theorem gives every simple graph of maximum degree Δ\DeltaΔ a proper edge colouring with Δ+1\Delta+1Δ+1 colours. Maintaining such a colouring while edges are inserted and deleted is much harder: no dynamic algorithm for (Δ+1)(\Delta+1)(Δ+1) colours with subpolynomial update time is known, except for low-degree graphs. With slightly more colours, (1+ϵ)Δ(1+\epsilon)\Delta(1+ϵ)Δ,…

26 thms3 active usersReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: Shuze Chen

First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted GraphsResearch Paper

All-pairs approximate shortest paths (APASP) asks for a matrix ddd with δ(u,v)≤d[u,v]≤α δ(u,v)+β\delta(u,v)\le d[u,v]\le\alpha\,\delta(u,v)+\betaδ(u,v)≤d[u,v]≤αδ(u,v)+β for every pair of vertices. Static algorithms trade the stretch (α,β)(\alpha,\beta)(α,β) against running time; the classical additive tradeoffs are due to Dor, Halperin and Zwick for unweighted graphs and to Cohen and Zwick for weighted graphs,…

17 thms3 active usersReviewed
Captain: mikedeng1

An O~(m+n3/2ϵ−1)\widetilde O(m+n^{3/2}\epsilon^{-1})O(m+n3/2ϵ−1) algorithm for counting spanning trees by ℓ1\ell_1ℓ1​-regularized resistanceResearch Paper

A spanning tree connects every vertex of a finite graph without a cycle. When edges have positive real weights, the weight of a tree is the product of its edge weights, and the total tree weight sums these products over every spanning tree. This quantity connects a combinatorial counting problem with numerical linear algebra: Kirchhoff's matrix–tree theorem…

16 thms3 active usersReviewed
Probability·Captain: mikedeng1

Strong Convergence for Zig-Zag Products and Typical Spectra of Irregular GraphsResearch Paper

The zig-zag product separates the number of vertices of a graph from its degree. It combines a large regular graph with a fixed small graph, called a gadget, to produce another graph of bounded degree. Spectral estimates for this construction matter in the study of expander graphs: a small nontrivial adjacency spectrum measures how strongly the graph mixes.…

41 thms3 active usersReviewed
Theoretical Computer Science·Captain: mikedeng1

Constructive Arboricity in Almost-Linear Time for Dense GraphsResearch Paper

Graph algorithms often need a representation of sparsity that can be used directly. A forest has no cycle, so its edges admit tree operations and simple traversal rules. A graph whose edges split into a small number of forests can be processed one forest at a time. The minimum possible number, called arboricity, measures this form of sparsity. An algorithm…

18 thms3 active usersReviewed
Combinatorics·Captain: mikedeng1

Generalized Sorting via Four-CyclesResearch Paper

Ordinary comparison sorting can compare any pair of elements. In applications where only particular pairs can be compared, that freedom disappears: the available comparisons form a graph, and a sorting procedure must learn an order through its edges. The generalized sorting problem measures the number of comparisons needed when this graph is known but the…

10 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: Shuze Chen

Incremental Approximate Vertex Connectivity via Almost-Linear Time Local Cut AlgorithmsResearch Paper

The vertex connectivity κ(G)\kappa(G)κ(G) of a graph is the least number of vertices whose removal disconnects it. It measures how robust a network is against node failures, and it is one of the most basic quantities in graph algorithms. For directed graphs the notion is strong connectivity: κ(G)\kappa(G)κ(G) is the least size of a set whose deletion leaves a graph that is…

23 thms3 active usersReviewed
CombinatoricsProbability·Captain: Shuze Chen

Hitting time for loose Hamilton cycles in the random hypergraph processResearch Paper

Hitting-time theorems are among the sharpest statements in the theory of random graphs. Instead of asking at which edge density a property appears, they ask whether it appears at the exact moment the obvious local obstruction disappears. For graphs, Ajtai, Komlós and Szemerédi and, independently, Bollobás proved in 1984–85 that the random graph process…

21 thms3 active usersReviewed
Machine LearningProbabilityStatistics·Captain: Shuze Chen

Supervised Learning with Hidden CorrespondencesResearch Paper

In many data sets the correspondence between inputs and labels is lost or only partly known: records are linked across databases without a shared identifier, labels are released only in aggregate over bags of examples, or a privacy mechanism shuffles them. The learner then sees inputs X1,…,XnX_1,\dots,X_nX1​,…,Xn​ and labels Y1,…,YnY_1,\dots,Y_nY1​,…,Yn​ together with a graph of plausible…

24 thms3 active usersReviewed
CombinatoricsLinear algebraOperations Research+1·Captain: Shuze Chen

Breaking the Quadratic Time Barrier for Flow Sparsifiers via Schur Complement LocalizationResearch Paper

Many multicommodity flow and cut problems only concern a small set of terminals inside a large network. Vertex sparsification replaces the network by a graph on the terminals alone that preserves, up to a factor called the quality, how well every pattern of terminal traffic can be routed. Such a graph is a preprocessing step for approximation algorithms…

19 thms3 active usersReviewed
Convex OptimizationProbabilityTheoretical Computer Science·Captain: Shuze Chen

Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive ErrorResearch Paper

Releasing a weighted graph under edge-level differential privacy is a basic task in private data analysis: the vertex set is public, the weight of every pair of vertices is private, and a released synthetic graph should preserve the answers to a rich family of queries. Cut queries are the canonical family, because many graph optimization problems (Max-Cut,…

23 thms3 active usersReviewed
CombinatoricsComplexity Theory·Captain: iris

A Polynomial Kernel for Planar Directed Feedback Vertex SetResearch Paper

A directed feedback vertex set of a digraph DDD is a set of vertices whose removal leaves no directed cycle. Directed Feedback Vertex Set (DFVS) asks, for a digraph DDD and an integer kkk, whether such a set of size at most kkk exists. It is a basic problem in deadlock resolution, circuit testing and the analysis of feedback in networks, and it is NP-hard even on…

41 thms3 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Dynamic (Δ+1)(\Delta+1)(Δ+1)-Coloring with Polylogarithmic Worst-Case Update TimeResearch Paper

A graph of maximum degree Δ\DeltaΔ always has a proper coloring with Δ+1\Delta+1Δ+1 colors, and the static greedy algorithm finds one in linear time. In the fully dynamic setting the graph undergoes edge insertions and deletions, its maximum degree stays at most Δ\DeltaΔ, and a proper (Δ+1)(\Delta+1)(Δ+1)-coloring must be kept after every update. The recourse of an update is…

19 thms3 active usersReviewed
Computational ComplexityLinear algebraTheoretical Computer Science·Captain: Shuze Chen

Bipartite Matching is in NCResearch Paper

Whether a perfect matching of a bipartite graph can be found by a fast parallel algorithm has been a central open question of parallel complexity since the 1980s. Randomized parallel algorithms (the class RNC) were found early: Lovász's determinant test for the decision problem (1979), and the algorithms of Karp, Upfal and Wigderson (1986) and of Mulmuley,…

25 thms3 active usersReviewed
CombinatoricsTheoretical Computer ScienceTopology·Captain: Shuze Chen

A unifying framework for Graph Minor Structure Theorems with polynomial boundsResearch Paper

The Graph Minor Structure Theorem of Robertson and Seymour describes every graph that excludes a fixed graph HHH as a minor: around any large grid-like piece, after deleting a bounded number of apex vertices, the graph is drawn in a surface in which HHH does not embed, up to a bounded number of vortices of bounded depth. Its local form, the Local Structure…

20 thms3 active usersReviewed
CombinatoricsComputational Complexity·Captain: Shuze Chen

Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable DecompositionResearch Paper

Minimum Bisection asks whether the vertex set of a graph can be split into two halves, up to one vertex, with at most kkk edges between them. It is the unweighted two-part case of the graph-partitioning problem of Kernighan and Lin (1970) and is NP-complete (Garey, Johnson and Stockmeyer, 1976). Parameterized by the cut size kkk, it became a test case for the…

29 thms3 active usersReviewed
OptimizationTheoretical Computer Science·Captain: mikedeng1

Rounded Potentials Certify Exact Maximum FlowResearch Paper

A maximum flow measures how much material can move from a source to a sink while respecting directed edge capacities and conserving material at other vertices. The classical certificate for its exact value contains both a feasible flow and a separating cut of the same value. The maximum-flow/minimum-cut theorem guarantees that these witnesses exist Ford and…

23 thms3 active usersReviewed
Computational ComplexityLinear OptimizationTheoretical Computer Science·Captain: mikedeng1

An LP Algorithm for Counting Eulerian Orientations Through the Lens of Promise PolymorphismsResearch Paper

A finite graph can be oriented so that each vertex has equally many incoming and outgoing edges precisely when every vertex has even degree. Counting the orientations subject to local restrictions is a different computational problem. A vertex can favor some local arrangements, forbid others, or attach complex weights to them. The resulting weighted sum…

40 thms3 active usersReviewed
Computational Complexity·Captain: mikedeng1

Vertex Deletion on HHH-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation SchemesResearch Paper

Vertex deletion asks how many vertices must be removed to make a graph satisfy a prescribed condition. Removing vertices to eliminate every edge gives Vertex Cover; removing them to eliminate every cycle gives Feedback Vertex Set. These problems arise within a common formulation: the remaining graph must have bounded treewidth and satisfy a fixed logical…

30 thms3 active usersReviewed
Convex OptimizationOptimizationTheoretical Computer Science·Captain: Shuze Chen

Efficient Correlation Clustering in Single-pass Graph Streams: Deterministic and Adversarially RobustResearch Paper

Correlation clustering asks for a partition of a vertex set that agrees as much as possible with pairwise "similar / dissimilar" labels. It is a standard model for deduplication and community detection, introduced by Bansal, Blum and Chawla (2004); minimizing disagreements is APX-hard, and a line of offline work has pushed the approximation ratio from 3 (Ail…

23 thms3 active usersReviewed
Computational ComplexityTheoretical Computer Science·Captain: iris

Reverse Reductions: From Faster SAT to Subexponential AlgorithmsResearch Paper

The Exponential Time Hypothesis (ETH) asserts that 3-SAT on NNN variables needs time 2Ω(N)2^{\Omega(N)}2Ω(N). A large part of parameterized complexity rests on it: for Vertex Cover and ddd-Hitting Set parameterized by the solution budget kkk, the standard lower bounds say that no algorithm runs in 2o(k)∣I∣O(1)2^{o(k)}|I|^{O(1)}2o(k)∣I∣O(1) time unless ETH fails (Cygan et al., Parameterized…

57 thms3 active usersReviewed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Algorithms for Min-Color Path with Bounded Color-DegreeResearch Paper

A robot that must move from sss to ttt through a field of obstacles, or a signal that must cross a sensor field, wants to cross as few obstacles as possible. Discretized, this is Min-Color Path: the obstacles become colors on the vertices of an arrangement graph and one asks for an sss–ttt path touching the fewest colors. The problem appears as Minimum Constraint…

26 thms3 active usersReviewed
PreviousPage 3 of 16Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me