College of Computer & Information Science Fall 2014 Northeastern University Handout 12 CS7800: Advanced Algorithms 14 October 2014

Problem Set 4 (due Thursday, October 23)

1. (10 points) The escape problem

Problem 26-1 of text.

2. (7 + 8 = 15 points) Updating the maximum flow

Problem 26-4 of text.

3. (10 + 5 = 15 points) Tight-knit communities in social networks

Social networks are all the craze these days. Assuming that friendship links are symmetric, one can represent a social network such as Facebook as an undirected unweighted graph G. Identifying clusters, communities, and other connectivity properties is a hot topic of research.

Suppose you want to identify a tight-knit community in a social network G. For a given set S of nodes in G, let n(S) denote the number of edges with both endpoints in S. Define the connectedness of any set S of nodes in G to be n(S)/|S|. Larger the n(S), the more tight-knit n(S) is; dividing by |S| normalizes across sets of different sizes.

(a) Give a polynomial time algorithm that takes a rational number α and determines whether there exists a set S with connectedness at least α.

(b) Use the above algorithm to find a set S of nodes with maximum connectedness.

4. (5 + 2 + 3 = 10 points) Pathalogical example for the basic augmenting path algorithm

In the residual network G_{f} corresponding to a flow f, define an augmenting walk as a directed walk from source s to sink t that visits any arc at most once (it might visit nodes multiple times– in particular, an augmenting walk might visit nodes s and t multiple times). Define the residual capacity of an augmenting walk to be the residual capacity (i.e., capacity in G_{f}) of the minimumcapacity edge in the walk.

(a) Consider the network shown in Figure 1(a) with the edges labeled a, b, c, and d; note that one arc capacity is irrational. Show that this network contains an infinite sequence of augmenting walks whose residual capacities sum to the maximum flow value. (Hint : Each augmenting walk of the sequence contains exactly two arcs from node s to node t with finite residual capacities.)

(b) Now consider the network shown in Figure 1(b). Show that this network contains an infinite sequence of augmenting walks whose residual capacities sum to a value different than the maximum flow value.

a bcd s  t 1 ∞ ∞^{\sqrt{2}} a bcd s  t 1 ∞ ∞^{\sqrt{2}} e  1  ∞∞ ∞ ∞  ∞ ∞ ∞∞ ∞ ∞ 1^{\sqrt{2}} 12 34  1′ 2′ 3′ 4′ s  t 1

Figure 1: A pathological example for the basic augmenting path algorithm.

(c) Next consider the network shown in Figure 1(c); in addition to the edges shown, the network contains an infinite capacity edge connecting each node pair in the set {1, 2, 3, 4} as well as each node pair in the set {1′, 2′, 3′, 4′}. Show that each augmenting walk in the solution of part (b) corresponds to an augmenting path in Figure 1(c). Conclude the basic augmenting path algorithm, when applied to a maximum flow problem with irrational capacities, might perform an infinite sequence of augmentations and the terminal flow value might be different than the maximum flow value.