COMP3027/COMP3927 Tutorial questions The University of Sydney 2020 Semester 1 Tutorial 7 School of Computer Science
Pre-tutorial questions
Do you know the basic concepts of this week’s lecture content? These questions are only to test yourself. They will not be explicitly discussed in the tutorial, and no solutions will be given to them.
1. What are the running times of the various max flow algorithms discussed in the lecture? 2. Reductions
• What does it mean to reduce a problem to maximum flow?
• What are the components of a reduction?
• What does it mean to prove an equivalence between a problem and its maximum flow formulation? • What is the total time complexity of a reduction?
3. Bipartite matching.
(a) What is a bipartite matching?
(b) What is the maximum flow formulation of maximum bipartite matching?
(c) What does it mean to prove an equivalence between maximum bipartite matching and its maxi- mum flow formulation?
(d) What is the time complexity of the algorithm for maximum bipartite matching?
(e) What does the marriage theorem state?
(f) Why did we need to use integrality of max flow?
4. Edge disjoint paths
(a) What does it mean that two paths in a graph are edge disjoint?
(b) How can one use flow networks to count the maximum number of edge-disjoint paths?
5. Image segmentation
• What is the minimum cut formulation of the image segmentation problem?
• Why is image segmentation equivalent to its minimum cut formulation?
Tutorial
For each of the problems below, you need to design a reduction to either max flow or min cut.
Problem 1
Consider a generalization of the maximum flow problem where vertices have capacities. An instance is defined by a directed graph G = (V,E), a pair of vertices s and t, and vertex capacities c : V → Z+. A flow f : E → R≥0 is feasible if fout(u) ≤ c(u) for every vertex u ∈ V . The objective is to find a maximum feasible s-t flow.
1
Design an efficient algorithm for this problem by giving a reduction to the usual max flow problem.
Problem 2
Consider a generalization of the minimum cut problem where we want to separate two sets of vertices. An instance is defined by a graph G = (V, E), a pair of disjoint subsets of vertices S, T ⊆ V , and edge capacities c:E→Z+. Theobjectiveistofindaminimumcapacitycut(A,B)suchthatS⊆AandT ⊆B.
Design an efficient algorithm for this problem by giving a reduction to the usual max flow problem.
Problem 3
We want to wirelessly connect a set of mobile computers to a set of stationary base stations. Each computer u has an effective transmission radius ru. Suppose we know the spatial location of each computer and each base station. Our goal is to assign each computer to some station within its transmission radius. Define the load of a station to be the number of computers assigned to it.
Your task is to design a polynomial time algorithm that will produce a feasible computer-station assign- ment minimizing the maximum station load.
Problem 4
Given an undirected graph G = (V, E) and edge capacities c : E → R+ and two vertices s and t, design an algorithm for computing a minimum capacity s-t cut.
Problem 5
We define a new version of the game Capture the Flag. The game is played in a maze that consists of a large number of rooms that are connected by doors. Each door connects two rooms. Each player starts in a given room in the maze (different players may start in different rooms). From each room a player can decide to move to any adjacent room, going through a door, as long as the door is open. All doors are open in the beginning of the game, however, whenever a player crosses a door, the door will be closed and locked. That means, no other player will be able to go through that door, if they happen to find themselves in the same room at some point. So, when a player arrives in a new room, they can choose to go through any open door, but that door will be closed, and not available to anyone else from that point on. Some rooms contain a flag, and all flags are the same. Each player is trying to find a flag (any flag will do). A player can only pick up one flag. All players belong to the same team therefore they want to collect all flags if possible.
Here is the problem you need to solve. You are given the complete description of the maze, which consists of a set of rooms R, and a complete description of the set of doors D (which are pairs of rooms that are connected by a door). You are also given a set S ⊂ R, the initial k locations (rooms) of your team of k players. And you are given the set F ⊂ R, which are the k rooms that contain a flag. Your task is to check whether it is possible to find paths that your k players can follow in order to find all k flags, and no two paths cross the same door. Note that a given maze may not allow this, since doors can only be used once.
Given R,D, S and F , describe how to decide whether such a maze allows the collection of all flags or not.
Problem 6
A d-regular graph is one where every vertex has degree d. Prove that every d-regular bipartite graph has a perfect matching. Use marriage theorem.
Problem 7
In class we argued that Ford-Fulkerson runs for at most F iterations where F is the value of the max flow. If F is too large, this may take too long. Luckily, a variant of the algorithm can be shown to run for at most O(m log F ) iterations. The idea is very simple: Select an augmenting path maximizing the minimum residual capacity along the path. Show how to modify Dijkstra’s algorithm to find such a path in the residual graph Gf .
2