The max-flow min-cut property of two-dimensional affine convex geometries

In a matroid, (X,e) is a rooted circuit if X is a set not containing element e and X∪{e} is a circuit. We call X a broken circuit of e. A broken circuit clutter is the collection of broken circuits of a fixed element. Seymour [The matroids with the max-flow min-cut property, J. Combinatorial Theory B 23 (1977) 189-222] proved that a broken circuit clutter of a binary matroid has the max-flow min-cut property if and only if it does not contain a minor isomorphic to Q₆. We shall present an analogue of this result in affine convex geometries. Precisely, we shall show that a broken circuit clutter of an element e in a convex geometry arising from two-dimensional point configuration has the max-flow min-cut property if and only if the configuration has no subset forming a ‘Pentagon’ configuration with center e.Firstly we introduce the notion of closed set systems. This leads to a common generalization of rooted circuits both of matroids and convex geometries (antimatroids). We further study some properties of affine convex geometries and their broken circuit clutters.     

Examples of max-flow and min-cut problems with duality gaps in continuous networks

Strang (Mathematical Programming 26, 1983) gave a method to establish a max-flow min-cut theorem in a domain of a Euclidean space. The method can be applied also to max-flow min-cut problems defined by Iri (Survey of Mathematical Programming, North-Holland, 1979) whenever the capacity functions of max-flow problems are bounded and continuous. This paper deals with max-flow min-cut problems of Strang and Iri with unbounded or noncontinuous capacity functions. It is proved that, in such problems, max-flow min-cut theorems may fail to hold.     

Integer version of the multipath flow network synthesis problem

We consider the following integer multipath flow network synthesis problem. We are given two positive integers q, n, (1<q<n), and a non-negative, integer, symmetric, n×n matrix R, each non-diagonal element r_ij of which represents the minimum requirement of q-path flow value between nodes i and j in an undirected network on the node set N={1,2,…,n}. We want to construct a simple, undirected network G=[N,E] with integer edge capacities {u_e:e∈E} such that each of these flow requirements can be realized (one at a time) and the sum of all the edge capacities is minimum. We present an O(n³) combinatorial algorithm for the problem and we show that the problem has integer rounding property.     

Pathwidth, trees, and random embeddings

We prove that, for every integer k≥1, every shortest-path metric on a graph of pathwidth k embeds into a distribution over random trees with distortion at most c=c(k), independent of the graph size. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair [12] states that for every minor-closed family of graphs F, there is a constant c(F) such that the multi-commodity max-flow/min-cut gap for every flow instance on a graph from F is at most c(F). The preceding embedding theorem is used to prove this conjecture whenever the family F does not contain all trees.     

Improved bounds on the max-flow min-cut ratio for multicommodity flows

In this paper we consider the worst case ratio between the capacity of min-cuts and the value of max-flow for multicommodity flow problems. We improve the best known bounds for the min-cut max-flow ratio for multicommodity flows in undirected graphs, by replacing theO(logD) in the bound byO(logk), whereD denotes the sum of all demands, andk demotes the number of commodities. In essence we prove that up to constant factors the worst min-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities.Klein, Rao, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the min-cut max-flow ratio in general undirected graphs is bounded byO(logClogD), whereC denotes the sum of all the capacities. Tragoudas has improved this bound toO(lognlogD), wheren is the number of nodes in the network. Garg, Vazirani and Yannakakis further improved this toO(logklogD). Klein, Plotkin and Rao have proved that for planar networks, the ratio isO(logD).Our result improves the bound for general networks toO(log² k) and the bound for planar networks toO(logk). In both cases our result implies the first non-trivial bound that is independent of the magnitude of the numbers involved. The method presented in this paper can be used to give polynomial time approximation algorithms to the minimum cuts in the network up to the above factors.Preliminary version appeared in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, 691-697.Research supported by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by a grant from Mitsubishi Electric Laboratories.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

A Relaxation of a Min-Cut Problem in an Anisotropic Continuous Network

Strang [18] introduced optimization problems on a Euclidean domain which are closely related with problems in mechanics and noted that the problems are regarded as continuous versions of famous max-flow and min-cut problems. In [15] we generalized the problems and called the generalized problems max-flow and min-cut problems of Strang's type. In this paper we formulate a relaxed version of the min-cut problem of Strang's type and prove the existence of optimal solutions under some suitable conditions. The conditions are essential. In fact, there is an example of the relaxed version which has no optimal solutions if the conditions are not fulfilled. We give such an example in the final section. Accepted 8 October 1998     

A note on polylinking flow networks

This is a supplementary note on M. X. Goemans, S. Iwata, and R. Zenklusen’s paper that proposes a flow model based on polylinking systems. Their flow model is a series (or tandem) connection of polylinking systems. We can consider an apparently more general model of a polylinking flow network which consists of an ordinary arc-capacitated network endowed with polylinking systems on the vertex set, one for each vertex of the network. This is a natural, apparent generalization of polymatroidal flow model of E. L. Lawler and C. U. Martel and of generalized-polymatroidal flow model of R. Hassin. We give a max-flow min-cut formula for the polylinking network flow problem and discuss some acyclic flow property of polylinking flows.     

Control of the transition probabilities of input rates of a flow in a network

A stochastic control problem concerning the flow in a network is considered. Some of the nodes in the network are fed by an external input whose rate constitute a component of a continuous in time L-state Markov process θ. A numerical study is conducted on the dependence of the network performance on the choice of the q-matrix (the matrix of the infinitesimal characteristics of θ) of θ. Also, for the sake of completeness, the problem of an optimal q-matrix is discussed.     

Reduced graphs for min-cut/max-flow approaches in image segmentation

In few years, min-cut/max-flow approach has become a leading method for solving a wide range of problems in computer vision. However, min-cut/max-flow approaches involve the construction of huge graphs which sometimes do not fit in memory. Currently, most of the max-flow algorithms are impracticable to solve such large scale problems. In this paper, we introduce a new strategy for reducing exactly graphs in the image segmentation context. During the creation of the graph, we test if the node is really useful to the max-flow computation. Numerical experiments validate the relevance of this technique to segment large scale images.     

Ancestor tree for arbitrary multi-terminal cut functions

In many applications, a function is defined on the cuts of a network. In the max-flow min-cut theorem, the function on a cut is simply the sum of all capacities of edges across the cut, and we want the minimum value of a cut separating a given pair of nodes. To find the minimum cuts separating pairs of nodes, we only needn – 1 computations to construct the cut-tree. In general, we can define arbitrary values associated with all cuts in a network, and assume that there is a routine which gives the minimum cut separating a pair of nodes. To find the minimum cuts separating pairs of nodes, we also only needn – 1 routine calls to construct a binary tree which gives all minimum partitions. The binary tree is analogous to the cut-tree of Gomory and Hu.     

On the q-extension of Euler and Genocchi numbers

Carlitz has introduced an interesting q-analogue of Frobenius-Euler numbers in [L. Carlitz, q-Bernoulli numbers and polynomials, Duke Math. J. 15 (1948) 987-1000; L. Carlitz, q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc. 76 (1954) 332-350]. He has indicated a corresponding Stadudt-Clausen theorem and also some interesting congruence properties of the q-Euler numbers. A recent author's study of more general q-Euler and Genocchi numbers can be found in previous publication [T. Kim, L.C. Jang, H.K. Pak, A note on q-Euler and Genocchi numbers, Proc. Japan Acad. Ser. A Math. Sci. 77 (2001) 139-141]. In this paper we give a new construction of q-Euler numbers, which are different from Carlitz's q-extension and author's q-extension in previous publication (see [T. Kim, L.C. Jang, H.K. Pak, A note on q-Euler and Genocchi numbers, Proc. Japan Acad. Ser. A Math. Sci. 77 (2001) 139-141]). By using our q-extension of Euler numbers, we can also consider a new q-extension of Genocchi numbers and obtain some interesting relations between q-extension of Euler numbers and q-extension of Genocchi numbers.     

Coarse Differentiation and Multi-flows in Planar Graphs

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound (Chakrabarti et al. in 49th Annual Symposium on Foundations of Computer Science, pp. 761–770, 2008) for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair. This also improves the largest known gap for planar graphs from \frac32\frac{3}{2} to 2, yielding the first lower bound that does not follow from elementary calculations. Our approach uses the coarse differentiation method of Eskin, Fisher, and Whyte in order to lower bound the distortion for embedding a particular family of shortest-path metrics into L ₁.     

Campopiano-type bounds in non-Hamming array coding

Campopiano [C.N. Campopiano, Bounds on burst error correcting codes, IRE Trans. IT-8 (1962) 257-259] obtained an upper bound for burst error correction in classical coding systems where codes are subsets/subspaces of the space , the space of all n-tuples with entries from a finite field F_q equipped with the Hamming metric. In [S. Jain, Bursts in m-metric array codes, Linear Algebra Appl., in press], the author introduced the notion of burst errors for m-metric array coding systems where m-metric array codes are subsets/subspaces of the space Mat_m×s(F_q), the linear space of all m × s matrices with entries from a finite field F_q, endowed with a non-Hamming metric and obtained some lower bounds for burst error correction. In this paper, we obtain various construction upper bounds on the parameters of m-metric array codes for the detection and correction of burst errors.     

Four problems on graphs with excluded minors

The four problems we consider are the Chinese postman, odd cut, co-postman, and odd circuit problems. Seymour's characterization of matroids having the max-flow min-cut property can be specialized to each of these four problems to show that the property holds whenever the graph has no certain excluded minor. We develop a framework for characterizing graphs not having these excluded minors and use the excluded minor characterizations to solve each of the four optimization problems. In this way, a constructive proof of Seymour's theorem is given for these special cases. We also show how to solve the Chinese postman problem on graphs having no four-wheel minor, where the max-flow min-cut property need not hold.     

New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

We give a new upper bound on the maximum size Aq(n,d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q?3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q=3,4,5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme.     

Permanence of a delayed SIR epidemic model with density dependent birth rate

In this paper, we consider the permanence of a modified delayed SIR epidemic model with density dependent birth rate which is proposed in [M. Song, W. Ma, Asymptotic properties of a revised SIR epidemic model with density dependent birth rate and time delay, Dynamic of Continuous, Discrete and Impulsive Systems, 13 (2006) 199–208]. It is shown that global dynamic property of the modified delayed SIR epidemic model is very similar as that of the model in [W. Ma, Y. Takeuchi, T. Hara, E. Beretta, Permanence of an SIR epidemic model with distributed time delays, Tohoku Math. J. 54 (2002) 581–591; W. Ma, M. Song, Y. Takeuchi, Global stability of an SIR epidemic model with time delay, Appl. Math. Lett. 17 (2004) 1141–1145].     

Vector transversals

The max-flow min-cut theorem is used to give a necessary and sufficient condition for one or two finite families of finite non-negative vectors to have a (common) vector transversal. The duality theorem of linear programming is then used to prove the polymatroid intersection theorem for any finite number of polymatroids, which in turn is used to give a necessary and sufficient condition for any finite number of finite families of finite sets to have a common vector transversal. (This result was announced without proof in [D. R. Woodall, in “Combinatorics (Proceedings, 4th British Combinatorial Conference)” pp. 195–200, London Mathematical Society Lecture Note Series No. 13, Cambridge Univ. Press, London/New York 1974].) This provides a weak generalization of the well-known conditions of Hall and of Ford and Fulkerson for one and two families of sets, respectively, to have a (common) transversal. It also provides a stronger necessary condition than was previously known for three or more families of sets to have a common transversal.     

Fractional covers for forests and matchings

We give polynomial algorithms for the fractional covering problems for forests andb-matchings: min{1·y: yA≥w,y≥0} whereA is a matrix whose rows are the incidence vectors of forests/b-matchings respectively. It is shown that each problem can be solved by a series of max-flow/min-cut calculations, and hence the use of the ellipsoid algorithm to guarantee a polynomial algorithm can be avoided. Visiting professor at the European Institute for Advanced Studies in Management in Brussels and at CORE. Supported in part by the CIM. On leave from New York University, New York, NY 10006.