A note on the parametric maximum flow problem and some related reoptimization issues

In this paper, we will extend the results about the parametric maximum flow problem to networks in which the parametrization of the arc capacities can involve both the source and the sink, as in Gallo, Grigoriadis, and Tarjan (1989), and also an additional node. We will show that the minimum cuts of the investigated networks satisfy a relaxed form of the generalized nesting property (Arai, Ueno, and Kajitani, 1993). A consequence is that the corresponding parametric maximum flow value function has at most n −1 breakpoints. All the minimum cut capacities can therefore be computed by O(1) maximum flow computations. We will show then that, given O(n) increasing values of the parameter, it is possible to compute the corresponding maximum flows by O(1) maximum flow computations, by suitably extending Goldberg and Tarjan’s maximum flow algorithm.     

Minimum cut bases in undirected networks

Given an undirected, connected network G=(V,E) with weights on the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisingly, this problem has not attained as much attention as another graph theoretic problem closely related to it, namely, the cycle basis problem. We consider two versions of the problem: the unconstrained and the fundamental cut basis problem.For the unconstrained case, where the cuts in the basis can be of an arbitrary kind, the problem can be written as a multiterminal network flow problem, and is thus solvable in strongly polynomial time. In contrast, the fundamental cut basis problem, where all cuts in the basis are obtained by deleting an edge, each from a spanning tree T, is shown to be NP-hard. In this proof, we also show that a tree which induces the minimum fundamental cycle basis is also an optimal solution for the minimum fundamental cut basis problem in unweighted graphs.We present heuristics, integer programming formulations and summarize first experiences with numerical tests.     

Complexity of Source-Sink Monotone 2-parameter min cut

There are many applications of max flow with capacities that depend on one or more parameters. Many of these applications fall into the “Source-Sink Monotone” framework, a special case of Topkis's monotonic optimization framework, which implies that the parametric min cuts are nested. When there is a single parameter, this property implies that the number of distinct min cuts is linear in the number of nodes, which is quite useful for constructing algorithms to identify all possible min cuts.When there are multiple Source-Sink Monotone parameters, and vectors of parameters are ordered in the usual vector sense, the resulting min cuts are still nested. However, the number of distinct min cuts was an open question. We show that even with only two parameters, the number of distinct min cuts can be exponential in the number of nodes.     

Minimum flow problem on network flows with time-varying bounds

In this paper, we consider the minimum flow problem on network flows in which the lower arc capacities vary with time. We will show that this problem for set {0, 1, … , T} of time points can be solved by at most n minimum flow computations, by combining of preflow-pull algorithm and reoptimization techniques (no matter how many values of T are given). Running time of the presented algorithm is O(n²m).     

Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra

In this paper, we study the relationship between 2D lattice-free cuts, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in ${\mathbb{R}^2}$ , and various types of disjunctions. Recently Li and Richard (2008), studied disjunctive cuts obtained from t-branch split disjunctions of mixed-integer sets (these cuts generalize split cuts). Balas (Presentation at the Spring Meeting of the American Mathematical Society (Western Section), San Francisco, 2009) initiated the study of cuts for the two-row continuous group relaxation obtained from 2-branch split disjunctions. We study these cuts (and call them cross cuts) for the two-row continuous group relaxation, and for general MIPs. We also consider cuts obtained from asymmetric 2-branch disjunctions which we call crooked cross cuts. For the two-row continuous group relaxation, we show that unimodular cross cuts (the coefficients of the two split inequalities form a unimodular matrix) are equivalent to the cuts obtained from maximal lattice-free sets other than type 3 triangles. We also prove that all 2D lattice-free cuts and their S-free extensions are crooked cross cuts. For general mixed integer sets, we show that crooked cross cuts can be generated from a structured three-row relaxation. Finally, we show that for the corner relaxation of an MIP, every crooked cross cut is a 2D lattice-free cut.     

Quaternionic pryms and Hodge classes

Abelian varieties of dimension 2n on which a definite quaternion algebra acts are parametrized by symmetrical domains of dimension n(n−1)/2. Such abelian varieties have primitive Hodge classes in the middle dimensional cohomology group. In general, it is not clear that these are cycle classes. In this paper we show that a particular 6-dimensional family of such 8-folds are Prym varieties and we use the method of Schoen to show that all Hodge classes on the general abelian variety in this family are algebraic. We also consider Hodge classes on certain 5-dimensional subfamilies and relate these to the Hodge conjecture for abelian 4-folds.     

Most balanced minimum cuts

We consider the problem of finding most balanced cuts among minimum st-edge cuts and minimum st-vertex cuts, for given vertices s and t, according to different balance criteria. For edge cuts we seek to maximize . For vertex cuts C of G we consider the objectives of (i) maximizing min{|S|,|T|}, where {S,T} is a partition of V(G)?C with s∈S, t∈T and [S,T]=0?, (ii) minimizing the order of the largest component of G−C, and (iii) maximizing the order of the smallest component of G−C.All of these problems are NP-hard. We give a PTAS for the edge cut variant and for (i). These results also hold for directed graphs. We give a 2-approximation for (ii), and show that no non-trivial approximation exists for (iii) unless P=NP.To prove these results we show that we can partition the vertices of G, and define a partial order on the subsets of this partition, such that ideals of the partial order correspond bijectively to minimum st-cuts of G. This shows that the problems are closely related to Uniform Partially Ordered Knapsack (UPOK), a variant of POK where element utilities are equal to element weights. Our algorithm is also a PTAS for special types of UPOK instances.     

A contraction algorithm for finding small cycle cutsets

We consider the problem of finding a minimum size cutset in a directed graph G = (V, E), i.e., a vertex set that cuts all cycles in G. Since the general problem is NP-complete we concentrate on finding small cutsets. The algorithm we suggest uses contraction operations to reduce the graph size and to identify candidates for the cutset; the complexity of the algorithm is O(|E|log|V|). This contraction algorithm is compared to Shamir-Rosen algorithm. It is shown that the class of graphs for which the contraction algorithm finds a minimum cutset (completely contractible graphs) properly contains the class of graphs for which Shamir-Rosen algorithm finds a minimum cutset (quasi-reducible graphs) and thus that the contraction algorithm is more powerful. As a by-product of this analysis we construct a hierarchy of the classes of graphs for which minimum cutsets can be found efficiently. The class of quasi-reducible graphs lies, in this hierarchy, between two classes which are closely related. This result illuminates the nature of the quasi-reducible graphs. The hierarchy constructed allows us also to compare the Wang-Lloyd-Soffa algorithm to the Shamir-Rosen algorithm and to the contraction algorithm.     

Ordered optimal solutions and parametric minimum cut problems

In this paper, we present an algebraic sufficient condition for the existence of a selection of optimal solutions in a parametric optimization problem that are totally ordered, but not necessarily monotone. Based on this result, we present necessary and sufficient conditions that ensure the existence of totally ordered selections of minimum cuts for some classes of parametric maximum flow problems. These classes subsume the class studied by Arai et al. [Discrete Appl. Math. 41 (1993) 69–74] as a special case.     

Random walks and local cuts in graphs

For a specified subset S of vertices in a graph G we consider local cuts that separate a subset of S. We consider the local Cheeger constant which is the minimum Cheeger ratio over all subsets of S, and we examine the relationship between the local Cheeger constant and the Dirichlet eigenvalue of the induced subgraph on S. These relationships are summarized in a local Cheeger inequality. The proofs are based on the methods of establishing isoperimetric inequalities using random walks and the spectral methods for eigenvalues with Dirichlet boundary conditions.     

3‐Flows and Combs

Tutte's 3‐Flow Conjecture states that every 2‐edge‐connected graph with no 3‐cuts admits a 3‐flow. The 3‐Flow Conjecture is equivalent to the following: let G be a 2‐edge‐connected graph, let S be a set of at most three vertices of G; if every 3‐cut of G separates S then G has a 3‐flow. We show that minimum counterexamples to the latter statement are 3‐connected, cyclically 4‐connected, and cyclically 7‐edge‐connected.     

Determining the Optimal Flows in Zero-Time Dynamic Networks

Here we are dealing with minimum cost flow problem on dynamic network flows with zero transit times and a new arc capacity, horizon capacity, which denotes an upper bound on the total flow traversing through on an arc during a pre-specified time horizon T. We develop a simple approach based on mathematical modelling attributes to solve the min-cost dynamic network flow problem where arc capacities and costs are time varying, and horizon capacities are considered. The basis of the method is simple and relies on the appropriate defining of polyhedrons, and in contrast to the other usual algorithms that use the notion of time expanded network, this method runs directly on the original network.     

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.     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

Parallel nested dissection for path algebra computations

This paper extends the authors' parallel nested dissection algorithm of [13] originally devised for solving sparse linear systems. We present a class of new applications of the nested dissection method, this time to path algebra computations (in both cases of single source and all pair paths), where the path algebra problem is defined by a symmetric matrix A whose associated graph G with n vertices is planar. We substantially improve the known algorithms for path algebra problems of that general class; this has further applications to maximum flow and minimum cut problems in an undirected planar network and to the feasibility testing of a multicommodity flow in a planar network.     

A note on the MIR closure and basic relaxations of polyhedra

Anderson et al. (2005) [1] show that for a polyhedral mixed integer set defined by a constraint system Ax≥b, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a basic relaxation, i.e., one defined by a subset of linearly independent constraints. This result implies that any split cut can be obtained as an intersection cut. Equivalence between split cuts obtained from simple disjunctions of the form x_j≤0 or x_j≥1 and intersection cuts was shown earlier for 0/1-mixed integer sets by Balas and Perregaard (2002) [4]. We give a short proof of the result of Anderson, Cornuéjols and Li using the equivalence between mixed integer rounding (MIR) cuts and split cuts.     

Minimal stabilizers with arbitrary spectrum for SIMO and MISO systems

We consider two classes of linear dynamical systems, single-input-many-output (SIMO) systems and many-input-single-output (MISO) systems. For both classes, we consider the problem of synthesizing a stabilizer of minimum dimension providing pole assignment in the closed-loop system. We show that, for these classes, a minimal stabilizer providing pole assignment has dimension k _min = min{ν ? 1, µ ? 1}, where ν and µ are the controllability and observability indices of the original (SIMO or MISO) dynamical system.     

The Positive Lightness of Digraphs,Embeddable in a Surface,without 4-Cycles

The positive lightness of a digraph is the minimum arc value, where the value of an arc is the maximum of the in-degrees of its terminal vertices. We determine upper bounds for the positive lightness of digraphs with nonzero minimum in-degree and a given girth $k⩾5$ which can be embedded in a surface S. These bounds are tight for surfaces of nonnegative Euler characteristics. We further obtain bounds for classes of graphs where 3-cycles are permitted.     

Empirical bayesian test of the smoothness

In the context of adaptive nonparametric curve estimation a common assumption is that a function (signal) to estimate belongs to a nested family of functional classes. These classes are often parametrized by a quantity representing the smoothness of the signal. It has already been realized by many that the problem of estimating the smoothness is not sensible. What can then be inferred about the smoothness? The paper attempts to answer this question. We consider implications of our results to hypothesis testing about the smoothness and smoothness classification problem. The test statistic is based on the empirical Bayes approach, i.e., it is the marginalized maximum likelihood estimator of the smoothness parameter for an appropriate prior distribution on the unknown signal.