Abstract. A rational with denominator a power of two is said to be dyadic. We prove that for every integer weighted directed graph, there exists a maximum fractional packing of directed joins with dyadic values. This settles a long-standing conjecture of Paul Seymour on ideal clutters and dyadic dual solutions for the case of clutters of dijoins.

A vector is dyadic if each of its entries is a dyadic rational number, i.e., an integer multiple of $\frac{1}{2^k}$ for some nonnegative integer $k$. We prove that every clean clutter with a covering number of at least two has a dyadic fractional packing of value two. This result is best possible, for there exist clean clutters with a covering number of three and no dyadic fractional packing of value three. Examples of clean clutters include ideal clutters, binary clutters, and clutters without an intersecting minor. Our proof is constructive and leads naturally to an (albeit exponential) algorithm. We improve the running time to quasi-polynomial in the rank of the input and to polynomial in the binary case.

In the directed Steiner tree problem, we are given a digraph, nonnegative arc weights, a subset of vertices called terminals, and a special terminal called the root. The goal is to compute a minimum weight directed tree that connects each terminal to the root. We study the classical directed cut linear programming (LP) formulation which has a variable for every arc, and a constraint for every cut that separates a terminal from the root. For what instances is the directed cut LP integral? In this paper we demonstrate how the celebrated theorem of Lehman [Math. Program., 17 (1979), pp. 403--417] on minimally nonideal clutters provides a framework for deriving answers to this question. Specifically, we show that this framework yields short proofs of the optimum arborescences theorem and the integrality result for series-parallel digraphs. Furthermore, we use this framework to show that the directed cut linear program is integral for digraphs that are acyclic and have at most two nonterminal vertices.

Consider a binary matroid $M$ given by its matrix representation. We show that if $M$ is a lift of a graphic or cographic matroid, then in polynomial time (in the size of $M$ and encoding length of the weights) we can either solve the single commodity-flow problem for $M$ or find an obstruction for which the max-flow min-cut relation does not hold. The key tool is an algorithmic version of Lehman's theorem for set covering polyhedra. This tool relies on the ellipsoid method.

We show how pairs of signed graphs with the same even cycles relate to pairs of grafts with the same even cuts. These results are proved in the more general context of signed binary matroids.

A binary clutter is the family of odd circuits of a binary matroid, that is, the family of circuits that intersect with odd cardinality a fixed given subset of elements. Let A denote the 0,1 matrix whose rows are the characteristic vectors of the odd circuits. A binary clutter is ideal if the polyhedron $\{ x \geq {\bf 0}: \; Ax \geq {\bf 1} \}$ is integral. Examples of ideal binary clutters are st-paths, st-cuts, T-joins or T-cuts in graphs, and odd circuits in weakly bipartite graphs. In 1977, Seymour [J. Combin. Theory Ser. B, 22 (1977), pp. 289--295] conjectured that a binary clutter is ideal if and only if it does not contain ${\cal{L}}_{F_7}$, ${\cal{O}}_{K_5}$, or $b({\cal{O}}_{K_5})$ as a minor. In this paper, we show that a binary clutter is ideal if it does not contain five specified minors, namely the three above minors plus two others. This generalizes Guenin's characterization of weakly bipartite graphs [J. Combin. Theory Ser., 83 (2001), pp. 112--168], as well as the theorem of Edmonds and Johnson [ Math. Programming, 5 (1973), pp. 88--124] on T-joins and T-cuts.

We propose two algorithms for constructing and training compact feedforward networks of linear threshold units. The SHIFT procedure constructs networks with a single hidden layer while the PTI constructs multilayered networks. The resulting networks are guaranteed to perform any given task with binary or real-valued inputs. The various experimental results reported for tasks with binary and real-valued inputs indicate that our methods compare favorably with alternative procedures deriving from similar strategies, both in terms of size of the resulting networks and of their generalization properties.