Minimax relations for T-join packing problems

In this paper we present structural and algorithmic results for problems involving the packing of T-joins. We explore minimax relations that relate the size of a packing of T-joins with the size of a minimum T-cut in a graph. We present a new conjecture stating that if all T-cuts have the same parity then the maximum size of a family of T-joins that uses each edge at most twice equals the double of the size of a minimum T-cut. We show that this conjecture is equivalent to a famous conjecture for perfect matchings. We also prove a theorem for the case |T|/spl les/8 and describe a polynomial time algorithm for the maximization problem.