ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

13. Combinatorics

1991 MS Classification: 90C27, 05C40 Frank, András, Eötvös Loránd University and Ericsson Traffic Laboratory, Budapest, Hungary Applications of Relaxed Submodularity

Let V be a finite set and b : 2^{V} → Z a set-function. The submodular inequality for two subsets X, Y ⊆ V is, as follows:

b(X) + b(Y) ≥ b(X ∩ Y) + b(X ∪ Y).  (1)

Function b is called fully submodular if (1) holds for every two subsets X, Y ⊆ V. (When the reverse inequality holds in (1) we speak of the supermodular inequality. When equality holds everywhere, b is called modular.) Submodular functions proved to be extremely powerful in combinatorial optimization. One intuitive explanation for this is that submodular functions, as recognized in the early eighties, may be considered as discrete counterparts of convex functions. For example, Lovász observed that a (natural) linear extension of an arbitrary set-function h to a real function on R^{V} is convex if and only if h is submodular. Another occurence of this relationship is the discrete separation theorem asserting that if an integer-valued supermodular function p is dominated by an integer-valued submodular functions b, then there is an integer-valued (!) modular function m for which p ≤ m ≤ b. Recently, this kind of analogy has been developed systematically by K. Murota into a theory relating convex analysis and discrete optimization. In applications, however, very often the submodular inequality is not fulfilled for every pair of sets. Accordingly, several types of submodular functions have been introduced, analyzed and applied. For example, b is intersecting submodular if (1) is required only when X ∩ Y is nonempty. Some further relaxations are: T -intersecting, crossing, ST -crossing, skew, and near submodular functions. The main goal of the present paper is to outline recent developments on these functions, along with applications.

1. T -intersecting supermodular functions. For a directed graph G = (V, E) with a specified node s and terminal set T ⊆ V one may want to find a minimum cost subgraph in which there are k edge-disjoint paths from s to every element of T. This has been known to be NP-complete in general (even for k = 1) and solvable in polynomial time if T = V. With the help of T -intersecting supermodular functions we solve the problem for general T provided the cost of every edge entering a node in V − T is zero.

This extension enables one to solve a variation of the problem when k nodedisjoint paths are required to exist from s to the elements of T.

2. Crossing sub- and supermodular functions. A set-function b is called crossing submodular if (1) holds for crossing pairs X, Y (that is, X − Y ≠ ∅, Y − X ≠ ∅, X ∩ Y ≠ ∅, X ∪ Y ≠ V).

(a) We exhibit a new, simplified necessary and sufficient condition for the feasibility of a submodular flow problem constrained by a crossing submodular function. As a consequence, several orientation theorems will be deduced, in particular, we describe a characterization of mixed graphs having a k-edge-connected orientation.

(b) A recent direction of investigations is motivated by connectivity augmentation problems. The general question is to find a graph or digraph that covers a supermodular function. For example, the following theorem, due to A. Benczúr and A. Frank [1996], holds: given a non-negative, integer-valued, symmetric, crossing supermodular function p, there is a graph (V, E) of at most γ edges so that there are at least p(X) edges in the cut [X, V − X] for every subset X ⊆ V if and only if (i) ∑_{i} p(V_{i}) ≤ 2γ holds for every family {V_{1}, …, V_{t}} of disjoint non-empty subsets of V and (ii) there is a member V_{j} ∈ F so that p(V_{1} ∪ V_{j}) = 0 for every partition F := {V_{1}, …, V_{h}} of V with h ≥ γ + 2 and p(V_{1}) = 1. This result may be used to characterize graphs or hypergraphs which can be made k edge-connected by adding at most γ new edges.

3. ST -crossing supermodular functions. Let F be a family of subsets of V and p : F → Z_{+} a function. For two non-empty subsets S, T of V family F is called ST -crossing and p ST -crossing supermodular if X, Y ∈ F, X ∩ Y ∩ S ≠ ∅, T − (X ∪ Y) ≠ ∅ imply that X ∩ Y, X ∪ Y ∈ F and the supermodular inequality holds for these pairs. (When S = T = V, we are back at ordinary crossing functions.) We will report on the following theorem (due to A. Frank and T. Jordán, 1995): given an ST -crossing supermodular function p on F, there is a digraph (V, E) of at most γ edges so that every set X ∈ F admits at least p(X) entering edges if and only if ∑_{i} p(V_{i}) ≤ γ for every family {V_{1}, …, V_{t}} of independent members of F where independence means that V_{i} ∩ V_{j} ∩ S = ∅ or T ⊆ V_{i} ∪ V_{j} (1 ≤ i < j ≤ t). This result implies a solution to the node connectivity augmentation problem of directed graphs. As a recent development, we describe a (purely combinatorial) strongly polynomial algorithm for computing the minimum digraph in question, as well as the maximum independent family in the special case p ≡ 1. This way an algorithm is available for finding a minimum number of new edges whose addition to a given k-connected digraph results in a (k + 1)-connected digraph. The algorithm also finds a surprising application in combinatorial geometry: with its help, a vertically convex region R of the plane, bounded by horizontal and vertical segments, can be covered by a minimum number of rectangles belonging to R.