Revisiting parametric multi-terminal problems: Maximum flows, minimum cuts and cut-tree computations

Given an undirected network, the multi-terminal network flows analysis consists in determining the all pairs maximum flow values. In this paper, we consider an undirected network in which some edge capacities are allowed to vary and we analyze the impact of such variations on the all pairs maximum flow values. We first provide an efficient algorithm for the single parametric capacity case, and then propose a generalization to the case of multiple parametric capacities. Moreover, we provide a study on Gomory–Hu cut-tree relationships.     

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.     

Inverse problem of minimum cuts

Given a networkN = (V,A,c), a sources V, a. sinkt V and somes —t cuts and suppose each element of the capacity vectorc can be changed with a cost proportional to the changes, the inverse problem of minimum cuts we study here is to change the original capacities with the least total cost under restrictions on the changes of the capacities, so that all thoses —t cuts become minimum cuts with respect to the new capacities.In this paper we shall show that the inverse problem of minimum cuts can be directly transformed into a minimum cost circulation problem and therefore can be solved efficiently by strongly polynomial algorithms.The author is grateful to the partial support of the Universities Grant Council of Hong Kong under the grant CITYU #9040189Work partially supported by the National Natural Science Foundation of China     

Computing minimum multiway cuts in hypergraphs

The hypergraph $k$-cut problem is the problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into at least $k$ connected components. We present an algorithm for this problem, that runs in strongly polynomial time if both $k$ and the maximum size of the hyperedges are constants. Our algorithm extends the algorithm proposed by Thorup (2008) for computing minimum $k$-cuts of graphs from greedy packings of spanning trees.     

Maximum flows and minimum cuts in the plane

A continuous maximum flow problem finds the largest t such that div v = t F(x, y) is possible with a capacity constraint ||(v ₁, v ₂)|| ≤ c(x, y). The dual problem finds a minimum cut ∂ S which is filled to capacity by the flow through it. This model problem has found increasing application in medical imaging, and the theory continues to develop (along with new algorithms). Remaining difficulties include explicit streamlines for the maximum flow, and constraints that are analogous to a directed graph.     

A fast algorithm for computing minimum 3-way and 4-way cuts

For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n ^k-1 F(n,m))=O(mn ^k log(n ² /m)) time and O(n ²) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn ³) for weighted graphs, but improves the bound ?(mn ³) to O(n ² F(n,m))=O(min{mn ^8/3,m ^3/2 n ²}) for unweighted graphs. The bound ?(mn ⁴) for k=4 improves the previous best randomized bound ?(n ⁶) (for m=o(n ²)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000     

Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs

We consider a class of two-stage stochastic integer programs with binary variables in the first stage and general integer variables in the second stage. We develop decomposition algorithms akin to the $L$ -shaped or Benders’ methods by utilizing Gomory cuts to obtain iteratively tighter approximations of the second-stage integer programs. We show that the proposed methodology is flexible in that it allows several modes of implementation, all of which lead to finitely convergent algorithms. We illustrate our algorithms using examples from the literature. We report computational results using the stochastic server location problem instances which suggest that our decomposition-based approach scales better with increases in the number of scenarios than a state-of-the art solver which was used to solve the deterministic equivalent formulation.     

Number of minimum vertex cuts in transitive graphs

Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let m_k(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{m_k(G): GT_n,k}, where T_n,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k).     

Basis properties and algorithmic specializations for gub transformed networks

Applying standard transformations of generalized upper bounding (GUB) theory to a pure or generalized network basis is shown to yield a reduced working basis that is itself a basis for a reduced network. As a result, the working basis can be represented via specialized data structures for networks. The resultant GUB based specializations to the network simplex algorithm are described.     

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.     

A fast algorithm for minimum weight odd circuits and cuts in planar graphs

We give a simple algorithm for finding a minimum weight odd circuit in planar graphs. By geometric duality, the same algorithm can be used to find minimum weight odd cuts. For general sparse graphs, the fastest known algorithms for these two problems take time and time, respectively.     

An algorithmic approach to finding factorial designs with generalized minimum aberration

Factorial designs are arguably the most widely used designs in scientific investigations. Generalized minimum aberration (GMA) and uniformity are two important criteria for evaluating both regular and non-regular designs. The generation of GMA designs is a non-trivial problem due to the sequential optimization nature of the criterion. Based on an analytical expression between the generalized wordlength pattern and a uniformity measure, this paper converts the generation of GMA designs to a constrained optimization problem, and provides effective algorithms for solving this particular problem. Moreover, many new designs with GMA or near-GMA are reported, which are also (nearly) optimal under the uniformity measure.     

Logical and algorithmic properties of stable conditional independence

The logical and algorithmic properties of stable conditional independence (CI) as an alternative structural representation of conditional independence information are investigated. We utilize recent results concerning a complete axiomatization of stable conditional independence relative to discrete probability measures to derive perfect model properties of stable conditional independence structures. We show that stable CI can be interpreted as a generalization of Markov networks and establish a connection between sets of stable CI statements and propositional formulas in conjunctive normal form. Consequently, we derive that the implication problem for stable CI is coNP-complete. Finally, we show that Boolean satisfiability (SAT) solvers can be employed to efficiently decide the implication problem and to compute concise, non-redundant representations of stable CI, even for instances involving hundreds of random variables.     

Openness properties for parametric set-valued mappings and implicit multifunctions

The aim of this paper is to obtain some openness results in terms of normal coderivative for parametric set-valued mappings acting between infinite dimensional spaces. Then, implicit multifunction results are obtained by simply specializing the openness results. Moreover, we study a kind of metric regularity of the implicit multifunction. The results of the paper generalize several recent results in literature.     

On the continuity of the minimum in parametric quadratic programs

This paper establishes results on the lower semicontinuity and continuity of the optimal objective value of a parametric quadratic program with continuous dependence of the coefficients on parameters. The results established herein generalize directly well-known results on parametric linear programs.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189.     

Generating partitions of a graph into a fixed number of minimum weight cuts

In this paper, we present an algorithm for the generation of all partitions of a graph G with positive edge weights into k mincuts. The algorithm is an enumeration procedure based on the cactus representation of the mincuts of G. We report computational results demonstrating the efficiency of the algorithm in practice and describe in more detail a specific application for generating cuts in branch-and-cut algorithms for the traveling salesman problem.     

Closure properties of parametric subcompleteness

For an ordinal \(\varepsilon \), I introduce a variant of the notion of subcompleteness of a forcing poset, which I call \(\varepsilon \)-subcompleteness, and show that this class of forcings enjoys some closure properties that the original class of subcomplete forcings does not seem to have: factors of \(\varepsilon \)-subcomplete forcings are \(\varepsilon \)-subcomplete, and if \(\mathbb {P}\) and \(\mathbb {Q}\) are forcing-equivalent notions, then \(\mathbb {P}\) is \(\varepsilon \)-subcomplete iff \(\mathbb {Q}\) is. I formulate a Two Step Theorem for \(\varepsilon \)-subcompleteness and prove an RCS iteration theorem for \(\varepsilon \)-subcompleteness which is slightly less restrictive than the original one, in that its formulation is more careful about the amount of collapsing necessary. Finally, I show that an adequate degree of \(\varepsilon \)-subcompleteness follows from the \(\kappa \)-distributivity of a forcing, for \(\kappa >\omega _1\).     

On goodness-of-fit tests for parametric hypotheses in perturbed dynamical systems using a minimum distance estimator

We consider the problem of the construction of the goodness-of-fit test in the case of continuous time observations of a diffusion process with small noise. The null hypothesis is parametric and we use a minimum distance estimator of the unknown parameter. We propose an asymptotically distribution free test for this model.