Exercises Matching Flow
Exercises Matching Flow
1. A stable matching is called institute optimal if every institute gets the highest possible preference it
can get in any stable matching. Prove that the algorithm we saw in the class was gives an institute
optimal stable matching. If you want a student optimal stable matching, what will be your algorithm?
2. Define the notion of stable matchings when vertices have a preference order over only a subset of the
other side vertices. The number of vertices need not be equal on the two sides. How will you modify
the Gale Shapely algorithm to work in this more general setting. Show that a stable matching always
exists.
3. Is it possible that there is no stable matching with size equal to maximum size matching in the graph.
The graph we consider here is as follows: there is an edge between ui and vj if ui is in the preference
list of vj and vj is in the preference list of ui .
4. In the roommate allocation problem, we have a complete (non-bipartite) graph. Every vertex has a
preference order over the remaining n − 1 vertices. Find an example where there is no stable matching.
5. Have a look at the guidelines of the COAP (common offer acceptance portal). Do you think their
algorithm always gives a stable matching. The offers are given by institutes to multiple students in
parallel. In 2024, they did 10 such rounds of institutes making offers and students retaining/rejecting.
How many rounds should be sufficient for all possible scenarios? Do you think there is an alternative
approach, where the whole process can be done in one day.
6. For an s-t path, the bottleneck is defined to be the least capacity of an edge on that path. Can you
design an efficient algorithm to find the s-t path with largest bottleneck? Or try this variant: given a
threshold λ, is there an s-t path where every edge has capacity at least λ?
7. Construct a flow network with irrational capacities, where it is possible that the maximum flow algo-
rithm takes infinite iterations. Note that there can be a clever way of choosing s-t paths. Here we are
just saying that there is a possibility of choosing paths that leads to infinite iterations.
8. Try to design a scaling
P version of the max flow algorithm, that is, where the number of iterations is
proportional to log( e ce ).
Hint: take a parameter ∆, which will initially be large and will become smaller over time. First, ignore
all the edges whose capacity is less than ∆, and run the max flow algorithm. When it is no longer
possible to increase the flow, then reduce the value of ∆ appropriately and repeat.
9. Use max flow algorithm to solve the following problem. Given a graph with a source vertex s and
a destination vertex t, find the minimum number of vertices which can be removed to make s and t
disconnected.
10. TA allocation: for each TA, we are given a list of suitable courses. For each course we are given the
required number of TAs. We want to check whether a TA allocation is possible meeting all course
demands, where a TA is only assigned to one of their suitable courses. Design an algorithm for this
problem using network flow.
Use max flow min cut theorem to prove the following: if the above TA allocation is not possible then
there must be a subset S of courses whose total demand is larger than the total number suitable TAs
for them. This is also known as Hall’s theorem.
1
11. Recall the algorithm we discussed for partitioning a poset (partially ordered set) into minimum number
of chains. The algorithm went via the bipartite matching algorithm. First, for the given poset P on n
elements, we construct a bipartite graph GP on n + n vertices, say {`1 , `2 , . . . , `n } and {r1 , r2 , . . . , rn }.
We have an edge (ri , `j ) in GP if and only if i ≤ j in the poset.
• Prove that from a matching of size n − k in GP , we can get a partition of P into k chains. What
happens with the unmatched vertices.
• Prove that for every partition of P into k chains, there is a corresponding matching of size n − k
in GP .
• Prove the optimality of the obtained partition into chains.
12. Use the max flow min cut theorem to prove Dilworth’s theorem. That is, for any partially ordered set,
the minimum number of chains in which we can partition the set is equal to the maximum antichain
(i.e., maximum number of mutually incomparable elements). You can use the above reduction to
bipartite matching and then a reduction to max flow. Assume max flow is equal to s-t-minimum-cut.
Then given an s-t cut with outgoing capacity of n − k, try to construct an antichain of size k.
13. Vertex Cover: a set of vertices S such that every edge in the graph has at least one end point in S.
Observe that for any vertex cover S and any matching M , we have |S| ≥ |M |.
Use max flow min cut theorem to prove that in bipartite graphs, maximum matching size is equal to
minimum vertex cover size.
14. Project selection We are given a set of projects, where some projects are pre-requisites for others.
This can be represented by a direct acylic graph on projects. An edge from i to j represents that
i is a pre-requisite for j. Clearly this is a transitive relation. A project can be done only if all its
pre-requisite projects have been done.
Some projects might have a positive value, i.e., you gain a net profit from them. While some other
projects may have a negative value, i.e., you have to invest more into them than what you gain from
them. The goal is to select a subset of projects which maximizes the total value, under the constraint
that if a project is selected then all its pre-requisites must also be selected.
Reduce this problem to s-t-minimum-cut problem. That is design an algorithm which can use s-t-
minimum-cut subroutine. Note that minimum cut is also a subset (of vertices) selection problem.
15. Tiger counting: The tiger population in the country is counted once in every four years. To count their
number, cameras are installed in the areas visited by them. Tigers are uniquely identified by their
stripes. Interestingly, the stripes on the two sides of a tiger are not correlated. Hence, they always
install cameras in pairs, where the two cameras face each other. This way they can get pictures from
both the sides of the tigers. Sometimes there are obstacles or some malfunctioning, due to which they
get only one side of the tiger. Suppose they get (pairs of) images where they have both sides of k
distinct tigers. And additionally, they have some images of the left stripes of m distinct tigers and
some images of the right stripes of n distinct tigers. When there is no way to figure out which of
the left images and right images belong to the same tiger, they take a conservative estimate, which is
k + max{m, n}.
At some point, allegedly to show a higher count, they changed the protocol and counted the above
scenario as k + m + n distinct tigers. Clearly, the actual count is somewhere between k + max{m, n}
and k + m + n.
Let’s say there are some experts who can identify which pairs of left and right images are definitely
from distinct tigers. For example, for m = 3, n = 3, suppose they say that the pairs (`1 , r2 ), (`1 , r3 ),
(`2 , r2 ), (`2 , r3 ) are definitely from distinct tigers. With this additional information, the conservative
estimate will be 4 distinct tigers. How will you find this conservative estimate for any given list of
pairs from experts.
2
16. Suppose there are n thermal power plants and m coal mines in the country. The coal is transported to
power plants via the train network. Each segment (edge) of the train network has a certain transport
capacity per day. Each coal mine has a maximum limit on the amount of coal that can be produced
in one day. Each thermal power plant has a certain demand for coal per day. Given all this, we want
to decide the coal transportation plan. That is, from which coal mine, how much coal should be sent
to which power plant, using which rail route, so that we meet all the demands.