Graph Algorithms

Prev: Geometric Algorithms and Linear Programming Next: Approximate Counting

Problems

10.1

Suppose that the time required for Boolean matrix multiplication is $\mathrm{BM}(n)$. Show that the closure of a Boolean matrix can be computed in time $O(\mathrm{BM}(n))$.

---

10.2

Prove Lemma 10.1.

---

10.3

Prove Lemma 10.2.

---

10.4

Prove Lemma 10.3.

---

10.5

Prove Lemma 10.5.

---

10.6

Modify the BPWM algorithm so as to obtain a high probability bound on its running time.

---

10.7

Show that the product of $A^R$ and $B^R$ can be computed in time $O((n/r{)}^2\mathrm{MM}(r))$ by omitting the columns of $A^R$ and the rows of $B^R$ corresponding to the indices not present in $R$, and then multiplying these $n\times r$ and $r\times n$ matrices in blocks of $r\times r$ matrices.

---

10.8

Suppose that $\mathrm{MM}(n)=\Omega (n^{2+ϵ})$ for some $ϵ>0$. Show that it is possible to implement Algorithm BPWM such that its expected running time becomes $O(\mathrm{MM}(n)\log n)$. Why does this not work for $\mathrm{MM}(n)=O(n^2)$? (Hint: Use the idea suggested in Problem 10.7.)

---

10.9

Let $G(V,E)$ be a multigraph. Devise a data structure that processes any arbitrary sequence of edge contractions in $G$, such that at any given point where the set of edges contracted is $F$, the graph $G/F$ is available in the adjacency matrix format. Furthermore, it should be possible to efficiently determine for any edge in $E/F$ the corresponding edge in $E$. Your data structure should require $O(n)$ time per contraction and use a polynomial amount of space. Can you modify this to provide the adjacency list format for $G/F$ using only $O(m)$ space?

Remark: Note that the time bound is independent of the number of edges. For this, the multigraph needs to be represented as a graph with integer edge weights that represent the multiplicities of the edges. You may assume that the number of edges in the multigraph is polynomial in $n$, although this is not strictly necessary.

---

10.10

Given a multigraph $G(V,E)$, show that an edge can be selected uniformly at random from $E$ in time $O(n)$, given access to a source of random bits. (See the remark in Problem 10.9.)

---

10.11

Combining the solutions to Problems 10.9 and 10.10, prove Theorem 10.10. What is the space requirement for this implementation?

---

10.12

Prove Lemma 10.15.

---

10.13

Due to D.R. Karger [231].

For any $\alpha \ge 1$, define an $\alpha$-approximate cut in a multigraph $G$ as any cut whose cardinality is within a multiplicative factor $\alpha$ of the cardinality of a min-cut in $G$. Determine the probability that a single iteration of the randomized algorithm for min-cuts will produce as output some $\alpha$-approximate cut in $G$.

---

10.14

Due to D.R. Karger [231].

(a) Using the analysis of the randomized min-cut algorithm, show that the number of distinct min-cuts in a multigraph $G$ cannot exceed $n(n-1)/2$, where $n$ is the number of vertices in $G$.

(b) Formulate and prove a similar result for the number of $\alpha$-approximate cuts in a multigraph $G$ (see Problem 10.16).

---

10.15

Consider the min-cut problem in weighted graphs. Describe how you would generalize Algorithm Contract to this case. What is the running time and space requirement for your implementation?

---

10.16

Suppose that the edges of a graph are presented in an arbitrary order, and the number of edges $m$ is not known in advance. Using the idea for a greedy algorithm described in Section 10.3.2, devise an online MST algorithm that runs in time $O(m\log n)$.

---

10.17

Show that Boruvka’s algorithm can be implemented to run in time $O(\min \{m\log n,n^2\})$.

---

10.18

Show that Algorithm MST has the same worst-case running time as Boruvka’s algorithm, i.e., $O(\min \{m\log n,n^2\})$.