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).

## Error

Your reply will be screened

Your IP address will be recorded

11011110: ←MathJax in Wikipedia11011110: →17-40 @ LACMA