In the theory of maximum flows, a "mimicking network" for a given flow network with a given set of terminals is a different network having the same set of terminals and the same behavior with respect to all possible flow demands. Mimicking networks can be seen as a type of separator based sparsification for flow; they were introduced by Hagerup, Katajainen, Nishimura, and Ragde in SODA 1995, who showed that flow problems in graphs of bounded treewidth could be solved in linear time by repeatedly replacing parts of the graph by smaller mimicking networks. They also showed that any given set of terminals always has a mimicking network whose size is only double exponential in the number of terminals.

Later, Chaudhuri, Subrahmanyam, Wagner, and Zaroliagis (Algorithmica 2000) found small mimicking networks for graphs with up to five terminals, and showed that bounded treewidth graphs have mimicking networks that are much smaller than the double exponential bound for general graphs. More recently Erin Chambers and I used mimicking networks to find flows on minor-closed families of graphs in which at least one of the forbidden minors can be drawn with only one crossing.

Now there are two new papers on the arXiv on the same subject: On Mimicking Networks Representing Minimum Terminal Cuts (arXiv:1207.6371) by Arindam Khan, Prasad Raghavendra, Prasad Tetali, and László A. Végh, and Mimicking Networks and Succinct Representations of Terminal Cuts (arXiv:1207.6246), by Robert Krauthgamer and Inbal Rika. Both papers show that mimicking networks may sometimes need to be of exponential size, narrowing the gap to the doubly-exponential upper bound. The basic idea is that every minimum cut that separates one set of terminals from another must have the same cut value in the mimicking network that it does in the original graph, so if one can find graphs in which these cuts have an exponential number of degrees of freedom then their mimicking networks need to be exponentially large. But this approach won't work to produce superexponential lower bounds, so at this point it looks like the upper bound is the place to look for the next improvement.

Khan et al make a start on that end of the problem, too: expanding on a brief remark in my paper with Erin, they show that the size of a mimicking network can be upper bounded by a Dedekind number (logarithmic in the square of the number of terminals, much better than double exponential, but still not single exponential). Krauthgamer and Rika continue in a different direction: they show that planar graphs have mimicking networks of single-exponential size (formed as minors of the original graph, and therefore planar themselves).