BIPARTRE - Explanation?

general
,
1

Can somebody explain how to solve BIPARTRE problem in detail.
Problem Link

2

the title is misleading… this question is not an editorial, please change so that it is more appropriate

3

PROBLEM

Given an implicit bipartite graph, given by a tree with N nodes and M lists, compute the size of the maximal bipartite matching from these M lists to the N nodes.

PREREQUISITES

Maxflow

QUICK EXPLANATION

Create a maxflow graph such that:

  • Every list L=\{l_1, l_2, ..., l_m\} is a node with an edge to l_i with capacity 1
  • Connect the source node to every list with capacity 1
  • A parent in the tree has an edge to a child with capacity \infty
  • Connect every node in the tree to the sink with capacity 1

Perform the maxflow with Dinic’s algorithm or similar, and print the answer.

EXPLANATION

This is a graph modeling problem. A list L and a node j can be matched if there exists an ancestor of j that is in L.

Slow solution

At first glance, it is quite possible to create a bipartite graph with all nodes on both sides. Just straightforwardly create the bipartite graph as per the definition. But this is in fact too slow since there can be at most 5000^2 \approx 25,000,000 edges (consider all lists pointing to the root node, will create a complete bipartite graph). It is well-known that unweighted maximal bipartite matching can be solved with Hopcroft-Karp or Dinic’s algorithm in O(E \sqrt{V}) time, but with such a large number of edges this is not feasible with V=10000 and E=25000000. A better approach is needed.

Better graph model

We will need a better graph model to solve the problem faster. First, observe how having l_i \in L implies that all descendants of l_i can be matched with L. This means that we can implicitly create the graph by exploiting the tree structure. Instead of having multiple edges towards all the descendants, we can instead have a single edge to l_i, and have directed edges from l_i downwards to the children, and deeper into the tree. To allow multiple usage, we set the capacity of such edges to be \infty (consider the black edges in the figure below). Create necessary edges from source and sink nodes, then perform regular maxflow on the implicit graph, and we get the maximal matching.

alt text

COMPLEXITY

Solving with Dinic’s algorithm, the complexity would be O(min\{V^2 E, Ef\}). In this case, E < 20000 (10000 red edges, 4999 downward edges, 5000 from source, 5000 to sink), and the flow cost is up to 5000. Taking the minimum, this results to Ef < 20000*5000 \approx 10^8 operations, which roughly runs in 1 second. The same O(Ef) complexity can be achieved with Edmonds-Karp and Ford-Fulkerson algorithm; either should pass as a solution, but one must be careful of the constant factors.

SOLUTION LINKS

Here’s my solution using Dinic’s.

5 Likes
4

You can find the official editorial here.

1 Like
5

I chose this title so that all solutions related to this problem can be here. But feel free to edit the title appropriately as I’ve marked this as community wiki now.

6

Got it, thanks.

7

Where did you got that pic from??? Wow @hikarico is back, lively as usual :smiley:

1 Like
8

Thanks a lot for this awesome explanation…thumbs up