PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
Consider the graph whose nodes correspond to posters where two posters are connected by an edge if they share a common point. The problem is then to find the largest independent set in this graph. Here’s the idea.
The graph is actually a “comparability graph”. That is, the edges can be directed so that if u->v and v->w are directed edges, then so is u->w. To see this, for two posters u,v that overlap, we direct the edge from the skinnier to the larger poster. If one remembers the property that no poster contains the corner of another, a moments thought (or a quick doodle on a scrap of paper) reveals that u->v and v->w implies u->w.
Comparability graphs enjoy the nice property that the maximum independent set size is equal to the minimum number of cliques whose union covers all nodes (this is Dilworth’s theorem). Furthermore, cliques in comparability graphs correspond to directed paths and vice-versa (once the edges are oriented as implied above). So, we have reduced the problem to computing the minimum number of paths required in a directed graph to cover all nodes. This is solved via bipartite matching.
Build a bipartite graph B with a copy of the nodes of the original graph on both sides. Call the original directed graph G and say it has n nodes. Add an edge from a node u on the “left” to a node v on the “right” in B if u->v is a directed edge in G. Then, the size of a minimum path cover in G (and, hence, a maximum independent set) is exactly n minus the maximum matching size in B.
To see this, say we have covered the nodes of G with k paths. In total, these paths use exactly n-k edges in G. For each u->v edge used in the path decomposition of G, we select the corresponding u-v edge in B (with u on the “left” and v on the “right”). This is a valid matching in that uses n-k edges.
Conversely, consider a matching of size m in B. We can construct exactly n-m paths in G whose union covers all nodes. Also note that exactly n-m nodes on the “left” and n-m nodes on the “right” of B are not matched. Pick any node v _ 1 on the “right” of B that is not matched. Now, let v _ 2 be the node on the “right” that is matched to the copy of v _ 1 on the “left”. Let v _ 3 be the node on the “right” that is matched to the copy of v _ 2 on the “left”. Continuing in this way until we reach a node v _ b whose “left” counterpart is not matched, we construct a path v _ 1, v _ 2, …, v _ b. Furthermore, we have used exactly one unmatched node on the “left” of B (corresponding to v _ b) and one unmatched node on the “right” (corresponding to v _ 1) and there are now n-m-1 unmatched nodes on the “left” and the “right” of B. Iterate this process to obtain n-m paths in G which, together, cover all nodes.
Building the graph takes O(n^2) time (each pair of posters need to be checked for intersection). Assuming the worst case of O(n^2) edges, the matching phase takes O(n^3) with the standard augmenting paths algorithm. This can be improved to O(n^2.5) with Dinic’s matching algorithm but is not necessary for the time restrictions placed on the problem.
That might seem like quite a few steps to make, but I think it is actually a little easier than the Generalized Spanning Tree problem used in the May competition (easier, but still hard). The main idea is to see the intersection graph as a comparability graph.