We consider multicommodity flows in undirected graphs. An instance consists of an edgecapacitated graph \(G\), called the supply graph, and a set of source-sink pairs with associated demands (commodities), defining a demand graph \(H\). An instance is said to be feasible if there exists a flow that routes all demands while respecting the edge capacities. In many applications, it is further required that the entire demand of each commodity be routed along a single path; this is known as the unsplittable multicommodity flow problem. We study conditions under which the existence of a feasible (splittable) flow implies the existence of an unsplittable flow that does not significantly violate edge capacities.

We consider the $\boldsymbol{k}$-edge connected spanning subgraph (k-ECSS) problem, where we are given an undirected graph $G=(V, E)$ with nonnegative edge costs $\left\{c_{e}\right\}_{e \in E}$, and the goal is to find a minimum-cost subgraph H of G that is k edge connected, i.e., there exist at least k edge-disjoint paths between every pair of vertices in H. For even k, we present a polynomial time algorithm that computes a ($k-2$)-edge connected subgraph of cost at most that of the optimal k-edge connected subgraph of G; for odd k, we obtain a $(k-3)$ edge connected subgraph of cost at most the optimum. In fact, the cost of our solution does not exceed the optimal value, $\mathbf{L P}_{\boldsymbol{k} \text {-ECSSLP }}^{\boldsymbol{*}}$ of the natural LP-relaxation for $\boldsymbol{k}$-ECSS. Since k-ECSS is $A P X$-hard for all values of $k \geq 2$, our results are nearly optimal. They also significantly improve upon the recent work of Hershkowitz, Klein, and Zenklusen [1], both in terms of solution quality and the simplicity of algorithm and its analysis. Interestingly, our techniques also yield an alternate guarantee, where we obtain a($k-1$)-edge connected subgraph of cost at most $1.5 \cdot \mathrm{LP}_{\boldsymbol{k}-\mathrm{ECSSLP}}^{*}$; with unit edge costs, the cost guarantee improves to $\left(1+\frac{4}{3 k}\right) \cdot$ LP $_{\boldsymbol{k} \text {-ECSSLP }}^{\boldsymbol{*}}$, which improves upon the state-of-the-art approximation guarantee for unit edge costs [2], albeit with a unit loss in edge connectivity. Our k-ECSS-result also yields results for the k-edge connected spanning multigraph (k-ECSM) problem, where multiple copies of an edge can be selected. For $\boldsymbol{k}$-ECSM, we obtain a $\left(1+\frac{2}{k}\right)$-approximation algorithm for even k, and $\mathbf{a}\left(1+\frac{3}{k}\right)$ approximation algorithm for odd $\boldsymbol{k}$. Finally, our techniques extend to the degree-bounded versions of k-ECSS and k-ECSM, wherein we also impose degree lower- and upper- bounds on the nodes. Our results for k-ECSS and k-ECSM extend to yield the same cost and connectivity guarantees for these degree-bounded versions with an additive violation of (roughly) 2 for the degree bounds. These are the first results for degree-bounded $\{k$-ECSS, k-ECSM $\}$ of the form where the cost of the solution obtained is at most the optimum, and the connectivity constraints are violated by an additive constant. Work done while N. Kumar was a postdoc in the $C \& O$ department at the University of Waterloo. Supported in part by C. Swamy’s NSERC Discovery grant.

Given a set of source-sink pairs, the maximum multiflow problem asks for the largest total amount of flow that can be feasibly routed between them. The minimum multicut problem, which is dual to multiflow, seeks the lowest-cost set of edges whose removal disconnects all source-sink pairs. It is straightforward to see that the value of a minimum multicut is at least that of the corresponding maximum multiflow. The ratio between the two is known as the multiflow-multicut gap. The classical max-flow min-cut theorem tells us that this gap is exactly one when there is only a single source-sink pair. However, for multiple source-sink pairs, the gap can be arbitrarily large. In this work, we investigate the multiflow-multicut gap in cactus graphs, and establish the following results (i) tight upper bound of 1.5 for cycle (ii) an upper bound of 2 + 2/(ln 2) < 3.45 for general cactus graph (iii) tight upper bound of 2 for unicyclic graphs, where the graph contains exactly one cycle (iv) tight upper bound of 2 for path cactus graphs, where cycles are arranged along a single path. We develop novel generalizations of the classical rounding algorithm to establish our results.

Flow sparsification is a classic graph compression technique which, given a capacitated graph G on k terminals, aims to construct another capacitated graph H, called a flow sparsifier, that preserves, either exactly or approximately, every multicommodity flow between terminals (ideally, with size as a small function of k). Cut sparsifiers are a restricted variant of flow sparsifiers which are only required to preserve maximum flows between bipartitions of the terminal set. It is known that exact cut sparsifiers require 2^Ω(k) many vertices [Krauthgamer and Rika, SODA 2013], with the hard instances being quasi-bipartite graphs, where there are no edges between non-terminals. On the other hand, it has been shown recently that exact (or even (1+ε)-approximate) flow sparsifiers on networks with just 6 terminals require unbounded size [Krauthgamer and Mosenzon, SODA 2023, Chen and Tan, SODA 2024]. In this paper, we construct exact flow sparsifiers of size 3^k³ and exact cut sparsifiers of size 2^k² for quasi-bipartite graphs. In particular, the flow sparsifiers are contraction-based, that is, they are obtained from the input graph by (vertex) contraction operations. Our main contribution is a new technique to construct sparsifiers that exploits connections to polyhedral geometry, and that can be generalized to graphs with a small separator that separates the graph into small components. We also give an improved reduction theorem for graphs of bounded treewidth [Andoni et al., SODA 2011], implying a flow sparsifier of size O(k⋅w) and quality O((log w)/log log w), where w is the treewidth.

We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-r graph, there exists a (fractional) multicommodity flow of value f, and a multicut of capacity c such that f ≤ c ≤ O(ln(r+1)) · f. It is well known that the multiflow-multicut gap on an r-vertex (constant degree) expander graph can be Ω(lnr), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time O(ln(r+1))-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.

We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value f with congestion 4, and a multicut of capacity c such that c ≤ 20 f. This implies a multiflow-multicut gap of 80 and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.

We consider the problem of multi-commodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing $\Omega(1)$-fraction of all the demands. To prove this, we give a $L_{1} $-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.

Consider the problem where $n$ jobs, each with a release time, a deadline and a required processing time are to be feasibly scheduled in a single- or multi-processor setting so as to minimize the total energy consumption of the schedule. A processor has two available states: a \emph{sleep state} where no energy is consumed but also no processing can take place, and an \emph{active state} which consumes energy at a rate of one, and in which jobs can be processed. Transitioning from the active to the sleep does not incur any further energy cost, but transitioning from the sleep to the active state requires $q$ energy units. Jobs may be preempted and (in the multi-processor case) migrated. The single-processor case of the problem is known to be solvable in polynomial time via an involved dynamic program, whereas the only known approximation algorithm for the multi-processor case attains an approximation factor of $3$ and is based on rounding the solution to a linear programming relaxation of the problem. In this work, we present efficient and combinatorial approximation algorithms for both the single- and the multi-processor setting. Before, only an algorithm based on linear programming was known for the multi-processor case. Our algorithms build upon the concept of a \emph{skeleton}, a basic (and not necessarily feasible) schedule that captures the fact that some processor(s) must be active at some time point during an interval. Finally, we further demonstrate the power of skeletons by providing an $2$-approximation algorithm for the multiprocessor case, thus improving upon the recent breakthrough $3$-approximation result. Our algorithm is based on a novel rounding scheme of a linear-programming relaxation of the problem which incorporates skeletons.

Given a graph G = (V,E) with non-negative real edge lengths and an integer parameter k, the (uncapacitated) Min-Max Tree Cover problem seeks to find a set of at most k trees which together span V and each tree is a subgraph of G. The objective is to minimize the maximum length among all the trees. In this paper, we consider a capacitated generalization of the above and give the first constant factor approximation algorithm. In the capacitated version, there is a hard uniform capacity (λ) on the number of vertices a tree can cover. Our result extends to the rooted version of the problem, where we are given a set of k root vertices, R and each of the covering trees is required to include a distinct vertex in R as the root. Prior to our work, the only result known was a (2k-1)-approximation algorithm for the special case when the total number of vertices in the graph is kλ [Guttmann-Beck and Hassin, J. of Algorithms, 1997]. Our technique circumvents the difficulty of using the minimum spanning tree of the graph as a lower bound, which is standard for the uncapacitated version of the problem [Even et al.,OR Letters 2004] [Khani et al.,Algorithmica 2010]. Instead, we use Steiner trees that cover λ vertices along with an iterative refinement procedure that ensures that the output trees have low cost and the vertices are well distributed among the trees.

Given an edge weighted graph and a forest $F$, the $\textit{2-edge connectivity augmentation problem}$ is to pick a minimum weighted set of edges, $E'$, such that every connected component of $E'\cup F$ is 2-edge connected. Williamson et al. gave a 2-approximation algorithm (WGMV) for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be modified to obtain a half-integral dual. The 2-edge connectivity augmentation problem has an interesting connection to routing flow in graphs where the union of supply and demand is planar. The half-integrality of the dual leads to a tight 2-approximate max-half-integral-flow min-multicut theorem.

We consider the problem of multicommodity flows in planar graphs. Seymour [Seymour, 1981] showed that if the union of supply and demand graphs is planar, then the cut condition is also sufficient for routing demands. Okamura-Seymour [Okamura and Seymour, 1981] showed that if the supply graph is planar and all demands are incident on one face, then again the cut condition is sufficient for routing demands. We consider a common generalization of these settings where the end points of each demand are on the same face of the planar graph. We show that if the source sink pairs on each face of the graph are such that sources and sinks appear contiguously on the cycle bounding the face, then the flow cut gap is at most 3. We come up with a notion of approximating demands on a face by convex combination of laminar demands to prove this result.

Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires L units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem.