T-join
A graft is a pair (G,T) where G=(V,E) is an undirected graph and [math]T \subseteq V[/math] is a node set of even cardinality. A T-join of the graft (G,T) is a subset [math]F \subseteq E[/math] of edges with the property that [math]d_F(v)[/math] is odd precisely if [math]v \in T[/math].
A subset X of nodes is T-odd if [math]|X \cap T|[/math] is odd. The cut [math]\delta(X)[/math] 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 [math]\delta(X)[/math] 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 [1]. This is not true in general graphs, but the T-join polyhedron is always described by
[math]\{x \in {\mathbb R}^E: x \geq 0, \sum_{e \in C}x_e \geq 1 \text{ for every T-cut C}\}[/math]
by the results of Edmonds and Johnson [2]. 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 [3] proved that a minimum weight T-cut can be found using the Gomory-Hu tree of the graph.
For a survey, see Frank [4].
References
- ↑ P.D. Seymour, On odd cuts and plane multicommodity Flows, DOI link.
- ↑ J. Edmonds, E.L. Johnson, Matching, Euler tours and the Chinese postman problem, DOI link.
- ↑ M.W. Padberg, M.R. Rao, Odd minimum cut-sets and b-matchings, DOI link.
- ↑ A. Frank, A survey on T-joins, T-cuts, and conservative weightings, CiteSeer link, author link.
