In 1998, Hu and Liu developed a strongly polynomial algorithm for solving the inverse arborescence problem that aims at minimally modifying a given cost-function on the edge-set of a digraph D so that an input spanning arborescence of D becomes a cheapest one. In this note, we develop a conceptually simpler algorithm along with a new min–max formula for the minimum modification of the cost-function. The approach is based on a link to a min–max theorem and a simple (two-phase greedy) algorithm by the first author from 1979 concerning the primal optimization problem of finding a cheapest subgraph of a digraph that covers an intersecting family along with the corresponding dual optimization problem, as well.

We introduce the notion of sink-stable sets of a digraph and prove a min-max formula for the maximum cardinality of the union of $k$ sink-stable sets. The results imply a recent min-max theorem of Abeledo and Atkinson on the Clar number of bipartite plane graphs and a sharpening of Minty's coloring theorem. We also exhibit a link to min-max results of Bessy and Thomassé and of Sebö on cyclic stable sets.

Let G be an Eulerian digraph, and let {x1, x2}, {y1,y2} be two pairs of vertices in G. A directed path from a vertex s to a vertex t is called an st-path. An instance (G;{x1, x2}, {y1,y2}) is called feasible if there is a choice of h,i,j,k with {h,i} = {j,k} = {1,2} such that G has two arc-disjoint xhxi- and yjyk-paths. In this paper, we characterize the structure of minimal infeasible instances, based on which an O(m+nlog n) time algorithm is presented to decide whether a given instance is feasible, where n and m are the number of vertices and arcs in the instance, respectively. If the instance is feasible, the corresponding two arc-disjoint paths can be computed in O(m(m+nlog n)) time.

Generalizing the two-commodity flow theorem of Rothschild and Whinston [Oper. Res., 14 (1966), pp. 377--387] and the multiflow theorem of Lovász [Acta Mat. Akad. Sci. Hungaricae, 28 (1976), pp. 129--138] and Cherkasky [Ekonom.-Mat. Metody, 13 (1977), pp. 143--151], Karzanov and Lomonosov [Mathematical Programming, O. I. Larichev, ed., Institute for System Studies, 1978, pp. 59--66] in 1978 proved a min-max theorem on maximum multiflows. Their original proof is quite long and technical and relies on earlier investigations into metrics. The main purpose of the present paper is to provide a relatively simple proof of this theorem. Our proof relies on the locking theorem, which is another result of Karzanov and Lomonosov, and the polymatroid intersection theorem of Edmonds [Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Gordon and Breach, 1970, pp. 69--87]. For completeness, we also provide a simplified proof of the locking theorem. Finally, we introduce the notion of a node demand problem and, as another application of the locking theorem, we derive a feasibility theorem concerning it. The presented approach gives rise to (combinatorial) polynomial-time algorithms.

Generalizing and unifying earlier results of W. Mader, and A. Frank and B. Jackson, we prove two splitting theorems concerning mixed graphs. By invoking these theorems we obtain min-max formulae for the minimum number of new edges to be added to a mixed graph so that the resulting graph satisfies local edge-connectivity prescriptions. An extension of Edmonds’s theorem on disjoint arborescences is also deduced along with a new sufficient condition for the solvability of the edge-disjoint paths problem in digraphs. The approach gives rise to strongly polynomial algorithms for the corresponding optimization problems.

What is the minimum number $\gamma$ of edges to be added to a given graph G so that in the resulting graph the edge-connectivity between every pair $\{ u,v \}$ of its nodes is at least a prescribed value $r( u,v )$? Generalizing earlier results of S. Sridhar and R. Chandrasekaran [Integer Programming and Combinatorial Optimization, R. Kannan and W. Pulleyblank, eds., Proceedings of a conference held at the University of Waterloo, University of Waterloo Press, Waterloo, Ontario, Canada, 1990, pp. 467–484] (when G is the empty graph), of K. P. Eswaran and R. E. Tarjan [SIAM Journal on Computing, 5 (1976), pp. 653–665] (when $r ( u,v ) \equiv 2$), and of G.-R. Cai and Y.-G. Sun [Networks, 19 (1989 ), pp. 151–172 ] (when $r ( u,v ) \equiv k\geqq 2$, we derive a min-max formula for $\gamma$ and describe a polynomial time algorithm to compute $\gamma$. The directed counterpart of the problem is solved in the same sense for the case when $r ( u,v ) \equiv k\geqq 1$ and is shown to be NP-complete if $r ( u,v ) \equiv 1$ for $u,v \in T$, and $r( u,v ) \equiv 0$ otherwise where T is a specified subset of nodes. A fundamental tool in the proof is the splitting theorems of W. Mader [Annals of Discrete Mathematics, 3 (1978), pp. 145–164] and L. Lovász [lecture, Prague, 1974; North–Holland, Amsterdam, 1979]. We also rely extensively on techniques concerning submodular functions. The method makes it possible to solve a degree-constrained version of the problem. The minimum-cost augmentation problem can also be solved in polynomial time provided that the edge-costs arise from node-costs, while the problem for arbitrary edge-costs was known to be NP-complete even for $r( u,v ) \equiv 2$.

The problem of determining the minimum number gamma of edges to be added to a graph G so that in the resulting graph the edge-connectivity between every pair (u,v) of nodes is at least a prescribed value r(u,v) is treated. A min-max formula for gamma is derived, and a polynomial-time algorithm for computing gamma is described. The directed counterpart of the problem is also solved for the case in which r(u,v)=k>or=1. The approach used makes it possible to solve a degree-constrained version of the problem. The minimum-cost augmentation problem can also be solved in polynomial time provided that the edge costs arise from node costs.>

We present a preprocessing algorithm to make certain polynomial algorithms strongly polynomial. The running time of some of the known combinatorial optimization algorithms depends on the size of the objective function w. Our preprocessing algorithm replaces w by an integral valued w whose size is polynomially bounded in the size of the combinatorial structure and which yields the same set of optimal solutions as w. As applications we show how existing polynomial algorithms for finding the maximum weight clique in a perfect graph and for the minimum cost submodular flow problem can be made strongly polynomial. The method relies on Lovász's simultaneous approximation algorithm.