Algorithms for telecommunications: class #6

Topics

  1. Applications of flows:
    1. Find maximum matching
    2. Find disjoint paths
  2. Shortest path algorithms:
    1. Dijkstra's algorithm: greedy, positive weights.(4.4 in the book)
    2. Bellman-Ford: dynamic programming, allows negative weights. (6.8 in the book)

Bibliography

  • Algorithm design; Kleinberg & Tardos (available in The pirate bay, rapidshare and friends)
  • Wikipedia article

Application of flows

The bipartite match problem

A bipartite graph G = (V, E) is an undirected graph whose node set can be partitioned as $V = X \cup Y$, with the property that each edge $e \in E$ has one end in X and the other in Y.

A matching M in G is a subset of the edges $M \subseteq E$, such that each node appears in at most one edge in M.

The bipartite matching problem is that of finding a matching in a bipartite graph with the largest possible size.

Algorithm

Remark: other flow problems seen used directed graphs. This is a problem on undirected graphs.

We take the graph G and construct a flow network G' as follows:

  1. We direct all edges from X to Y (need to partition the graph first).
  2. We add a node s, and an edge from s to each node in X.
  3. We do the same with a new node t and all nodes in Y.
  4. Finally, we give each edge in G' a capacity of 1.

We now compute the maximum flow between s and t. We will see that the value of this flow is equal to the size of the maximum matching in G.

Analysis

Suppose there is a matching in G consisting of k edges $(x_{i_1}, y_{i_1}) \dots (x_{i_k}, y_{i_k})$, the we consider the flow f that sends one unit along each path of the form $(s, x_{i_j}, y_{i_j}, t)$. $f(e) = 1$ for each edge in the path. It is easy to see that f is a flow of value k.

Conversely, suppose there is a flow f' in G' of value k.

We use here the integrality theorem (??): if all capacities in the flow network are integers, then there is a maximum flow g in which g(e) is an integer for every edge e in G'.

Since all capacities are 1, this means that g(e) is either 0 or 1. Now we consider the set M' of edges of the form (x, y) in which the flow value is 1.

M' contains k edges: consider the cut (A, B) of G', with $A = {s} \cup X$. The value of the flow is the total flow leaving A (minus the total flow entering A, which is 0). The total flow leaving A is the number of edges of M', since them are the edges leaving A that carry flow, and each carries exactly one unit.

Each node in X is the tail of at most one edge in M': to prove this, suppose $x \in X$ where x is the tail of at least two edges in M'. Since our flow is integer valued, this means that at least two units of flow leave from x. By conservation of flow, at least 2 units of flow would have to enter c, which is impossible with only one edge of capacity 1.

Each node in Y is the head of a most one edge in M': not explained?? I suppose is the same "proof" as before.

Combining those facts, we see that if we view M' as a set of edges in the original bipartite graph, we get a matching of size k.

Conclusion: the size of a maximum matching in G is equal to the value of a maximum flow in G'; and the edges in such a matching are the edges that carry flow from X to Y.

Note of the typist: the important part of the proof is that there is a bijection between any matching of size k and any flow of value k, so a maximum flow is also a maximum matching.

Complexity

  • Complexity of the Ford-Fulkenson algorithm: suppose that all capacities in the flow network G' are integers. Then the FF algorithm can be implemented in $O(mC)$ time, with $C = \sum_{e \in E, e = (s, x)} c_e$. Then, the complexity of finding the maximum matching is in $O(mn)$ time, with $n = |X|, m = |E|$.

Disjoint path in directed and undirected graphs

We say that a set of paths is edge-disjoint if their edge ests are disjoint, that is, no two paths share and edge. Multiple paths may go through some of the same nodes.

Given a directed graph $G = (V, E)$, with two distinguished nodes $s, t \in V$, the directed edge-disjoint paths problem is to find the maximum number of edge-disjoint paths.

Algorithm

We put a capacity of 1 in all the edges and we solve the corresponding flow problem.

Directed graph

  1. We transform the undirected graph G into a directed graph G' by replacing all undirected edges with two edges of opposite direction.
  2. We remove edges entering s and edges leaving t.
  3. We put one as a capacity on all edges

Then, we solve the maximum flow problem on G'

difficulty: the maximum flow in G' could have a couple of edges (i, j) and (j, i) with positive flow. This will give a solution with paths that are disjoint in G' but not in G. If we have a flow f like this, then there exist a flow f' with the same values but replacing the flows with the values 0 and $|f(i, j) - f(j, i)|$ to the edges in f with less and more flow, respectively. (this will not happen here, all flows are 0 or 1, we just replace with 0).

Shortest path algorithms

A weighted (or labeled) graph is a pair $(G, w)$ with $G = (V, E)$ and $w : E \rightarrow \mathbb{R}$ (the weight function).

The distance between two nodes u and v, noted $\textrm{dist}_G(u, v)$ is the minimum lenght of a path between then. In the case of a non-weighted graph, it corresponds to the path with minimal number of edges (they can be considered as having weight 1 on all edges).

In an undirected graph, we have $\textrm{dist}_G(u, v) = \textrm{dist}_G(v, u)$.

The shortest path problem is to calculate $\textrm{dist}_G(u, v)$ and to give the corresponding path. In unweighted graphs, the problem is easy to solve with a breadth first search.

To solve this problem, we will solve a more general problem:

Shortest path tree problem

Let (G, w) be a weighted graph and a rooted node r (?). We want to find a tree T such that it is a subgraph of G, rooted in r such that $\forall x \in V, \textrm{dist}_G(r, x) = \textrm{dist}_T(r, x)$.

Dijksgtra's algorithm

NOTE: this notes doesn't make much sense (and it's not my fault), read the book, page 137.

The algorithm is based on the following principle: let $S \subset V(G)$, with $r \in S$ and let $\bar{S} = V(G) \setminus S$.

If $P = (r, s_1 \dots s_k, \bar{s})$ is the minimum shortest path from r to any node in $\bar{S}$, then $s_k \in S$. So,

(1)
\begin{align} \textrm{dist}(r, \bar{s}) = \textrm{dist}(r, s_k) + w(s_k, \bar{s}) \end{align}

and the distance from r to $\bar{S}$ is given by the formula

(2)
\begin{align} \textrm{dist}(r, \bar{S}) = \min_{u \in S, v \in \bar{S}} \{ dist(r, u) + w(u, v) \} \end{align}

Another way to see it: Dijkstra is a greedy algorithm which at each time step finds the shortest path to a new node.


To improve the complexity, we associate to each node $v \in V(G)$, a function $d'(v)$ which is an upper bound for $\textrm{dist}(r, v)$, and a node p(v) which is the potential father of v in the tree. At each step i, we have

(3)
\begin{align} d'(v) = \left \begin{array}{ll} \textrm{dist}(r, v) & \textrm{if}\ v \in V(T \end{align}
Unclear, need to ask the teachers, since most is obviously derived works.