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
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

k-Coloring is Faster than Computing the Chromatic NumberResearch Paper

Graph coloring is one of the basic NP-complete problems, and its exact exponential-time complexity has been studied for decades. Computing the chromatic number χ(G)\chi(G)χ(G) of an nnn-vertex graph takes O∗(2n)O^*(2^n)O∗(2n) time by the inclusion–exclusion algorithm of Björklund, Husfeldt and Koivisto (SIAM J. Comput. 2009), where O∗O^*O∗ hides factors polynomial in the input size.…

17 thms2 active usersReviewed
CombinatoricsProbability·Captain: mikedeng1

Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation FactorsResearch Paper

The weighted girth of an undirected graph is the minimum total edge weight of a cycle. Computing this quantity asks for the least expensive closed route with no repeated intermediate vertex or edge. Approximation algorithms trade precision for running time: instead of finding the minimum exactly, they return a number within a specified multiplicative…

7 thms2 active usersReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

An EPTAS for Max-Cut on Interval GraphsResearch Paper

In Max-Cut one is given a graph G=(V,E)G=(V,E)G=(V,E) and asks for a set S⊆VS\subseteq VS⊆V maximizing cutG(S)\mathrm{cut}_G(S)cutG​(S), the number of edges with exactly one endpoint in SSS; mc(G)\mathrm{mc}(G)mc(G) denotes the maximum. On general graphs the Goemans–Williamson algorithm achieves the ratio αGW≈0.878\alpha_{GW}\approx0.878αGW​≈0.878, and beating it is NP-hard under the Unique Games Conjecture; …

31 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

Traveling Salesman Problem on Graphs with Proportional Independent SetResearch Paper

A Hamiltonian cycle, or tour, visits every vertex of a finite graph exactly once and returns to its starting vertex. The traveling salesman problem asks for a tour of minimum total edge cost, or a determination that no tour exists. It matters in exact combinatorial optimization because a fast feasibility algorithm need not extend to arbitrary weighted…

21 thms2 active usersReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

A King for Almost EveryoneResearch Paper

A collection of pairwise contests can have cyclic outcomes: one contestant defeats a second, the second defeats a third, and the third defeats the first. A useful substitute for a contestant who defeats everyone is a king: a vertex that reaches every other vertex either directly or through one intermediary. The question here concerns the information needed…

10 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

New bounds for online coloring three-colorable graphsResearch Paper

A proper coloring assigns different colors to adjacent vertices of a graph. In the online vertex-coloring problem, vertices arrive one at a time with their edges to earlier vertices, and each color choice is immediate and irrevocable. The algorithm has to commit before learning which future vertices will connect to its current color classes. This separates…

12 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

Testability of General Graphs with Weak Query OraclesResearch Paper

A graph property tester examines a small part of a graph and distinguishes graphs having a property from graphs requiring many changes to acquire it. Researchers studying sublinear graph algorithms need to know which properties admit a query bound independent of the number of vertices. That question depends on what a query reveals. An adjacency query can…

23 thms2 active usersReviewed
Probability·Captain: mikedeng1

Exact Fully Dynamic Single-Source Shortest Paths in Nonnegative Weighted GraphsResearch Paper

Single-source shortest paths (SSSP) with nonnegative arc weights is a basic primitive of routing, navigation and graph analytics. In many applications the graph changes one arc at a time, and recomputing all distances with Dijkstra's algorithm in O(m+nlog⁡n)O(m+n\log n)O(m+nlogn) time (Fredman–Tarjan 1987) after every change discards the fact that most distances are unaffected.…

26 thms2 active usersReviewed
Linear algebraTheoretical Computer Science·Captain: mikedeng1

A Tight Superlinear Lower Bound on the Sketching Dimension of Weighted Spectral SparsificationResearch Paper

A spectral sparsifier of a weighted graph is a matrix that approximately preserves every quadratic form of its Laplacian. Sparsifiers are used to compute cuts and flows, solve Laplacian systems and cluster graphs. In the linear sketching model the graph is accessible only through a small number of fixed linear measurements of its edge weights. This model…

28 thms2 active usersReviewed
CombinatoricsInformation Theory·Captain: mikedeng1

Optimal girth-dependent bounds for the Bethe approximation of the permanentResearch Paper

The permanent of an n×nn\times nn×n matrix, per(A)=∑σ∈Sym(n)∏iAi,σ(i)\mathrm{per}(A)=\sum_{\sigma\in\mathrm{Sym}(n)}\prod_i A_{i,\sigma(i)}per(A)=∑σ∈Sym(n)​∏i​Ai,σ(i)​, is the partition function of the weighted perfect-matching model, and computing it is #P-hard even for 0–1 matrices (Valiant 1979). Randomized approximation to any factor 1+ε1+\varepsilon1+ε is possible in polynomial time (Jerrum–Sinclair–Vigoda 2004),…

27 thms2 active usersReviewed
ProbabilityStatistics·Captain: iris

Distinguishability Threshold for Random Geometric GraphsResearch Paper

The binomial random graph G(n,p)G(n,p)G(n,p) joins every pair of nnn vertices independently with probability ppp. Many real networks are instead built from proximity: each vertex carries a hidden position, and nearby vertices are joined. The spherical random geometric graph G(n,d,p)G(n,d,p)G(n,d,p) is the high-dimensional version of this model. In high dimension the geometry should wash…

29 thms2 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

Hypergraph Recovery from Anonymous Projection StreamsResearch Paper

Many networks record interactions among whole groups, but the data often arrive only as low-order co-occurrences: which pairs, or which qqq-sets, of participants appeared together, and how often. The groups {a,b,c}\{a,b,c\}{a,b,c} and {a,b,d}\{a,b,d\}{a,b,d} contribute two copies of the pair {a,b}\{a,b\}{a,b}, and nothing in the counts says which copy came from which group. Counted pair…

46 thms2 active usersReviewed
Linear algebraProbability·Captain: iris

Integral saturation of adjacency-degree latticesResearch Paper

Start from the constant function e=(1,…,1)e=(1,\dots,1)e=(1,…,1) on the vertices of a graph and apply two operations: summing over neighbours (multiplication by the adjacency matrix AAA) and multiplying by the vertex degree (the diagonal matrix D=diag⁡(Ae)D=\operatorname{diag}(Ae)D=diag(Ae)). Over a field, the vectors obtained span a cyclic module, and asking whether it is the whole space is a…

53 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

Breaking the quantum barriers for Graph CollisionResearch Paper

In the graph collision problem a simple undirected graph G=(V,E)G=(V,E)G=(V,E) on nnn vertices is known in advance, and a quantum algorithm has query access to an input x∈{0,1}Vx\in\{0,1\}^Vx∈{0,1}V. The task is to decide whether some edge has both endpoints marked (xu=xv=1x_u=x_v=1xu​=xv​=1). Only queries to xxx are counted; all computation on the known graph is free.

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

Approximation Algorithms for Directed Telephone MulticastResearch Paper

Telephone broadcast and multicast model how a message spreads through a network in synchronous rounds: in each round every informed vertex may call one neighbour, and no vertex takes part in more than one call. The minimum number of rounds needed to reach a set of terminals measures how fast information can be disseminated over a fixed network (Hedetniemi,…

37 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Sublinear Time Clustering: Taming Random Walks in Arbitrary NoiseResearch Paper

Spectral clustering identifies communities in a graph: vertex sets that are well connected inside and sparsely connected to the rest. When a graph is very large and only a few membership questions must be answered, computing a spectral embedding of the whole graph is too expensive, and one asks instead for a clustering oracle: given two vertices, decide…

27 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Stochastic Matching with Polynomial DegreeResearch Paper

The stochastic matching problem of Blum et al. (EC 2015) models matching markets in which the availability of each potential pair is uncertain and can only be learned through a costly query: kidney exchange, where a compatibility test is expensive, online labor markets and online dating. A known graph G=(V,E)G=(V,E)G=(V,E) is given; each edge is realized independently…

17 thms2 active usersReviewed
AnalysisCombinatorics·Captain: iris

Graphon Colourings and Limits of Graph PartitionsResearch Paper

The Cheeger constant of a graph measures its worst bottleneck: the smallest ratio between the number of edges leaving a vertex set and the volume of that set. It controls the spectral gap of the random walk through the Cheeger–Buser inequalities, and through them mixing times, expansion and the quality of spectral partitioning.

50 thms2 active usersReviewed
CombinatoricsProbabilityQuantum Information·Captain: iris

Entanglement in random graph statesResearch Paper

Graph states are multi-qubit stabilizer states indexed by graphs (Hein, Eisert, Briegel, 2004, doi). They are used in measurement-based quantum computation, error correction and secret sharing, so it is useful to measure their entanglement by combinatorial invariants of the underlying graph. Two graph states are equivalent under single-qubit Clifford…

27 thms2 active usersReviewed
Complexity TheoryLinear algebraOptimization·Captain: iris

Maximum-Completion Forests via Sharp Spectral QuantizationResearch Paper

Determinant maximization asks, for a positive semidefinite matrix MMM and a budget kkk, for the kkk indices SSS maximizing det⁡MS\det M_SdetMS​. For a Gram matrix this is the squared volume spanned by the chosen vectors; in a fixed-size determinantal model it is the most likely subset. For general positive semidefinite matrices the best known deterministic polynomial-time…

96 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Parallel Edge Ranking of TreesResearch Paper

An edge ranking of a tree assigns positive integer ranks to its edges so that the path between any two distinct edges of equal rank contains an edge of higher rank. The edge ranking number er(T)\mathrm{er}(T)er(T) is the least possible maximum rank. This number gives the minimum worst-case number of edge queries needed to locate a target element in a tree, the…

27 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

A Near-Optimal Generalized Sorting AlgorithmResearch Paper

Ordinary comparison sorting assumes that any two elements can be compared. In many settings only some comparisons are possible or affordable: in the nuts and bolts problem a nut can only be compared with a bolt, and in pairwise preference or ranking problems only certain pairs are ever presented together. Generalized sorting, introduced by Huang, Kannan and…

51 thms2 active usersReviewed
Operations ResearchTheoretical Computer Science·Captain: iris

Tight Bounds for Sublinear Metric Steiner TreeResearch Paper

The metric Steiner tree problem asks for a cheapest tree connecting a prescribed set of terminals in a metric space, possibly through additional points. It is one of Karp's original NP-complete problems, with a best known polynomial-time ratio of ln⁡4+ε≈1.39\ln 4+\varepsilon\approx1.39ln4+ε≈1.39 (Byrka, Grandoni, Rothvoß, Sanità, J. ACM 2013).

31 thms2 active usersReviewed
Computational GeometryTheoretical Computer Science·Captain: iris

Tight Bounds for (1+ϵ)(1+\epsilon)(1+ϵ)-Approximation for Minimum Spanning Trees in Doubling MetricsResearch Paper

A minimum spanning tree (MST) of a finite metric space (X,d)(X,d)(X,d) is a spanning tree of the complete graph on XXX of least total edge length. Computing it exactly from a distance oracle takes Θ(n2)\Theta(n^2)Θ(n2) distance queries even in metrics of constant doubling dimension (Andoni et al., 2014), so the question is how fast a (1+ϵ)(1+\epsilon)(1+ϵ)-approximate MST, a spanning tree…

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

Polylog Pairwise Poise: Approximating Multicommodity MulticastResearch Paper

In the synchronous telephone model, each vertex of a graph can exchange any number of messages with at most one neighbor per round. Multicommodity multicast asks, given source–sink pairs (s1,t1),…,(sk,tk)(s_1, t_1), \dots, (s_k, t_k)(s1​,t1​),…,(sk​,tk​), to deliver each source's message to its sink within the minimum number of rounds. It generalizes the single-source problems known as…

51 thms2 active usersReviewed
PreviousPage 9 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