by András A. Benczúr
Siam Journal on Computing 24(3):505-510 (1995)
Citations from the paper (the infamous incorrect Schnorr paper) as in the Hypertext Bibliography Project (apparently not maintained since 1998)
We show that there is no cut-tree for various connectivity concepts, hence pointing out to errors in the papers of Schnorr and Gusfield and Naor. Gomory and Hu constructed a cut-tree for undirected graphs which compactly represents a minimum cut for each pair of vertices. This has a straightforward generalization to directed Eulerian graphs, cf. Gupta. To arbitrary directed graphs a generalization was given by Schnorr. There is a well-known transformation of vetex connectivity to directed edge connectivity; directed edge cuts correspond to vertex cuts in some weak sense. The result of Schnorr was later applied by Gusfield and Naor for such a cut-tree construction. In this paper counterexamples are described to show that for directed graphs there is no cut-tree and therefore the cut-tree results of Schnorr and Gusfield and Naor are incorrect. Our final example shows that, without weakening the notion of vertex connectivity, it is impossible to construct vertex cut-trees for undirected graphs in general.
Schnorr, C.P.
Bottlenecks and edge connectivity in unsymmetrical networks
SIAM. J. Comput. 8 (1979) 265--274.
Gusfield, D. and D. Naor
Efficient Algorithms for Generalized Cut-Trees
Networks 21 (1991) 505--520.