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
CombinatoricsOptimal TransportTheoretical Computer Science·Captain: Shuze Chen

Graph Similarity Meets Optimal TransportResearch Paper

A common way to measure how different two graphs are is to align their vertex sets and count how much the adjacency structure disagrees under the alignment. With different matrix norms this gives graph edit distance, a standard tool in pattern recognition and graph matching (Gao et al. 2010); local edit distance, the largest number of edits needed at a…

21 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: Shuze Chen

Nearly Tight Low-Stretch Ramsey Spanning TreesResearch Paper

Embeddings of metric spaces into trees and ultrametrics are a standard tool for approximation algorithms, distance oracles and compact routing: a problem on a general metric is solved on a tree and the answer is mapped back, at the price of the distortion. The metric Ramsey theorem (Bartal, Linial, Mendel, Naor 2005; Mendel, Naor, FOCS 2006) says that every …

18 thms2 active usersReviewed
ProbabilityStatisticsTheoretical Computer Science·Captain: Shuze Chen

Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation TestingResearch Paper

Graph matching asks for the correspondence between the nodes of two structurally similar graphs. It is a quadratic assignment problem, NP-hard in the worst case, with applications such as the de-anonymization of social networks. The average-case version on random graphs is a standard testbed for the gap between what is information-theoretically possible and…

25 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: Shuze Chen

Recognizing Label-Connected GraphsResearch Paper

In the classical gossiping problem every participant holds one piece of information, and whenever two participants call each other they exchange everything they know. With all pairs allowed to call, 2n−42n - 42n−4 calls are necessary and sufficient for n≥4n \ge 4n≥4 participants (Baker–Shostak 1972; Hajnal–Milner–Szemerédi 1972). When the available calls are prescribed…

19 thms2 active usersReviewed
CombinatoricsComputational ComplexityTheoretical Computer Science·Captain: Shuze Chen

Constrained Directed Separation: Algorithms and ClassificationsResearch Paper

Directed Multicut asks to delete at most kkk nonterminal vertices of a digraph so that no directed path remains from the first to the second terminal of any demand. Olkowski and Ramanujan study what happens when the deleted vertices must also satisfy a structural condition: the subdigraph they induce must belong to a fixed hereditary class H\mathcal HH.…

27 thms2 active usersReviewed
CombinatoricsComputational ComplexityTheoretical Computer Science·Captain: Shuze Chen

Once-Paid Subsequences and the Cost of Min-Plus ApproximationResearch Paper

Many sequence problems are solved by a prefix recurrence that uses only minimum and addition, and such a recurrence, once its structure is fixed before the costs are known, is a min-plus circuit. Lower bounds on min-plus circuits therefore say which recurrences cannot exist, independently of how clever the choice of states is (Jukna–Seiwert 2020).

18 thms2 active usersReviewed
Computational Complexity·Captain: mikedeng1

Exact Mean Certificates under Sparse Graph CorruptionResearch Paper

A network of sensors can report a plausible average even when a few individual readings are arbitrary. A known bound on how much the true value changes across an edge supplies information beyond the reports. The question is then how much uncertainty about the network mean survives a particular observation. The distinction matters when an application needs…

32 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Online Graph Exploration under T-Interval ConnectivityResearch Paper

A mobile agent that discovers a network one hop at a time cannot plan from a complete map. If links change while it moves, connectivity at each instant does not by itself let the agent reach every vertex. This matters for the mathematical foundations of exploration in changing networks: the assumption must constrain how connectivity persists, rather than…

22 thms2 active usersReviewed
Theoretical Computer Science·Captain: mikedeng1

Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar DigraphsResearch Paper

A dependency system can contain directed cycles even when its underlying connections can be drawn without crossings. The directed feedback vertex set problem asks how many vertices must be removed to eliminate every such cycle. Its parameterized version asks for a set of at most a given budget kkk. The issue is whether the exponential part of the running time…

17 thms2 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: Shuze Chen

Breaching the 2-Approximation Barrier for Prize-Collecting Steiner ForestResearch Paper

Prize-Collecting Steiner Forest (PCSF) is a network design problem: connect demand pairs in a graph by buying edges, where a pair may also be left unconnected at the cost of its penalty. It contains Steiner Tree and Steiner Forest, so it is NP-hard and APX-hard (Karp 1972); approximation algorithms are the standard way to handle it.

18 thms2 active usersReviewed
Operations ResearchTheoretical Computer Science·Captain: Shuze Chen

Faster Algorithms for Minimum Degree Spanning TreeResearch Paper

In the minimum degree spanning tree (MDST) problem one is given a connected undirected graph G=(V,E)G=(V,E)G=(V,E) with n=∣V∣n=|V|n=∣V∣ nodes and m=∣E∣m=|E|m=∣E∣ edges and seeks a spanning tree whose largest node degree is as small as possible. The optimum

17 thms2 active usersReviewed
CombinatoricsComputational ComplexityTheoretical Computer Science·Captain: Shuze Chen

Deterministic Connectivity Sketches Under Edge DeletionsResearch Paper

A graph is to be compressed so that, after any set of its edges is deleted, one can still tell whether the remaining graph is connected. The question links one-way communication, fault-tolerant connectivity oracles, and single-pass dynamic graph streaming. With randomness it is well understood: the linear sketches of Ahn, Guha and McGregor (AGM12) use …

25 thms2 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Improved Approximations for Two-Edge-Connected and Two-Vertex-Connected Spanning SubgraphsResearch Paper

A network that has to survive the failure of any single link must be 2-edge-connected: it stays connected after the deletion of any one edge. The minimum 2-edge-connected spanning subgraph problem (2ECSS) asks for such a network with the fewest links inside a given graph. It is a basic survivable network design problem, NP-hard (a solution on nnn vertices has…

46 thms2 active usersReviewed
CombinatoricsComputational ComplexityLinear algebra+1·Captain: Shuze Chen

Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph HomomorphismsResearch Paper

A graph homomorphism partition function assigns to a symmetric weight matrix M∈Rn×nM\in\mathbb R^{n\times n}M∈Rn×n and a graph G=(V,E)G=(V,E)G=(V,E) the number

23 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

The Power of Interaction in Locally Edge-Private Subgraph CountingResearch Paper

Subgraph counts (the number of triangles, stars, cycles or cliques in a network) are among the most widely used summaries of a graph. When the edges are sensitive relationships, releasing such counts leaks information, and differential privacy (Dwork, McSherry, Nissim, Smith 2006) is the standard way to bound that leakage. In the local model no trusted…

27 thms2 active usersReviewed
Captain: Shuze Chen

Maximal Isolating Vertex Cuts and Shredders: Structure and ApplicationsResearch Paper

A graph can remain connected after several vertices fail and then break into several pieces when one small set fails. The size of a smallest disconnecting vertex set measures resilience, but that number alone does not describe the failures that fragment the graph most severely. Listing the smallest cuts that produce three or more components exposes this…

29 thms2 active usersReviewed
CombinatoricsProbability·Captain: iris

Universality in random graphs via optimal linking systems: trees and beyondResearch Paper

A graph GGG is universal for a family F\mathcal FF if it contains a copy of every member of F\mathcal FF as a subgraph. Sparse universal graphs for bounded-degree trees were first studied for circuit design (Friedman–Pippenger 1987; Bhatt, Chung, Leighton and Rosenberg 1989). The probabilistic question is how large ppp must be for the binomial random graph G(n,p)G(n,p)G(n,p) to…

40 thms2 active usersReviewed
Combinatorics·Captain: Shuze Chen

Sharp Spectral Bounds for Kikuchi Matrices: The Hypergraph Moore Bound and Optimal Trade-offs for kkkXORResearch Paper

A collection of parity constraints can contain a small dependency: a nonempty collection of constraints in which every variable appears an even number of times. Such dependencies are combinatorial certificates, and their size measures how far a hypergraph resembles an acyclic object. For ordinary graphs, the smallest such collection is a shortest cycle. The…

23 thms2 active usersReviewed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: iris

Breaking the O(mn)O(mn)O(mn) Barrier for Minimum Bipartite Dijoin via Dynamic and Local Graph AlgorithmsResearch Paper

A dijoin of a digraph is a set of arcs whose contraction makes the digraph strongly connected; equivalently, a set of arcs meeting every dicut, the nonempty set of arcs crossing a vertex bipartition when all crossing arcs point the same way. Lucchesi and Younger proved in 1978 that the minimum size of a dijoin equals the maximum number of pairwise…

30 thms2 active usersReviewed
Theoretical Computer Science·Captain: Shuze Chen

Local Distributed Computation under Crash FailuresResearch Paper

In the LOCAL model of distributed computing, every node of a communication graph runs the same deterministic program, rounds are synchronous, messages are unbounded, and a problem's complexity is the number of rounds after which every node can produce its output. Without failures, a node learns its whole radius-RRR neighborhood in RRR rounds, so any TTT-round…

20 thms2 active usersReviewed
CombinatoricsComplexity TheoryLogic·Captain: Shuze Chen

Exact Counting and Sampling of Labeled Graphs of Bounded Treewidth with MSO PropertiesResearch Paper

Treewidth measures how closely a graph resembles a tree. Graphs of treewidth at most kkk have tree decompositions computable in linear time for fixed kkk (Bodlaender 1996), and Courcelle's theorem decides every fixed monadic second-order property on such graphs in linear time (Courcelle 1990; Arnborg, Lagergren and Seese 1991). These results analyze a given grap…

24 thms2 active usersReviewed
Captain: mikedeng1

Partially Dynamic Single-Source Shortest Paths in Almost-Linear TimeResearch Paper

A decremental shortest-path data structure receives a directed graph and a fixed source, then answers distance queries while edges disappear. A deletion can invalidate shortest paths to many vertices at once. Recomputing all distances after every deletion is therefore a useful baseline, but its total work can be much larger than the initial graph. The…

60 thms2 active usersReviewed
CombinatoricsProbability·Captain: mikedeng1

Adaptive Sparsifier Revisited: (1±ϵ)(1 \pm \epsilon)(1±ϵ)-Approximate, Fast, and SimpleResearch Paper

A spectral sparsifier replaces a graph by a smaller reweighted subgraph while approximately preserving the energy of every real vector on its vertices. This allows graph algorithms to use a smaller representation without losing the quadratic quantities they need. The source identifies Laplacian systems, random walks, and flow algorithms as applications. In…

20 thms2 active usersReviewed
Linear algebraTheoretical Computer Science·Captain: iris

Revisiting Local Push: Faster Algorithms and Optimal Query Complexity for PageRank and Effective ResistanceResearch Paper

Personalized PageRank from a seed node is the basic primitive of local graph algorithms: it drives local clustering by sweep cuts (Andersen, Chung, Lang 2007; Andersen, Chung 2007) and the bidirectional estimation of single PageRank values (Lofgren, Banerjee, Goel 2015). The standard local method is the push of Andersen, Chung and Lang. It computes an…

29 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Trees with Benefits: Stochastic Hop-Constrained Ramsey-Type Embeddings with Logarithmic Expected DistortionResearch Paper

Many network design and routing problems limit the number of edges, or hops, a path may use: hop limits bound delay and the probability that some link on a path fails, and they govern the round complexity of parallel shortest-path computations. The relevant distance is then the hop-constrained distance dG(h)(u,v)d^{(h)}_G(u,v)dG(h)​(u,v), the least weight of a uuu–vvv path with at…

31 thms2 active usersReviewed
PreviousPage 8 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