DSzoo:Dynamic Graph Problems

212,941pages on
this wiki
Add New Page
Add New Page Discuss this page0

This page only covers fully dynamic problems in general graphs.

Virtually all problems have an \Omega(\lg n) lower bound inherited from connectivity in dynamic forests. For dynamic trees, this is tight, but in general graphs the problems are not too well understood:

  • certain "easy" problems on undirected graphs have polylogarithmic bounds. It is not clear whether the optimal bounds should be O(\lg n) or higher.
  • for problems on directed graphs, as well as "hard" problems on undirected graphs, it is believed that sublinear bounds (in an appropriate sense) are not possible. However, no strong beliefs exist about the optimal bounds, especially for sparse graphs.

Most of the upper bounds are amortized, and many are randomized. Deamortizing (and derandomizing) these bounds is a well-known open problem. In most cases, the gaps are very large. In addition, many constructions do not use $O(m)$ space (the optimal space for storing the graph). Obtaining optimal space, where it has been achieved, required interesting graph-theoretic observations.

Dynamic Trees

In general we are talking about forests, but the name "dynamic trees" is standard.

Upper bounds of O(\lg n) are known for updates and virtually any query. One can achieve an update/query tradeoff of t_q \lg \frac{t_u}{t_q} = O(\lg n). Bounds are deterministic, worst-case.

A matching cell-probe lower bound and tradeoff is known [PD85], even for connectivity queries. The bounds apply to randomized, amortized, and even nondeterministic algorithms.

Teaching: The lower bound via the "time tree technique" (from the original paper) is one of the simplest lower bounds around.

Two well-known algorithms are:

  • Euler-tour trees [TOADD]. They can be used to answer subtree queries (e.g. count the number of nodes below a given node).
Teaching: These are very easy to present: simply maintain a dynamic list with the Euler tour of the tree. They immediately achieve worst-case bounds, and the optimal update/query tradeoff.
  • link-cut trees [ST83]. These can be used to find LCAs (even with a dynamically chosen root), and answer a variety of path queries (e.g. min on a path).
Teaching: The implementation breaks the tree into preferred paths and builds a search tree on each path. A beautiful amortized analysis involving the heavy-light decomposition shows an O(\lg^2 n) bound. To achieve O(\lg n), one needs to bias the search trees depending on the size of the subpaths. Biased trees achieve this explicitly, while splay trees achieve it implicitly because they are optimal for any weights. Good illustration of the power of splay trees, with an independent motivation.

"Easy" Problems on Undirected Graphs




Directed Graphs and Hard Problems


Shortest Paths

s-t MinCut

Also on Fandom

Random wikia