More Reductions to Flow Consider the problem of forming a un

More Reductions to Flow

Consider the problem of forming a univeristy wide faculty committee that has one representative from each department. Suppose the university has n departments, and m faculty. Each faculty member may have appointments at multiple departments, and thus he/she may be a represetative for any of those departments. However, two departments are not allowed to pick the same faculty member as their representative.

Note that forming such a committee easily reduces to a max flow problem. Now, suppose we have the additional constraint that the committee has equal representation from all ranks of professors (assistant, associate, full). Give a polynomial time algorithm that incorporates this constraint and comes up with a committee, or concludes that it is impossible.

Solution

m departments and each from department should represent in committee, size of committee is n.

To take one person from each dept and considering criteria of committee size is n and all items in that are unique.

For that we use 3 for loops

One m loop

In side n loop

Inside it m loop

The time complexity is

O(m²n+mn)

Because out loop * first inner * second inner + comparision for one person only for one dept