5 - Cactus Representations

Summary

In this chapter, we investigate structures and algorithms of cactus representations, which were introduced in Section 1.5.4 to represent all minimum cuts in an edgeweighted graph G. Throughout this chapter, we assume that λ(G) > 0 for a given graph G, which implies that G is connected. Let C(G) denote the set of all minimum cuts in G. In Section 5.1, we define a canonical form of cactus representations. In Section 5.2, we show that a subset of C(G) that consists of minimum cuts separating two given vertices, s and t, can be represented by a simple cactus structure. In Section 5.3, we design an O(mn + n² log n) time algorithm for constructing a cactus representation R of C(G).

Canonical Forms of Cactus Representations

In this section, we discuss cactus representations for a subset of minimum cuts, and we prove the existence of two canonical forms, which we call the cycle-type and junction-type normal cactus representations. Such a canonical representation is useful in designing an efficient algorithm that constructs a cactus representation for all the minimum cuts of a given graph [244]. It also helps to efficiently test whether two given graphs have the same “structure” with respect to their minimum cuts, which is based on a planar isomorphism algorithm due to Hopcroft and Tarjan [126].

A cactus representation for a given subset C ⊆ C(G), if one exists, may not be unique unless we impose further structural restrictions.