Abstract Let $$D\,=\,(V,A)$$ D = ( V , A ) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper face F of P not contained in $$\{x:x_a=i\}$$ { x : x a = i } for any $$a\in A,i\in \{0,1\}$$ a ∈ A , i ∈ { 0 , 1 } . We prove under a mild necessary condition that $$F\cap \{0,1\}^A$$ F ∩ { 0 , 1 } A contains an integral basis B, i.e., B is linearly independent, and any integral vector in the linear hull of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form a Hilbert basis. In proving the result, we develop a theory similar to Matching Theory for degree-constrained dijoins in bipartite digraphs. Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say $$\tau $$ τ , is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any prime number $$p\,\ge \,2$$ p ≥ 2 , a p-adic packing of dijoins of value $$\tau $$ τ and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by $$F\cap \{0,1\}^A$$ F ∩ { 0 , 1 } A , where F is the face of P satisfying $$x(\delta ^+(U))=1$$ x ( δ + ( U ) ) = 1 for every minimum dicut $$\delta ^+(U)$$ δ + ( U ) .

Abstract. Let [Formula: see text] be a digraph. A dicut is a cut [Formula: see text] for some nonempty proper vertex subset [Formula: see text] such that [Formula: see text], a dijoin is an arc subset that intersects every dicut at least once, and more generally a [Formula: see text]- dijoin is an arc subset that intersects every dicut at least [Formula: see text] times. Our first result is that [Formula: see text] can be partitioned into a dijoin and a [Formula: see text]-dijoin where [Formula: see text] denotes the smallest size of a dicut. Woodall conjectured the stronger statement that [Formula: see text] can be partitioned into [Formula: see text] dijoins. Let [Formula: see text], and suppose every dicut has weight at least [Formula: see text], for some integer [Formula: see text]. Let [Formula: see text], where each [Formula: see text] is the integer in [Formula: see text] equal to [Formula: see text] mod [Formula: see text]. We prove the following results: If [Formula: see text], then there is an equitable [Formula: see text]-weighted packing of dijoins of size [Formula: see text]. If [Formula: see text], then there is a [Formula: see text]-weighted packing of dijoins of size [Formula: see text]. If [Formula: see text], [Formula: see text], and [Formula: see text], then [Formula: see text] can be partitioned into three dijoins. Each result is best possible: (i) does not hold for [Formula: see text] even if [Formula: see text], (ii) does not hold for [Formula: see text], and (iii) does not hold for general [Formula: see text].

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.

Let $G=(V,E)$ be a graph, and $T\subseteq V$ a nonempty subset of even cardinality. The famous theorem of Edmonds and Johnson on the $T$-join polyhedron implies that the minimum cardinality of a $T$-cut is equal to the maximum value of a fractional packing of $T$-joins. In this paper, we prove that the fractions assigned may be picked as dyadic rationals, i.e., of the form $\frac{a}{2^k}$ for some integers $a,k\geq 0$.

A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that every 4-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it in the binary case. Two key ingredients for our proof are Jaeger’s 8-flow theorem for graphs, and Seymour’s characterization of the binary matroids with the sums of circuits property. As further evidence for our conjecture, we also note that it follows from an unpublished conjecture of Seymour from 1975.

For an integer $n\geq 3$, the clutter $\Delta_n:=\big\{\{1,2\},\{1,3\},\ldots,\{1,n\},\{2,3,\ldots,n\}\big\}$ is called a delta of dimension $n$, whose members are the lines of a degenerate projective plane. In his seminal paper on nonideal clutters, Lehman revealed the role of the deltas as a distinct class of minimally nonideal clutters [ The width length inequality and degenerate projective planes, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 1, AMS, Providence, RI, 1990, pp. 101--105]. A clutter is delta free if it has no delta minor. Binary clutters, ideal clutters, and clutters with the packing property are examples of delta free clutters. In this paper, we introduce and study basic geometric notions defined on clutters, including entanglement between clutters, a notion that is intimately linked with set covering polyhedra having a convex union. We will then investigate the surprising geometric attributes of delta minors and delta free clutters.

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.