180 Homework 3
Problem 1 (50 pts). Let G be an arbitrary graph with n nodes and each node has a weight. A set A of
its nodes is independent if no two of them are connected by an edge. The problem MIS of finding an
independent set of nodes with the maximal total weight is considered intractable although solvable in
the general case. That is why special cases of graphs are considered.
Assume that G is cyclic and find an efficient algorithm for solving MIS. An example of a cyclic graph
with weights is given in Figure 1.
10
6
3
8
5 3
Figure 1
Problem 2 (50 pts). Decide whether the following statement is true or false.
If it is true, give a short explanation.
If it is false, give a counterexample.
Let G be an arbitrary flow network with the source s, the sink t and all capacities c(e) are natural
numbers. If f is a maximal s-t flow in G, then there are not more than three edges e1 , e2 and e3 such
that f(ei) < c(ei) (i = 1,2,3).
