# Help with a special case for Hungarian algorithm

I am working on a problem and it appears to be a special case of Hungarian algorithm.

• In Hungarian algorithm for assignment problem, there are n people and n jobs.
• Each person can do any of n jobs and incur a corresponding cost C. The goal is to minimize the cost by assigning n people to n jobs.
• My special case that for each person, he can be assigned only 2 specific jobs out of n jobs. Given this condition, is there any optimization possible for Hungarian algorithm that will reduce its complexity from O(n^3) to lower.

• In that case, your graph is a collection of even-sized cycles. For each such cycle, there are two possible perfect matchings. By independence of the disconnected components, the cheaper of the two will be the one in the optimal matching. Thus, you can solve this problem in linear time by picking a vertex $v$, following it to a neighbor, and keep following to its next neighbor until you get back to $v$, closing the cycle. Then test the two possible matchings in this cycle, pick the cheapest one, and recurse on the rest of the graph. – Yonatan N Apr 1 '14 at 1:50