Reductions

A reduction solves a problem $A$ with an algorithm for a problem $B$, which runs on an instance built from the input graph $G$. If the algorithm for $B$ takes $T$ rounds on that instance, the reduction solves $A$ in the number of rounds given below.

$n', \Delta'$
Number of nodes and maximum degree of the instance.
$L(G)$
Line graph: one node per edge of $G$, adjacent if the edges share an endpoint.
$G \times K_{\Delta+1}$
$\Delta+1$ copies of every node; the copies of a node form a clique, and the $i$-th copies of adjacent nodes are adjacent.
$(C, D)$-ND
Network decomposition: clusters of diameter at most $D$, colored with $C$ colors so that adjacent clusters get different colors.
$c$
Number of colors of a given coloring.
Reductions between the problems
An arrow from $A$ to $B$: $A$ reduces to $B$, labelled with the instance if it is not $G$ itself. Click an arrow to see the reduction.

All reductions

Problem
From With runtime To Runtime Instance Models Source Technique