Applications of Flows and Cuts

Prev: Maximum Flows and Minimum Cuts Next: NP-Hardness

Exercises

1.

Let $G=(V,E)$ be a directed graph where for each vertex v, the in-degree and out-degree of v are equal. Suppose G contains k edge-disjoint paths from some vertex u to another vertex v. Under these conditions, must G also contain k edge-disjoint paths from v to u? Give a proof or a counterexample with explanation.

2.

Given an undirected graph $G=(V,E)$, with three vertices u, v, and w, describe and analyze an algorithm to determine whether there is a path from u to w that passes through v. [Hint: If G were a directed graph, this problem would be NP-hard!]

3.

Consider a directed graph $G=(V,E)$ with several source vertices $s_1,s_2,\dots ,s_{\sigma }$ and target vertices $t_1,t_2,\dots ,t_{\tau }$, where no vertex is both a source and a target. A multi-terminal flow is a function $f:E\to {\mathbb{R}}_{\ge 0}$ that satisfies the flow conservation constraint at every vertex that is neither a source nor a target. The value $|f|$ of a multi-terminal flow is the total excess flow out of all the source vertices:

$$|f|:=\sum _{i=1}^{\sigma }\left(\sum _{w}f(s_i\to w)-\sum _{u}f(u\to s_i)\right).$$

As usual, we are interested in finding flows with maximum value, subject to capacity constraints on the edges. (In particular, we don’t care how much flow moves from any particular source to any particular target.) (a) Consider the following algorithm for computing multi-terminal flows. The variables $f$ and $f^{\prime }$ represent flow functions. The subroutine MaxFlow(G, s, t) solves the standard maximum flow problem with source $s$ and target $t$.

MaxMultiFlow(G, s[1 .. σ], t[1 .. τ]):
f ←0
〈〈Initialize the flow〉〉
for i ← 1 to σ
for j ← 1 to τ
f' ← MaxFlow(G_f, s[i], t[j])
f ← f + f'
〈〈Update the flow〉〉
return f

Prove that this algorithm correctly computes a maximum multi-terminal flow in G. (b) Describe a more efficient algorithm to compute a maximum multiterminal flow in G.

4.

The Island of Sodor is home to a large number of towns and villages, connected by an extensive rail network. Recently, several cases of a deadly contagious disease (either swine flu or zombies; reports are unclear) have been reported in the village of Skarloey. The controller of the Sodor railway plans to close down certain railway stations to prevent the disease from spreading to Tidmouth, his home town. No trains can pass through a closed station. To minimize expense (and public notice), he wants to close down as few stations as possible. However, he cannot close the Skarloey station, because that would expose him to the disease, and he cannot close the Tidmouth station, because then he couldn’t visit his favorite pub. Describe and analyze an algorithm to find the minimum number of stations that must be closed to block all rail travel from Skarloey to Tidmouth. The Sodor rail network is represented by an undirected graph, with a vertex for each station and an edge for each rail connection between two stations. Two special vertices s and t represent the stations in Skarloey and Tidmouth. For example, given the following input graph, your algorithm should return the integer 2.

5.

An n × n grid is an undirected graph with n2 vertices organized into n rows and n columns. We denote the vertex in the ith row and the jth column by (i, j). Every vertex (i, j) has exactly four neighbors (i − 1, j), (i + 1, j), (i, j − 1), and (i, j + 1), except the boundary vertices, for which $i=1$, $i=n$, $j=1$, or $j=n$. Let (x 1, y1), (x 2, y2),…, (x m, ym) be distinct vertices, called terminals, in the n × n grid. The escape problem is to determine whether there are m vertex-disjoint paths in the grid that connect the terminals to any m distinct boundary vertices. (a) Describe and analyze an efficient algorithm to solve the escape problem. The running time of your algorithm should be a small polynomial function of n. (b) Now suppose the input to the escape problem consists of a single integer n and the list of m terminal vertices. If m is very small, the previous running time is actually exponential in the input size! Describe and analyze an algorithm to solve the escape problem in time polynomial in m. (c) Modify the previous algorithm to output an explicit description of the escape paths (if they exist), still in time polynomial in m.

6.

The SPU Commuter Silence Department is installing a mini-golf course in the basement of the See-Bull Center! The playing field is a closed polygon bounded by m horizontal and vertical line segments, meeting at right angles. The course has n starting points and n holes, in one-to-one correspondence. It is always possible hit the ball along a straight line directly from each starting point to the corresponding hole, without touching the boundary of the playing field. (Players are not allowed to bounce golf balls off the walls; too much glass.) The n starting points and n holes are all at distinct locations. Sadly, the architect’s computer crashed just as construction was about to begin. Thanks to the herculean efforts of their sysadmins, they were able to recover the locations of the starting points and the holes, but all information about which starting points correspond to which holes was lost! Describe and analyze an algorithm to compute a one-to-one correspondence between the starting points and the holes that meets the straight-line requirement, or to report that no such correspondence exists. The input consists of the x- and y-coordinates of the m corners of the playing field, the n starting points, and the n holes. Assume you can determine in constant time whether two line segments intersect, given the x- and y-coordinates of their endpoints.

7.

A cycle cover of a given directed graph $G=(V,E)$ is a set of vertex-disjoint cycles that cover every vertex in G. Describe and analyze an efficient algorithm to find a cycle cover for a given graph, or correctly report that no cycle cover exists. [Hint: Use bipartite matching!]

8.

Suppose you are given an n × n checkerboard with some of the squares deleted. You have a large set of dominos, just the right size to cover two squares of the checkerboard. Describe and analyze an algorithm to determine whether one tile the board with dominos—each domino must cover exactly two undeleted squares, and each undeleted square must be covered by exactly one domino. Your input is a boolean array $Deleted[1\dots n,1\dots n]$, where $Deleted[i,j]$ = True if and only if the square in row i and column j has been deleted. Your output is a single boolean; you do not have to compute the actual placement of dominos. For example, for the board shown in Figure 11.12, your algorithm should return True.

9.

Suppose we are given an n × n square grid, some of whose squares are colored black and the rest white. Describe and analyze an algorithm to determine whether tokens can be placed on the grid so that • every token is on a white square; • every row of the grid contains exactly one token; and • every column of the grid contains exactly one token.

Your input is a two dimensional array $IsWhite[1\dots n,1\dots n]$ of booleans, indicating which squares are white. Your output is a single boolean. For example, given the grid in Figure 11.13 as input, your algorithm should return True.

10.

Suppose we are given a set of boxes, each specified by their height, width, and depth in centimeters. All three side lengths of every box lie strictly between 10cm and 20cm. As you should expect, one box can be placed inside another if the first box can be rotated so that its height, width, and depth are respectively smaller than the height, width, and depth of the second box. Boxes can be nested recursively. Call a box is visible if it is not inside another box. Describe and analyze an algorithm to nest the boxes so that the number of visible boxes is as small as possible.

11.

Suppose we are given an n× n grid, some of whose cells are marked; the grid is represented by an array $M[1\dots n,1\dots n]$ of booleans, where $M[i,j]$ = True if and only if cell (i, j) is marked. A monotone path through the grid starts at the top-left cell, moves only right or down at each step, and ends at the bottom-right cell. Our goal is to cover the marked cells with as few monotone paths as possible. (a) Describe an algorithm to find a monotone path that covers the largest number of marked cells. (b) There is a natural greedy heuristic to find a small cover by monotone paths: If there are any marked cells, find a monotone path π that covers the largest number of marked cells, unmark any cells covered by π those marked cells, and recurse. Show that this algorithm does not always compute an optimal solution. (c) Describe and analyze an efficient algorithm to compute the smallest set of monotone paths that covers every marked cell.

12.

The Faculty Senate at Sham-Poobanana University has decided to convene a committee to determine whether Uncle Gabby, Professor Bobo Cornelius, or Mofo the Psychic Gorilla should replace the recently disgraced Baron Factotum as the new official mascot symbol of SPU’s athletic teams (The Fighting Pooh-bahs). Exactly one faculty member must be chosen from each academic department to serve on this committee. Some faculty members have appointments in multiple departments, but each committee member can represent only one department. For example, if Prof. Blagojevich is affiliated with both the Department of Corruption and the Department of Stupidity, and he is chosen as the Stupidity representative, then someone else must represent Corruption. Finally, University policy requires that every faculty committee must contain exactly the same number of assistant professors, associate professors, and full professors. Fortunately, the number of departments is a multiple of 3. Describe and analyze an algorithm to choose a subset of the SPU faculty to staff The Post-Factotum Simian Mascot Symbol Committee, or correctly report that no valid committee is possible. Your input is a bipartite graph indicating which professors belong to which departments; each professor vertex is labeled with that professor’s rank (assistant, associate, or full).

13.

The Department of Commuter Silence at Sham-Poobanana University has a flexible curriculum with a complex set of graduation requirements. The department offers n different courses, and there are m different requirements. Each requirement specifies a subset of the n courses and the number of courses that must be taken from that subset. The subsets for different requirements may overlap, but each course can be used to satisfy at most one requirement. For example, suppose there are $n=5$ courses A, B, C, D, E and $m=2$ graduation requirements: • You must take at least 2 courses from the subset {A, B, C}. • You must take at least 2 courses from the subset {C, D, E}. Then a student who has only taken courses B, C, D cannot graduate, but a student who has taken either A, B, C, D or B, C, D, E can graduate.

Describe and analyze an algorithm to determine whether a given student can graduate. The input to your algorithm is the list of m requirements (each specifying a subset of the n courses and the number of courses that must be taken from that subset) and the list of courses the student has taken.

14.

You’re organizing the First Annual SPU Commuter Silence 72-Hour Dance Exchange, to be held all day Friday, Saturday, and Sunday. Several 30-minute sets of music will be played during the event, and a large number of DJs have applied to perform. You need to hire DJs according to the following constraints. • Exactly k sets of music must be played each day, and thus 3k sets altogether. • Each set must be played by a single DJ in a consistent music genre (ambient, bubblegum, dubstep, horrorcore, K-pop, Kwaito, mariachi, straight-ahead jazz, trip-hop, Nashville country, parapara, ska,…). • Each genre must be played at most once per day. • Each candidate DJ has given you a list of genres they are willing to play. • Each DJ can play at most three sets during the entire event. Suppose there are n candidate DJs and g different musical genres available. Describe and analyze an efficient algorithm that either assigns a DJ and a genre to each of the 3k sets, or correctly reports that no such assignment is possible.

15.

Suppose you are running a web site that is visited by the same set of people every day. Each visitor claims membership in one or more demographic groups; for example, a visitor might describe himself as male, 40–50 years old, a father, a resident of Illinois, an academic, a blogger, and a fan of Gilbert and Sullivan.13 Your site is supported by advertisers. Each advertiser has told you which demographic groups should see its ads and how many of its ads you must show each day. Altogether, there are n visitors, k demographic groups, and m advertisers. Describe an efficient algorithm to determine, given all the data described in the previous paragraph, whether you can show each visitor exactly one ad per day, so that every advertiser has its desired number of ads displayed, and every ad is seen by someone in an appropriate demographic group.

16.

Suppose we are given an array $A[1\dots m,1\dots n]$ of non-negative real numbers.

We want to round $A$ to an integer matrix, by replacing each entry $x$ in $A$ with either $\lfloor x\rfloor$ or $\lceil x\rceil$, without changing the sum of entries in any row or column of $A$. (a) Describe and analyze an efficient algorithm that either rounds A in this fashion, or reports correctly that no such rounding is possible. (b) Prove that a legal rounding is possible if and only if the sum of entries in each row is an integer, and the sum of entries in each column is an integer. In other words, prove that either your algorithm from part (a) returns a legal rounding, or a legal rounding is obviously impossible. (c) Suppose we are guaranteed that none of the entries in the input matrix A is an integer. Describe and analyze an even faster algorithm that either rounds A or reports correctly that no such rounding is possible. For full credit, your algorithm must run in $O(mn)$ time. [Hint: Don’t use flows.]

17.

Ad-hoc networks are made up of low-powered wireless devices. In principle14, these networks can be used on battlefields, in regions that have recently suffered from natural disasters, and in other hard-to-reach areas. The idea is that a large collection of cheap, simple devices could be distributed through the area of interest (for example, by dropping them from an airplane); the devices would then automatically configure themselves into a functioning wireless network. These devices can communicate only within a limited range. We assume all the devices are identical; there is a distance D such that two devices can communicate if and only if the distance between them is at most D. We would like our ad-hoc network to be reliable, but because the devices are cheap and low-powered, they frequently fail. If a device detects that it is likely to fail, it should transmit its information to some other backup device within its communication range. We require each device x to have k potential backup devices, all within distance D of x; we call these k devices the backup set of x. Also, we do not want any device to be in the backup set of too many other devices; otherwise, a single failure might affect a large fraction of the network. So suppose we are given the communication radius D, parameters b and k, and an array $d[1\dots n,1\dots n]$ of distances, where $d[i,j]$ is the distance between device i and device j. Describe an algorithm that either computes a backup set of size k for each of the n devices, such that no device appears in more than b backup sets, or reports (correctly) that no good collection of backup sets exists.

18.

Faced with the threat of brutally severe budget cuts, Potemkin University has decided to hire actors to sit in classes as “students”, to ensure that every class they offer is completely full. Because actors are expensive, the university wants to hire as few of them as possible. Building on their previous leadership experience at the now-defunct Sham-Poobanana University, the administrators at Potemkin have given you a directed acyclic graph $G=(V,E)$, whose vertices represent classes, and where each edge $i\to j$ indicates that the same “student” can attend class i and then later attend class j. In addition, you are also given an array $cap[1\dots V]$ listing the maximum number of “students” who can take each class. Describe an analyze an algorithm to compute the minimum number of “students” that would allow every class to be filled to capacity.

19.

Quentin, Alice, and the other Brakebills Physical Kids are planning an excursion through the Neitherlands to Fillory. The Neitherlands is a vast, deserted city composed of several plazas, each containing a single fountain that can magically transport people to a different world. Adjacent plazas are connected by gates, which have been cursed by the Beast. The gates between plazas are open only for five minutes every hour, all simultaneously—from 12:00 to 12:05, then from 1:00 to 1:05, and so on—and are otherwise locked. During those five minutes, if more than one person passes through any single gate, the Beast will detect their presence.15 Moreover, anyone attempting to open a locked gate, or attempting to pass through more than one gate within the same five-minute period will turn into a niffin.16 However, any number of people can safely pass through different gates at the same time and/or pass through the same gate at different times. You are given a map of the Neitherlands, which is a graph G with a vertex for each fountain and an edge for each gate, with the fountains to Earth and Fillory clearly marked. (a) Suppose you are also given a positive integer h. Describe and analyze an algorithm to compute the maximum number of people that can walk from the Earth fountain to the Fillory fountain in at most h hours—that is, after the gates have opened at most h times—without anyone alerting the Beast or turning into a niffin. The running time of your algorithm should depend on h. [Hint: Build a different graph.] (b) Describe an analyze an algorithm for part (a) whose running time is polynomial in V and E, with no dependence on h. (c) On the other hand, suppose you are also given an integer k. Describe and analyze an algorithm to compute the minimum number of hours that allow k people to walk from the Earth fountain to the Fillory fountain, without anyone alerting the Beast or turning into a niffin. [Hint: Use part (a).]

20.

Let $G=(L\bigsqcup R,E)$ be a bipartite graph, whose left vertices $L$ are indexed ${\ell }_1,{\ell }_2,\dots ,{\ell }_n$ and whose right vertices are indexed $r_1,r_2,\dots ,r_n$. A matching $M$ in $G$ is non-crossing if, for every pair of edges ${\ell }_i{r}_j$ and ${\ell }_{i^{\prime }}{r}_{j^{\prime }}$ in $M$, we have $i<i^{\prime }$ if and only if $j<j^{\prime }$. (a) Describe and analyze an algorithm to find the largest non-crossing matching in G. [Hint: This is not really a flow problem.] (b) Describe and analyze an algorithm to find the smallest number of noncrossing matchings M1, M2,…, Mk such that each edge in G is in exactly one matching Mi. [Hint: This is really a flow problem.]

21.

Let $G=(L\bigsqcup R,E)$ be a bipartite graph, whose left vertices $L$ are indexed ${\ell }_1,{\ell }_2,\dots ,{\ell }_n$ in some arbitrary order. (a) A matching $M$ in $G$ is dense if there are no consecutive unmatched vertices in $L$; that is, for each index $i$, at least one of the vertices ${\ell }_i$ and ${\ell }_{i+1}$ is incident to an edge in $M$. Describe an algorithm to determine whether $G$ has a dense matching. (b) A matching $M$ in $G$ is sparse if there are no consecutive matched vertices in $L$; that is, for each index $i$, at least one of the vertices ${\ell }_i$ and ${\ell }_{i+1}$ is not incident to an edge in $M$. (In particular, the empty matching is sparse.) Describe an algorithm to find the largest sparse matching in $G$. (c) A matching $M$ in $G$ is palindromic if, for every index $i$, either ${\ell }_i$ and ${\ell }_{n-i+1}$ are both incident to edges in $M$, or neither ${\ell }_i$ nor ${\ell }_{n-i+1}$ is incident to an edge in $M$. (In particular, the empty matching is palindromic.) Describe an algorithm to find the largest palindromic matching in $G$. None of these problems restrict which vertices in $R$ are matched or unmatched.

22.

A rooted tree is a directed acyclic graph, in which every vertex has exactly one incoming edge, except for the root, which has no incoming edges. Equivalently, a rooted tree consists of a root vertex, which has edges pointing to the roots of zero or more smaller rooted trees. Describe an efficient algorithm to compute, given two rooted trees A and B, the largest rooted tree that is isomorphic to both a subgraph of A and a subgraph of B. More briefly, describe an algorithm to find the largest common subtree of two rooted trees. [Hint: This would be a relatively straightforward dynamic programming problem if either every node had $O(1) children or the children of each node were ordered from left to right. But for unordered trees with large degree, you need another technique to combine recursive subproblems efficiently.]

Prev: Maximum Flows and Minimum Cuts Next: NP-Hardness