Search authors, problems, graph classes, or formulas. Recognized classes and problem names such as planar MDS use both inclusion networks. You can type epsilon, delta, and log-star. Press slash to focus search.
| Compare | Problem / graph class | Approximation | Rounds | Model / type | Reference | Citation and details |
|---|
No matching results
Try a broader graph class, model, or search term.
A second way in
Explore the landscape
Select a cell to open its results in the reference table.
Cell counts include certified problem specializations; a bound can appear in several cells. They describe catalog coverage, not relative algorithm quality. Degree, approximation and graph assumptions can differ within a cell.
Problem formulations
Problem inclusion network
Follow special cases, approximation reductions and LP relaxations. Select a node to highlight its connections.
For a reduction, the arrow points to the problem whose algorithm is used. Select an edge for the resulting approximation ratio, round complexity and conditions. A formulation or LP relaxation alone does not give an integral approximation.
Structural assumptions
Graph-class inclusion network
Select a class to see its contained and containing classes.
Solid lines are direct inclusions; dashed lines follow a path through intermediate classes. Drag to move and use the zoom controls to read labels. Parameter restrictions and source assumptions still apply.
From one algorithm to another
Reductions
Use an algorithm for one problem to solve another, with the instance and communication costs made explicit.
An arrow A → B means that an algorithm for B can solve A. Here T is the algorithm’s round complexity, α its approximation ratio, and n′, Δ′ the size and degree of its instance. Select an arrow to inspect the rule and its computed consequences.
| Problem solved | Algorithm used | Resulting rounds | Guarantee | Input instance | Models | Source | Technique |
|---|
No matching reductions
Try another problem, model or search term.
Rules run automatically when the catalog is built. Compatible new results gain derived rows and provenance chains; graph-class inclusions are followed transitively when browsing. Source assumptions remain required, and SOTA is certified separately. Inspired by the reductions in Florian Schager’s Atlas ↗.
The sources behind the bounds
Bibliography
Definitions and conventions
Reading the atlas
Approximation algorithms and lower bounds for LOCAL, CONGEST and other distributed models. Each row gives a problem, a graph class, an approximation ratio, a round complexity and a reference. The table groups results by round complexity.
Coverage
Communication models
The communication network is a graph G with n vertices. Each vertex runs an algorithm and communicates with its neighbors. Computation proceeds in synchronous rounds: vertices exchange messages and perform local computations. The round complexity is the number of rounds needed to finish.
LOCAL
- Vertices have distinct identifiers. Messages may have arbitrary size, and local computations are unrestricted.
CONGEST
- As in LOCAL, with messages limited to O(log n) bits per edge and per direction in each round.
Anonymous
- Vertices have no unique identifiers. When port numbering is available, a vertex distinguishes its neighbors by locally numbering its incident edges. Picavet, §X.1 ↗
SUPPORTED
- Vertices may preprocess a fixed communication graph and store information before the input is known. The round complexity counts only the rounds needed to solve each new input. Agrawal et al., §1.2 ↗
Initial information matters. The result details specify assumptions about identifiers, port numbering, known parameters, colorings or orientations. They also state whether messages are broadcast and how large they may be.
Round complexity and fixed parameters
The label Constant means a universal constant, independent of n and of the stated structural and accuracy parameters. We use Δ for the maximum degree, g for the Euler genus and ε for the accuracy parameter.
For instance, a round complexity of f(g, ε) is independent of n when g and ε are fixed. Such bounds appear under Parameter-dependent rounds, with their parameter dependence written explicitly. The function f may grow quickly with these parameters. The notation does not imply polynomial dependence. We use a capital F when f already denotes the source’s expansion function.
Explicit bounds keep their dependence on all parameters. Constants hidden in O(log* n) may also depend on fixed parameters. Exact bounds such as one round, k rounds and 3k rounds are kept separate. Hover over a parameter to read its definition, or focus it with the keyboard or tap it. The definitions depend on the result.
Open a result to see the most explicit round complexity extracted from its source. Details distinguish stated formulas from upper bounds obtained by counting communication phases. A Partial expansion still contains a function or quantity whose dependence has not been made explicit. If a finer expression is unavailable, the details say so.
Approximation ratio
OPT denotes the value of an optimal solution. For a minimization problem, a 2-approximation returns a solution of cost at most 2 OPT. For a maximization problem, the ratio 2 means a value of at least OPT / 2. A guarantee written as 1 − ε of OPT means a value of at least (1 − ε) OPT.
The approximation column shows the ratio without OPT. The marker OPT_f indicates a comparison with the fractional optimum.
Some problems have several versions. Open a result to check what the algorithm computes and which optimal value is used in the approximation ratio.
The approximation ratio and round complexity are recorded separately, with the parameter dependence of each. A factor depending on genus or expansion is written as a function of those parameters. The label Constant is reserved for a universal approximation factor.
Constant ratio shows guarantees with a fixed approximation factor. Ratios such as 7 + ε and 2t − 1 depend on parameters and are excluded.
For constant-round algorithms, a numerical count is given when it can be checked. The sign ≤ marks a conservative upper bound obtained by counting the communication phases. Open the result for the schedule and source. Constant remains when no total count could be established.
A lower bound gives a limitation on the approximation ratio or the number of rounds. For example, an Ω(log* n) lower bound rules out an o(log* n)-round algorithm under the stated assumptions.
For a lower bound on the approximation ratio, > α rules out an α-approximation, while ≥ α rules out every strictly smaller factor. In entries labeled rounds ruled out, this restriction applies to algorithms whose round complexity depends only on the listed parameters.
Graph classes
An algorithm for a graph class also applies to every subclass, under the same assumptions. For instance, an algorithm for general graphs applies to planar graphs. Conversely, a lower bound on cycles also holds for planar graphs, since every cycle is planar.
The graph-class filter uses these inclusions automatically. Open a result to see the inclusions used and the required parameters. Turn off Use inclusion network to restrict the table to results stated for the selected class.
Reductions
A reduction uses an existing algorithm in a new construction. For instance, the algorithm for graphs of Euler genus at most g uses an approximation algorithm for Minimum Dominating Set on planar graphs.
The Reductions page gives the construction and the resulting approximation ratio and round complexity for each listed reduction. The constructed graph and the message sizes must satisfy the assumptions of the algorithm used. The resulting algorithm must solve the original problem.
Entries marked Derived follow from an algorithm and one or more reductions. Their details give the original reference and each reduction. Turn off Use problem reductions to see only the original results.
Best known results
SOTA means state of the art. It marks best known results for the stated problem, graph class and model. The comparison takes into account the approximation ratio, round complexity, weights, randomness and input assumptions.
Tight · ratio and Tight · rounds identify matching approximation ratios and round complexities. Tight · up to constants means that the upper and lower bounds differ by at most a constant factor. The label and result details specify the graph class, model, parameter restrictions and matching sources. Tightness is recorded separately from the best-known comparison.
The Tight filter shows results with matching upper and lower bounds for the selected setting. It can be combined with SOTA, Constant ratio and the other filters.
These comparisons retain the dependence on all parameters. In particular, a bound f(g) retains its dependence on g when comparing results on graphs of bounded genus.
A better approximation ratio may require more rounds, so both results can be relevant. Being best known for a class does not imply being best known for every subclass. These comparisons use the literature, including results hidden by the current filters. The result details explain each SOTA label and give references. An unmarked result may not yet have been compared with all relevant work.
References
The atlas gives a selection of results. Each entry links to the cited theorem or section; consult the paper for the full statement and proof. Conference, journal and preprint versions can appear separately. Where a later paper reports a problem with a proof, the entry links to that discussion.
For entries marked Folklore, the details give an algorithm and a short proof. The reference indicates where the argument is recorded.
The terminology follows the introductions of Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors and Meta-Theorems for Cuttable Distributed Problems. The literature search also uses Feuilloley’s bibliography.
Using the table
Use the filters to select a problem, graph class or model. Brackets join adjacent rows for the same problem. Select an arrow to read the assumptions and reference, or select up to four rows to compare them. The Explorer shows the relationships between graph classes and problems; the Bibliography lists the papers.
The BibTeX button copies a citation. Export CSV downloads the filtered rows, and Export BibTeX downloads their references, once per paper. The full data are also available. A result’s Download correction template button prepares a file in which to describe a correction and its reference.
Acknowledgments
The organization is inspired by Florian Schager’s Atlas of Distributed Algorithms. The colors and graph drawings are inspired by Timothé Picavet’s homepage.