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
Combinatorics·Captain: mikedeng1

Flow-Optimal Separators for Minor-Free and Induced-Minor-Free Graphs in Linear Time via Follow the Regularized LeaderResearch Paper

A balanced vertex separator removes a small set of vertices so that no remaining connected component contains most of the original graph. Such separators allow a graph problem to be divided into smaller instances. Their usefulness depends on both the number of removed vertices and the time spent finding them: a small separator with expensive construction…

25 thms3 active usersReviewed
Complexity Theory·Captain: mikedeng1

Quasipolynomial 3-Coloring of Diameter-2 Graphs via Domain Reduction from NogoodsResearch Paper

A proper three-coloring assigns one of three named colors to each vertex of a graph so that adjacent vertices receive different colors. A diameter-two graph has a direct edge or a common neighbor between every pair of distinct vertices. This promise makes the graph globally close together, but does not immediately supply a way to choose consistent colors.…

23 thms3 active usersReviewed
CombinatoricsComplexity TheoryProbability+1·Captain: Shuze Chen

Near-Linear Lower Bounds for Testing Directed AcyclicityResearch Paper

Property testing asks for algorithms that inspect a tiny part of a large object and distinguish objects with a property from objects that are far from it (Goldreich, Goldwasser, Ron 1998). For sparse directed graphs, the natural access model is the bounded-degree incidence-lists model of Bender and Ron (2002): the algorithm may ask for the outgoing edges of…

20 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Counterexamples to the Strong Roberson ConjectureResearch Paper

Lovász proved in 1967 that two finite graphs are isomorphic if and only if they have the same number of homomorphisms from every finite graph. Restricting the source graphs to a class F\mathcal FF gives a coarser equivalence, homomorphism indistinguishability over F\mathcal FF, and many equivalences of theoretical computer science are of this form: Dvořák…

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

Structural Origins of Cubic Complexity in Pebble MotionResearch Paper

In the pebble motion problem, labelled pebbles sit on distinct vertices of a graph, and a move slides one pebble along an edge onto an empty vertex. The task is to transform an initial placement into a target placement. The 15-puzzle is the best-known instance. The problem is a basic model of reconfiguration under exclusion constraints, and it underlies…

18 thms3 active usersReviewed
Complexity TheoryProbability·Captain: Shuze Chen

Semi-Streaming Matching in a Single Pass II: Greedy is OptimalResearch Paper

A large graph can have far more edges than vertices. Keeping every edge in memory may therefore be impractical even when retaining a few records for each vertex is affordable. The semi-streaming model asks what can be computed under this limitation when edges arrive sequentially. For maximum matching, a simple greedy procedure retains an arriving edge…

22 thms3 active usersReviewed
Operations ResearchTheoretical Computer Science·Captain: Shuze Chen

Weighted Minimum Cuts and Near-Minimum Cut EstimationResearch Paper

A minimum cut of a graph with positive edge capacities is a cheapest way to disconnect it. Minimum cuts measure network reliability, and they are a basic subroutine in clustering, network design and the estimation of disconnection probabilities. A graph can have many minimum cuts: a cycle on nnn vertices has (n2)\binom n2(2n​) of them. The cactus representation of…

27 thms3 active usersReviewed
Complexity Theory·Captain: Shuze Chen

Tree-Residue Vertex-Breaking: a new tool for proving hardness: NP-completeness of Planar (B, U)-TRVB and (B, U)-TRVB whenever B contains a degree k ≥ 4Research Paper

NP-hardness proofs for puzzles, video games and geometric path problems often reduce from a Hamiltonicity problem on restricted graphs. These reductions share a pattern: the local constraints of the target problem are easy to satisfy gadget by gadget, and the whole difficulty is a global constraint, typically that the chosen pieces form one connected,…

22 thms3 active usersReviewed
Complexity Theory·Captain: mikedeng1

Pfaffian Recognition is in coRPResearch Paper

A perfect matching is a set of edges covering each vertex exactly once. Deciding whether one exists is possible in polynomial time, but counting all perfect matchings is #P-complete even for bipartite graphs. This distinction matters in counting complexity and in the combinatorics of dimers: a graph can have an efficiently detectable matching while its full…

19 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Listing Even Cycles Even FasterResearch Paper

A pattern-listing problem asks for every occurrence of a fixed small graph inside a larger graph. Listing cycles is one such problem: its output can be much larger than its input, so a useful running-time guarantee must account for both. When a graph contains few copies, an algorithm should avoid exploring an enormous collection of unsuccessful candidates.…

9 thms3 active usersReviewed
Optimization·Captain: mikedeng1

Deterministic directed minimum cut via capacity-selected terminalsResearch Paper

A directed minimum cut measures the least total capacity whose removal prevents some vertex from reaching another. When both endpoints are prescribed, maximum flow determines this value. When only a root is prescribed, or neither endpoint is fixed, the algorithm must also locate an appropriate terminal. This distinction matters in algorithms that use…

14 thms3 active usersReviewed
Combinatorics·Captain: mikedeng1

Directed Global Minimum Cut in Almost-Linear TimeResearch Paper

A directed global minimum cut measures how cheaply a directed network can lose reachability: remove a set of arcs of minimum total weight so that some vertex can no longer reach another. Direction matters because losing access in one direction need not affect access in the reverse direction. The optimization problem concerns the weakest ordered-pair…

21 thms3 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian CertificatesResearch Paper

A proper coloring assigns a label to each vertex of a graph so that adjacent vertices have different labels. A graph is three-colorable when such an assignment exists using three labels. Knowing that three colors suffice does not supply the assignment. The approximation question asks how many colors an efficient algorithm can guarantee under that promise.…

22 thms3 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree GraphsResearch Paper

A multi-spin system assigns one of finitely many spins to each vertex of a graph. Each assignment receives a weight determined by local vertex preferences and interactions across edges. The sum of these weights, the partition function, is useful both as a counting quantity and as the normalizing constant of a probability distribution. Computing this sum…

25 thms3 active usersReviewed
CombinatoricsComputational Complexity·Captain: mikedeng1

Triangle-Freeness: Estimation Is as Easy as TestingResearch Paper

An algorithm examining a large graph may have time to inspect only a small part of its adjacency matrix. Property testing asks whether the graph has a specified property or requires a substantial number of edge changes to acquire it. Distance estimation asks how many changes are needed, to a prescribed additive accuracy. For triangle-freeness, a tester can…

17 thms3 active usersReviewed
Computational ComplexityInformation Theory·Captain: mikedeng1

Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent SetResearch Paper

A graph stream presents the edges of a graph one at a time while an algorithm keeps a limited working memory. Maximum Clique asks for a largest set of vertices with every pair joined by an edge. Streaming algorithms for this problem are relevant to the study of what graph information can be retained in a small memory: the desired output is a set of…

22 thms3 active usersReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

Ruling out Fast Approximation Algorithms for Clique, Biclique, Collinearity, and Arithmetic ProgressionsResearch Paper

A clique is a collection of vertices in a graph with an edge between every pair. Detecting a fixed small clique is a basic graph algorithm problem. A natural approximation question asks whether a promise of a much larger clique helps detect a smaller one. In particular, could a program distinguish a graph containing a large fixed clique from a graph…

25 thms3 active usersReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

Arc Kayles is PSPACE-completeResearch Paper

Arc Kayles is a two-player game on a finite undirected graph. The players alternate, and a move picks an edge uvuvuv of the current graph and deletes both endpoints. Under normal play the first player without a legal move loses. The winner is the player who plays the last edge of a maximal matching of the original graph, so Arc Kayles is to maximal matchings…

19 thms3 active usersReviewed
OptimizationProbability·Captain: mikedeng1

Optimal Sample Complexity for Max-CutResearch Paper

A maximum cut partitions a graph's vertices into two parts to maximize the total weight of edges between them. When a graph is too large to inspect in full, estimating this optimum from a small sample can reduce the amount of graph data needed. A value coreset is a small reweighted graph whose maximum-cut value approximates the original value. Returning a…

34 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Forgetting Alternation and BlossomsResearch Paper

A maximum cardinality matching of a general graph can be found by repeatedly augmenting the current matching along a maximal set of vertex-disjoint shortest augmenting paths. Hopcroft and Karp showed that O(n)O(\sqrt n)O(n​) such phases suffice, so the whole difficulty is to compute one maximal set of disjoint shortest augmenting paths in nearly linear time. In…

29 thms3 active usersReviewed
CombinatoricsProbability·Captain: iris

Almost Every 3-Uniform Hypergraph is Class 1Research Paper

Colouring the edges of a graph or hypergraph so that intersecting edges get different colours is the same as partitioning its edges into matchings. The problem appears in scheduling, communication networks and design theory. For ordinary graphs the answer is almost settled: by Vizing's theorem every graph GGG has χ′(G)∈{Δ(G),Δ(G)+1}\chi'(G) \in \{\Delta(G), \Delta(G)+1\}χ′(G)∈{Δ(G),Δ(G)+1}, and…

43 thms3 active usersReviewed
OptimizationTheoretical Computer Science·Captain: iris

Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified FrameworkResearch Paper

A semi-streaming algorithm reads the edges of an nnn-vertex graph as a stream, possibly several times, and keeps only O(n polylog n)O(n\,\mathrm{polylog}\,n)O(npolylogn) bits of memory. Matching is the central problem of this model: the output itself can have Θ(n)\Theta(n)Θ(n) edges, so the model allows just enough memory to write it down, and the question is how many passes over the stream a …

24 thms3 active usersReviewed
Complexity TheoryQuantum InformationTheoretical Computer Science·Captain: iris

Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is HardResearch Paper

The welded trees problem is the standard example of an exponential quantum speedup for a problem defined by a graph given only through a neighbor oracle. Childs, Cleve, Deotto, Farhi, Gutmann and Spielman showed in 2003 (doi:10.1145/780542.780552) that a continuous-time quantum walk started at the entrance of a randomly welded pair of binary trees reaches…

34 thms3 active usersReviewed
Algorithmic Game TheoryTheoretical Computer Science·Captain: iris

The Price of Stability in Undirected Network Design: Lower Bounds and Structural GuaranteesResearch Paper

In a network design game with equal cost sharing, players connect their terminals through a shared network and split the cost of every edge equally among its users. An optimal network can be unstable: one player may lower her own share by rerouting while the total cost rises. The price of stability (PoS) measures how much a stable outcome must cost: the…

28 thms3 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

NP-hardness for Bipartite Colorings up to the Maximum DegreeResearch Paper

Counting the proper qqq-colorings of a graph of maximum degree Δ\DeltaΔ is the central test case of approximate counting. Since Jerrum (1995) it has been conjectured that an FPRAS exists for general graphs whenever q≥Δ+1q\ge\Delta+1q≥Δ+1, and the rapid-mixing bounds for Glauber dynamics have moved from q>2Δq>2\Deltaq>2Δ toward that threshold. On the hardness side, Galanis,…

31 thms3 active usersReviewed
PreviousPage 4 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