The aim of this paper is to further develop the theory of packing trees in a graph. We first prove the classic result of Nash-Williams (Nash-Williams, 1961) and Tutte (Tutte, 1961) on packing spanning trees by adapting Lovász’ proof (Lovász, 1976) of the seminal result of Edmonds (Edmonds, 1973) on packing spanning arborescences in a digraph. Our main result on graphs extends the theorem of Katoh and Tanigawa (Katoh and Tanigawa, 2013) on matroid-based packing of rooted trees by characterizing the existence of such a packing satisfying the following further conditions: for every vertex v , there are given a lower bound f ( v ) and an upper bound g ( v ) on the number of trees rooted at v and there are given a lower bound α and an upper bound β on the total number of roots. We also answer the hypergraphic version of the problem. Furthermore, we are able to solve the augmentation version of the latter problem, where the goal is to add a minimum number of edges to have such a packing. The methods developed in this paper to solve these problems may have other applications in the future.

Given a connected undirected graph $\overline{G}$ on $n$ vertices and nonnegative edge costs $c$, the $\ensuremath{{2ECM}}$ problem is that of finding a 2-edge connected spanning multisubgraph of $\overline{G}$ of minimum cost. The natural linear program (LP) for $\ensuremath{{2ECM}}$, which coincides with the subtour LP for the traveling salesman problem on the metric closure of $\overline{G}$, gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution $x$, Carr and Ravi (1998) showed that the integrality gap is at most $\frac43$: they show that the vector $\frac43 x$ dominates a convex combination of incidence vectors of 2-edge connected spanning multisubgraphs of $\overline{G}$. We present a simpler proof of the result due to Carr and Ravi by applying an extension of Lovász's splitting-off theorem. Our proof naturally leads to a $\frac43$-approximation algorithm for half-integral instances. Given a half-integral solution $x$ to the LP for $\ensuremath{{2ECM}}$, we give an $O(n^2)$-time algorithm to obtain a 2-edge connected spanning multisubgraph of $\overline{G}$ with cost at most $\frac43 c^T x$. We also consider a related problem of finding a cheap 2-edge connected spanning subgraph of a 3-regular, 3-edge connected graph $G = (V,E)$ with arbitrary edge costs $c$. We give a polynomial-time Las Vegas algorithm that finds a random 2-edge connected spanning subgraph $H$ of $G$ whose expected cost, $\mathbb{E}\left[{c(H)}\right]$, is at most $\frac45 c(E)$.

It is well-known that every Eulerian orientation of an Eulerian 2k-edge-connected undirected graph is k-arc-connected. A long-standing goal in the area has been to obtain analogous results for vertex-connectivity. Levit, Chandran and Cheriyan recently proved in Levit et al. (2018) that every Eulerian orientation of a hypercube of dimension 2k is k-vertex-connected. Here we provide an elementary proof for this result. We also show other families of 2k-regular graphs for which every Eulerian orientation is k-vertex-connected, namely the even regular complete bipartite graphs, the incidence graphs of projective planes of odd order, the line graphs of regular complete bipartite graphs and the line graphs of complete graphs. Furthermore, we provide a simple graph counterexample for a conjecture of Frank attempting to characterize graphs admitting at least one k-vertex-connected orientation.

Given a connected undirected graph $\bar{G}$ on $n$ vertices, and non-negative edge costs $c$, the 2ECM problem is that of finding a $2$-edge~connected spanning multisubgraph of $\bar{G}$ of minimum cost. The natural linear program (LP) for 2ECM, which coincides with the subtour LP for the Traveling Salesman Problem on the metric closure of $\bar{G}$, gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution $x$, Carr and Ravi (1998) showed that the integrality gap is at most $\frac43$: they show that the vector $\frac43 x$ dominates a convex combination of incidence vectors of $2$-edge connected spanning multisubgraphs of $\bar{G}$. We present a simpler proof of the result due to Carr and Ravi by applying an extension of Lov\'{a}sz's splitting-off theorem. Our proof naturally leads to a $\frac43$-approximation algorithm for half-integral instances. Given a half-integral solution $x$ to the LP for 2ECM, we give an $O(n^2)$-time algorithm to obtain a $2$-edge connected spanning multisubgraph of $\bar{G}$ whose cost is at most $\frac43 c^T x$.

We provide the directed counterpart of a slight extension of Katoh and Tanigawa's result [SIAM J. Discrete Math., 27 (2013), pp. 155--185] on rooted-tree decompositions with matroid constraints. Our result characterizes digraphs having a packing of arborescences with matroid constraints. It is a proper extension of Edmonds' result [Combinatorial Algorithms, Algorithmics Press, New York, 1973] on packing of spanning arborescences and implies---using a general orientation result of Frank [J. Combin. Theory Ser. B, 28 (1980), pp. 251--261]---the above result of Katoh and Tanigawa. We also give a complete description of the convex hull of the incidence vectors of the matroid-based packings of arborescences and prove that the minimum cost version of the problem can be solved in polynomial time.

Given a symmetric crossing supermodular set function p on V and a partition of V, we solve the problem of finding a graph with ground set V having edges only between the classes of such that for every subset X of V the cut of the graph defined by X contains at least p(X) edges. The objective is to minimize the number of edges of the graph. This problem is a common generalization of the global edge-connectivity augmentation of a graph with partition constraints, which was solved by Bang-Jensen, Gabow, Jordán and Szigeti [1] and the problem of covering a symmetric crossing supermodular set function solved by Benczúr and Frank [3]. Our problem can be considered as an abstract form of the problem of global edge-connectivity augmentation of a hypergraph by a multipartite graph, which was earlier solved by the authors [5].

Let G=(V+s,E) be a graph with a designated vertex s of degree d(s), and let f(s)=(d 1 ,d 2 ,. . .,d p ) be a partition of d(s) into p positive integers. An f(s)-detachment of G is a graph G' obtained by "splitting" s into p vertices, called the pieces of s, such that the degrees of the pieces of s in G' are given by f(s). Thus every edge $sw\in E$ corresponds to an edge of G' connecting some piece of s to w. We give necessary and sufficient conditions for the existence of an f(s)-detachment of G in which the local edge-connectivities between pairs of vertices in V satisfy prespecified lower bounds. Our result is a common generalization of a theorem of Mader on edge splittings preserving local edge-connectivities and a result of Fleiner on f(s)-detachments satisfying uniform lower bounds. It implies a conjecture of Fleiner on f(s)-detachments preserving local edge-connectivities. By using our characterization we extend a theorem of Frank on local edge-connectivity augmentation of graphs to the case when stars of given degrees are added, and we also solve the local edge-connectivity augmentation problem for 3-uniform hypergraphs.

We give a $\frac{17}{12}$-approximation algorithm for the following NP-hard problem: Given a simple undirected graph, find a 2-edge connected spanning subgraph that has the minimum number of edges. The best previous approximation guarantee was $\frac{3}{2}$. If the well-known $\frac{4}{3}$ conjecture for the metric traveling salesman problem holds, then the optimal value (minimum number of edges) is at most $\frac{4}{3}$ times the optimal value of a linear programming relaxation. Thus our main result gets halfway to this target.

In the well-solved edge-connectivity augmentation problem we must find a minimum cardinality set F of edges to add to a given undirected graph to make it k-edge-connected. This paper solves the generalization where every edge of F must go between two different sets of a given partition of the vertex set. A special case of this partition-constrained problem, previously unsolved, is increasing the edge-connectivity of a bipartite graph to k while preserving bipartiteness. Based on this special case we present an application of our results in statics. Our solution to the general partition-constrained problem gives a min-max formula for |F| which includes as a special case the original min-max formula of Cai and Sun [Networks, 19 (1989), pp. 151--172] for the problem without partition constraints. When k is even the min-max formula for the partition-constrained problem is a natural generalization of the unconstrained version. However, this generalization fails when k is odd. We show that at most one more edge is needed when k is odd and we characterize the graphs that require such an extra edge. We give a strongly polynomial algorithm that solves our problem in time O(n(m + nlog n)log n). Here n and m denote the number of vertices and distinct edges of the given graph, respectively. This bound is identical to the best-known time bound for the problem without partition constraints. Our algorithm is based on the splitting off technique of Lovász, like several known efficient algorithms for the unconstrained problem. However, unlike previous splitting algorithms, when k is odd our algorithm must handle obstacles that prevent all edges from being split off. Our algorithm is of interest even when specialized to the unconstrained problem, because it produces an asymptotically optimum number of distinct splits.