T-join

A graft is a pair (G,T) where G=(V,E) is an undirected graph and $$T \subseteq V$$ is a node set of even cardinality. A T-join of the graft (G,T) is a subset $$F \subseteq E$$ of edges with the property that $$d_F(v)$$ is odd precisely if $$v \in T$$ .

A subset X of nodes is T-odd if $$|X \cap T|$$ is odd. The cut $$\delta(X)$$ is called a T-cut if X is T-odd (clearly, X is T-odd if and only if V-X is T-odd). It is easy to see that the intersection of a T-join and a cut $$\delta(X)$$ is odd if and only if X is T-odd.

In bipartite graphs, the minimum cardinality of a T-join equals the maximum number of edge-disjoint T-cuts by a theorem of Seymour . This is not true in general graphs, but the T-join polyhedron is always described by

$$\{x \in {\mathbb R}^E: x \geq 0, \sum_{e \in C}x_e \geq 1 \text{ for every T-cut C}\}$$

by the results of Edmonds and Johnson . They also showed that a minimum weight T-join can be found using the minimum weight perfect matching algorithm, for arbitrary weights. Padberg and Rao proved that a minimum weight T-cut can be found using the Gomory-Hu tree of the graph.

For a survey, see Frank .