A fusion week

The Jun 24 - Jun 30 week was quite calm, therefore we can divert our full attention to the problem from the previous summary: you are given a graph with n<=15 vertices and m<=200 edges. For each k between n-1 and m, compute the number of spanning sets of edges of size k (ones that connect all n vertices together). The numbers need to be computed modulo 10⁹+7.

If we didn't care about the number of edges, and just wanted to count all spanning sets, the following standard approach would be used: let's count all sets (there are 2^m of them) and subtract the sets which are not spanning. Each set that is not spanning has a uniquely determined connected component containing the vertex 0. So for each possible non-full subset of vertices containing the vertex 0 we need to subtract the number of subsets of edges with both ends within that component that are spanning within that components times two to the power of number of edges with both ends outside that component. Thus we can determine the number of spanning subsets for each subset of vertices containing the vertex 0 using dynamic programming with a running time of O(3ⁿ) if we precompute the number of edges within that subset for each subset of vertices, and the powers of two.

Adding a parameter for the number of edges makes this dynamic programming run in O(3ⁿ*m²): for each of O(3ⁿ) (set, subset) pairs we need to iterate over the number of edges in the subset, and the number of edges being added outside the subset, and our dynamic programming transition looks like

dp[set,a+b]-=dp[subset,a]*comb(outside_edges(set,subset),b)

Where comb(outside_edges(...),b) is the combination number that counts the ways to pick b edges to be added in the disconnected part. O(3ⁿ*m²) was too slow in this problem, but how to make this solution faster?

In many problems (for example in the TopCoder problem from three summaries ago), the key idea is about collapsing a subproblem as a separate dynamic programming to reduce the number of states or the processing time for each transition in the main dynamic programming. In this problem, we're going to do the opposite: the combination number is computed by its own dynamic programming, so we're going to unwrap that dynamic programming and fuse it with the main one!

Our state will now be the set of vertices, the number of edges we got so far, and the number of outside edges, for each of which we need to take a decision whether we add it to our edge counter or not.

We can then do (I'm describing a "forward" dynamic programming everywhere in this post)

sub[set,a,outside_edges(set,subset)] += dp[subset,a]

for all subsets of set and all values of a, then

sub[set,a,o-1] += sub[set,a,o]
sub[set,a+1,o-1] += sub[set,a,o]

to reconstruct the combination number by trying two possibilities on whether to include the next outside edge, and finally

dp[set,a] -= sub[set,a,0]

to subtract the disconnected graphs once we have made all decisions on the outside edges.

The first statement runs in O(3ⁿ*m), the second block of statements runs in O(2ⁿ*m²), and the last statement in O(2ⁿ*m), so the running time now is O(3ⁿ*m+2ⁿ*m²) which is fast enough.

By fusing the combination number dynamic programming into the main one we could no longer reuse its results between different transitions in the main part, so our complexity could become O(3ⁿ*m³) after doing this. But we achieved a different type of reuse: we can now do the part that adds the outside edges for all values of subset of a given set, and for all values of a for a given set, at the same time instead of doing it separately for each (subset, a) combination by iterating over b as we did before.

This dynamic programming fusion looks to be a quite general technique, but I couldn't remember many problems where it appeared, apart from one large cluster of problems: dynamic programming on "broken profile" can be viewed as an application of such fusion to dynamic programming on "normal profile" and the sub-dynamic programming between two profiles. Do you have more examples?

Thanks for reading, and check back for more!