Applications of Relaxed Submodularity

András Frank

Abstract. Combinatorial optimization problems often give rise to setfunctions which satisfy the sub- or supermodular inequality only for certain pairs of subsets. Here we discuss connectivity problems and show how results on relaxed submodular functions help in solving them.

1991 Mathematics Subject Classification: 90C27, 05C40

Keywords and Phrases: combinatorial optimization, submodular functions, connectivity of graphs

1. Introduction

Let V be a finite set and b : 2^{S} → R ∪ {∞} and p : 2^{S} → R ∪ {−∞} two set-functions. The submodular and the supermodular inequality, respectively, for subsets X, Y ⊆ V are, as follows:

b(X) + b(Y) ≥ b(X ∩ Y) + b(X ∪ Y),  (1.1b)
p(X) + p(Y) ≤ p(X ∩ Y) + p(X ∪ Y).  (1.1p)

Function b [respectively, p] is called fully submodular if (1.1b) [ fully supermodular if (1.1p)] holds for every two subsets X, Y ⊆ V. (When equality holds everywhere, we speak of a modular function.) We call a function semimodular if it is submodular or supermodular.

Semimodular functions proved to be extremely powerful in combinatorial optimization. One intuitive explanation for this is that submodular functions may be considered as discrete counterparts of convex functions. For example, L. Lovász [L83] 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 occurrence of this relationship is the discrete separation theorem [F82] asserting that

Research supported by the Hungarian National Foundation for Scientific Research Grant, OTKA T17580.

The paper was completed while the author visited the Department of Mathematics, EPFL, Lausanne, June 1998. if an integer-valued supermodular function p is dominated by an integer-valued submodular function 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 [M96] into a theory relating convex analysis and discrete optimization.

In applications, however, often the submodular inequality is not fulfilled by every pair of sets. Accordingly, several frameworks concerning semimodular functions have been introduced, analyzed, and applied. One fundamental property of these models is total dual integrality (TDI-ness) which ensured applicability to weighted optimization problems, as well. (See [Schrijver, 1984], for an account.) For example, C. Lucchesi and D. Younger [LY78] proved a min-max formula for the minimum number of edges of a directed graph whose contraction results in a strongly connected digraph. J. Edmonds and R. Giles [EG76], by introducing submodular flows, found an extension to a minimum cost version. Based on this ground, a polynomial time algorithm was developed in [F81] to actually find the cheapest edge set.

There have been optimization problems, however, where the minimum cardinality case was nicely treatable while the min-cost version was NP-complete. For example, making a digraph strongly connected by adding new edges is such a problem [Eswaran and Tarjan, 1976]. This type of connectivity augmentation problems gave rise recently to a new class of results concerning relaxed semimodular functions.

In this paper we outline the new frameworks, exhibit recent developments concerning submodular flows, and show applications to problems from the area of graph connectivity.

The following forms of relaxed semimodularity will be used. Let S and T be two subsets of a groundset V and b a set-function. b is intersecting submodular if (1.1b) holds whenever X∩Y ≠ ∅. b is crossing submodular if (1.1b) holds whenever X ∩ Y ≠ ∅ and V − (X ∪ Y) ≠ ∅. Intersecting and crossing supermodular funtions are defined analogously but for supermodularity we need further relaxations. Let p be a non-negative set-function. p is ST -crossing supermodular if (1.1p) holds whenever p(X) > 0, p(Y) > 0, X ∩ Y ∩ T ≠ ∅ and S − (X ∪ Y) ≠ ∅. p is T -intersecting supermodular if (1.1p) holds whenever p(X) > 0, p(Y) > 0, X ∩ Y ∩ T ≠ ∅. p is skew supermodular if p(X) + p(Y) ≤ max(p(X ∩ Y) + p(X ∪ Y), p(X − Y) + p(Y − X)) whenever p(X) > 0, p(Y) > 0. We call a set-function p symmetric if p(X) = p(V − X) for every X ⊆ V. Throughout we will assume that the occurring set-functions are integer-valued.

2. Connectivity problems

In a graph or digraph G, λ(u, v) (respectively, κ(u, v)) denotes the maximum number of edge-disjoint (openly disjoint) paths from u to v. λ(u, v) is called the local edge-connectivity from u to v while the minimum of these λ-values (κ-values) is the edge-connectivity (node-connectivity) of G. A digraph is k-edge- (node-) connected from root s if λ(s, v) ≥ k (κ(s, v) ≥ k) for every v ∈ V.

The problems we consider can be cast in the following general form: Create an (optimal) graph (or digraph, or hypergraph) satisfying some connectivity properties. Sometimes we are interested only in the existence of the requested object, other times finding an optimal object is also important. A connectivity property typically means that bounds are imposed on the number of edges (nodes) in cuts. ”Creating” means that certain specified operations are allowed. We will consider the following operations: Given a graph or digraph, take a subgraph, take a supergraph (that is, augment the graph), orient the undirected edges, reorient some of the directed edges.

The travelling salesman problem, for example, is a special case, as it requires finding a minimum cost 2-edge-connected subgraph of n edges. Another special case is the Steiner-tree problem which seeks for cheapest subgraphs containing at least one edge from each cut separating a specified set T of terminal nodes. These well-known NP-complete problems are special cases of several other connectivity problems. On the positive side, the problem of finding a minimum cost subdigraph of a digraph that contains k edge-disjoint paths from s to t is a special min-cost flow problem and hence it is solvable in polynomial time. Here we consider other connectivity problems having a good characterization and/or a polynomial-time solution algorithm. Some of them are, as follows.

Subgraph problems S1. Given a graph and a stable set S, find a (minimum cost) spanning tree satisfying upper and lower bound requirements for its degree of the nodes in S. S2. Given a digraph with a root s, find a cheapest subgraph which is k-edge- (node-) connected from s.

Supergraph (=augmentation) problems A1. Given a digraph, add a cheapest subset of new edges to get a k rooted edge-connected digraph. A2. Given a digraph, add a minimum number of new edges to get a k-edge- (node-) connected digraph. A3. Given a digraph and two subsets S and T of nodes, add a minimum number of new edges from S to T to get a digraph with λ(s, t) ≥ k (resp., κ(s, t) ≥ k) whenever s ∈ S, t ∈ T. A4. Given a hypergraph, add a minimum number of edges to obtain a k-edge-connected hypergraph.

Orientation problems O1. Given a graph, orient the edges to get a digraph which is k-edge-connected from a root s and l-edge-connected to s. (When k = l, the digraph is just k-edge-connected). O2. Given a mixed graph, orient its undirected edges so as to obtain a k-edge-connected digraph. O3. Given a digraph with edge-costs, reorient a cheapest subset of edges to get a k-edge-connected digraph.

Problem S1 is a matroid intersection problem and therefore Edmonds’ [E79] intersection theorem and algorithm apply. A solution to Problem S2 requires submodular flows, the topic of Section 3. Problem A1 may be formulated as a special case of S2, but the other augmentation problems need different techniques, to be discussed in Sections 4 and 5. All the orientation problems will be handled with the help of submodular flows.

3. Submodular flows

Let V be a ground-set and b an integer-valued set-function with b(∅) = 0. Associate with b a polyhedron B(b) := {x ∈ R^{V} : x(V) = b(V), x(A) ≤ b(A) for every A ⊆ V }. When b is fully submodular, B(b) is called a base-polyhedron (0-base-polyhedron in case b(V) = 0). For convenience, the empty set is also considered a base-polyhedron. It follows from the work of J. Edmonds [E70] that a nonempty base-polyhedron uniquely determines its defining fully submodular function. Moreover, the intersection of two base-polyhedra is integral (a version of Edmonds’ polymatroid intersection theorem). Therefore it is important that weaker functions may also define base-polyhedra. For example, L. Lovász [L83] proved that if b is intersecting submodular, then B := B(b) is a base-polyhedron which is non-empty if and only if b(V) ≥ ∑_{i} b(V_{i}) holds for every partition {V_{1}, …, V_{t}} of V. Moreover, the unique fully submodular function defining B is b^{↓}(Z) := min(∑_{i} b(Z_{i}) : {Z_{i}} a partition of Z). S. Fujishige [Fu84] extended this result to crossing submodular functions. He showed that B(b) is a base-polyhedron if b is crossing submodular. Moreover, B := B(b) is non-empty (assuming b(V) = 0) if and only if ∑_{i} b(Z_{i}) ≥ 0 and ∑_{i} b(V − Z_{i}) ≥ 0 for every partition {Z_{1}, …, Z_{t}} of V.

What is the unique fully submodular function defining B, provided B is nonempty? We need the following notion of tree-composition of sets. The treecomposition of the ground-set V is either a partition of V or a co-partition of V (the complements of a partition of V.) Let A be a proper non-empty subset of V. Let {A_{1}, …, A_{k}} (k ≥ 1) be a partition of A and {B_{1}, …, B_{l}} (l ≥ 1) a partition of B := V − A. Let U := {a_{1}, …, a_{k}, b_{1}, …, b_{l}} be a set of new elements and define φ(v) := a_{i} if v ∈ A_{i} and := b_{j} if v ∈ B_{j}. Let F be a directed tree defined on U so that every edge is of form b_{i}a_{j}. For every edge e of the tree, F − e has two components, among which F_{e} denotes the one entered by e. Now a treecomposition of A is a family of subsets of V given in form {φ^{−1}(F_{e}) : e ∈ E(F)}. (A tree-composition has at most |V | − 1 members.)

Theorem 3.1 [F96] Let b be a crossing submodular function for which b(V) = 0 and B := B(b) is non-empty. Then the unique fully submodular function b^{↓} defining B is given by b^{↓}(Z) = min(b(F) : F a tree-composition of Z).

Submodular flows provide a general and powerful framework for combinatorial optimization problems. Let G⃗ = (V, E⃗) be a directed graph. Let f : E⃗ → Z∪{−∞} and g : E⃗ → Z ∪ {+∞} be such that f ≤ g. For a function z : E⃗ → R let ϱ_{z}(A) := ∑(z(e) : e enters A) and δ_{z}(A) := ∑(z(e) : e leaves A). Let λ_{z}(A) := ϱ_{z}(A) − δ_{z}(A). Note that λ_{z} is modular, that is, λ_{z}(A) = ∑_{v∈A}(λ_{z}(v)) and therefore we may consider λ_{z} as a function on V. Furthermore, let b : 2^{V} → Z ∪ {∞} be a crossing submodular function with b(V) = 0. We call z : E⃗ → R a submodular flow (with respect to b) if

λ_{z}(A) ≤ b(A) for every A ⊆ V.  (3.1a)

Submodular flow z is feasible if

f ≤ z ≤ g.  (3.1b)

Submodular flows were introduced and investigated by J. Edmonds and R. Giles [EG77]. Their fundamental result asserts that the linear system (3.1) is totally dual integral, that is, the dual linear programming problem to max(cz : z satisfies (3.1)) has an integer-valued optimal solution for every integer-valued c for which the optimum exists. It follows that the primal polyhedron is also integral (i.e., every face contains an integer point) if b, f, g are integer-valued.

This result implies for example (a min-cost extension of) a theorem of C. Lucchesi and D. Younger asserting that a digraph (with no cut-edge) can be made strongly connected by reorienting at most γ edges if and only if there are no k + 1 disjoint directed cuts. Another direct consequence of the integrality of the submodular flow polyhedron is the (weak form of an) orientation theorem of C. Nash-Williams [N60] asserting that a 2k-edge-connected undirected graph always has a k-edge-connected orientation.

In applications, we often need criteria for feasibility which are easy to handle. An easy relationship between submodular flows and base-polyhedra enables us to formulate such a result. Namely, z is a submodular flow if and only if λ_{z} belongs to the base-polyhedron B(b). The following was proved in [F82]. Where b is fully submodular, there exists an integer-valued feasible submodular flow if and only if ϱ_{f}(A) − δ_{g}(A) ≤ b(A) holds for every A ⊆ V. (Note that, in the special case of b ≡ 0, we obtain Hoffman’s circulation feasibility theorem.) When this result is combined with Theorem 3.1, one obtains the following:

Theorem 3.2 Let b be (A) an intersecting or (B) a crossing submodular function. There exists an integer-valued feasible submodular flow if and only if

ϱ_{f}(A) − δ_{g}(A) ≤ b(A)  (3.2)

holds for every A ⊆ V and for every partition A of A in case (A) and for every tree-composition A of A in case (B).

The partition-type condition for (A) is easier to handle than the one including tree-compositions. Although there are important cases where tree-compositions cannot be avoided, in the next two special cases partition-type conditions turn out to be sufficient. As a generalization of Case (A) in Theorem 3.2, one has the following.

Theorem 3.3 Suppose that b is crossing submodular (with b(V) = 0) which, in addition, satisfies (1.1b) when X ∪ Y = V, X ∩ Y ≠ ∅, and d_{g−f}(X, Y) > 0 hold.

There exists an integer-valued feasible submodular flow if and only if (3.2) holds for every A ⊆ V and for every partition A of A.

The other special case requires both partitions and co-partitions, but not tree-compositions.

Theorem 3.4 Suppose that b is crossing submodular (with b(V) = 0) satisfying

ϱ_{g}(B) − δ_{f}(B) ≥ b(B) for every B ⊂ V.  (3.3)

There exists an integer-valued feasible submodular flow if and only if b(R) ≥ 0 for every partition and co-partition R of V.

Orientations

Connectivity orientation problems are strongly related to submodular flows. Let G = (V, E) be an undirected graph and h : 2^{V} → Z ∪ {−∞} a crossing G-supermodular set-function with h(V) = h(∅) = 0, (that is, h(X) + h(Y) ≤ h(X ∩ Y) + h(X ∪ Y) + d_{G}(X, Y) where d_{G}(X, Y) denotes the number of edges between X − Y and Y − X). The connectivity orientation problem consists of finding an orientation of G so that the in-degree function ϱG⃗ of the resulting digraph G⃗ = (V, E⃗) satisfies:

ϱG⃗(X) ≥ h(X) for every X ⊆ V.  (3.4)

Let us choose an arbitrary orientation G⃗_{r} = (V, E⃗_{r}) of G whose in-degree function is denoted by ϱ_{r} := ϱG⃗_{r}. G⃗_{r} will serve as a reference orientation to specify other orientations G⃗ of G. Define b(X) := ϱ_{r}(X) − h(X). Any other orientation of G will be defined by a vector x : E⃗ → {0, 1} so that x(a) = 0 means that we leave a alone while x(a) = 1 means that we reverse the orientation of a. The revised orientation of G defined this way satisfies (3.4) if and only if ϱ_{r}(X) − ϱ_{x}(X) + δ_{x}(X) ≥ h(X) for every X ⊆ V. Equivalently, ϱ_{x}(X) − δ_{x}(X) ≤ b(X). Clearly, the submodularity of b and the G-supermodularity of h are equivalent and hence there is a one-to-one correspondence between the good orientations of G and the 0 − 1-valued submodular flows. Since h ≥ 0 if and only if (3.3) holds for f ≡ 0, g ≡ 1, Theorem 3.4 implies:

Theorem 3.5 [F80] Suppose that h is non-negative and crossing G-supermodular. There exists an orientation of G satisfying (3.4) if and only if both e_{G}(P) ≥ ∑_{i} h(P_{i}) and e_{G}(P) ≥ ∑_{i} h(V − P_{i}) hold for every partition P= {P_{1}, …, P_{p}} of V. If, in addition, h is symmetric, then it suffices to require d_{G}(X) ≥ 2h(X) for every X ⊆ V.

When h(X) ≡ k for ∅ ⊂ X ⊂ V, we obtain Nash-Williams’ weak orientation theorem. The following generalization, answering Problem O1, is also a consequence of Theorem 3.5: A graph G has an orientation which is k-edge-connected from s and l-edge-connected to s (where k ≥ l) if and only if e_{G}(P) ≥ k|P| + l − k holds for every partition P of V.

Using the same bridge between orientations and submodular flows, one can derive from Theorem 3.3 the following.

Theorem 3.6 Suppose that h is crossing G-supermodular and that h satisfies h(A) + h(B) ≤ h(A ∩ B) + d_{G}(A, B) whenever A ∪ B = V, A ∩ B ≠ ∅ and d_{G}(A, B) > 0. Then G has an orientation satisfying (3.4) if and only if e_{G}(P) ≥ ∑_{i} h(P_{i}) holds for every sub-partition P of V.

This result can be used to derive a (generalization) of a recent orientation theorem of Nash-Williams [N95] on the existence of a strongly connected orientation of a mixed graph that satisfies lower bound requirements on the in-degrees of nodes.

Problem O2 gives rise to crossing G-supermodular functions for which treecompositions are needed. Let A be a tree-composition of a subset A ⊆ V and let j = uv be an edge of G. Let e_{uv}(A) denote the number of sets in A entered by the directed edge with tail v and head u. Let e_{j}(A) := max(e_{uv}(A), e_{uv}(A)) and e_{G}(A) := ∑_{j∈E} e_{j}(A). The quantity e_{j}(A) indicates the (maximally) possible contribution of an edge j = uv to the sum ∑(ϱG⃗(X) : X ∈ A) for any orientation G⃗ of G. Hence e_{G}(A) measures the total of these contributions and therefore, for any orientation G⃗ of G satisfying (3.4), one has ∑_{X∈A} h(X) ≤ ∑_{X∈A} ϱG⃗(X) ≤ e_{G}(A).

Theorem 3.7 Let h be a crossing G-supermodular function. G has an orientation G⃗ satisfying (3.4) if and only if ∑_{X∈A} h(X) ≤ e_{G}(A) holds for every subset A ⊆ V and for every tree-composition A of A.

Let M = (V, E + A⃗) be a mixed graph and let h(X) := k − ϱA⃗(X) for ∅ ⊂ X ⊂ V. By applying Theorem 3.7 to this G and h, one obtains a characterization of mixed graphs having a k-edge-connected orientation, the problem O2.

Rooted connectivity

Let G = (V, E) be a digraph with a special root node s and non-empty terminal set T ⊆ V − s so that no edge of G enters s. Let p be a non-negative, T -intersecting supermodular function. Let g : E → Z_{+} ∪ {∞} be a non-negative upper bound on the edges of G. We assume that ϱ_{g}(Z) ≥ p(Z) for every subset Z ⊆ V where ϱ_{g}(Z) := ∑(g(e) : e ∈ E, e enters Z).

Theorem 3.8(a) The linear system {ϱ_{x}(Z) ≥ p(Z) for every Z ⊂ V, 0 ≤ x ≤ g} is totally dual integral. (b) The polyhedron defined by this system is a submodular flow polyhedron.

For the special case T = V − s, part (a) was proved in [F79] while part (b) in [Schrijver, 1984]. The edge-version of problem S2 could be solved via this special case. It is not difficult to observe that the proofs extend easily to the more general case. The main advantage of this extension is that, beyond handling the edgeversion of problem S2, the node-version can also be settled by using the standard node-splitting technique.

To conclude the section, we remark that there is a polynomial time algorithm to solve minimum cost submodular flow problems hence all the connectivity problems above admit polynomial time solution algorithms.

4. Covering ST -crossing supermodular functions by digraphs

We say that a digraph G = (V, E) covers a set-function p if there are at least p(X) edges entering every subset X ⊆ V. How many edges are needed to cover p?

Theorem 4.1 [F94] Let p be a crossing supermodular function and γ a positive integer. There exists a digraph G = (V, E) of at most γ edges covering p if and only if ∑(p(X) : X ∈ P) ≤ γ and ∑(p(V − X) : X ∈ P) ≤ γ hold for every subpartition P of V.

This result can be extended, as follows. Let S and T be two subsets of a ground-set V. Two subsets X, Y are called ST -independent if X ∩ Y ∩ T = ∅ or S ⊆ X ∪ Y.

Theorem 4.2 [FJ95] Let p : 2^{V} → Z_{+} be an ST -crossing supermodular function and γ a positive integer. There exists a digraph G = (V, E) that covers p, has at most γ edges, and each edge has its tail in S and its head in T if and only if ∑(p(X) : X ∈ P) ≤ γ holds for every family P of pairwise ST -independent subsets of V.

When S = T = V, an ST -independent family consists of pairwise disjoint sets or of pairwise co-disjoint sets. (Two sets are co-disjoint if their complement is disjoint). Hence Theorem 4.1 is indeed a special case of Theorem 4.2. Theorem 4.1 may be applied to solve an extension of the edge-connectivity version of problem A2. Let D = (V, E) be a directed graph and T a subset of nodes. We say that D is k-edge-connected in T if λ(u, v) ≥ k for every pair of nodes u, v ∈ T.

Theorem 4.3 It is possible to make digraph D k-edge-connected in T by adding at most γ new edges connecting elements of T if and only if ∑_{i}(k − ϱ_{D}(X_{i})) ≤ γ and ∑_{i}(k − δ_{D}(X_{i})) ≤ γ holds for every family F = {X_{1}, …, X_{t}} of subsets V for which ∅ ⊂ X_{i} ∩ T ⊂ T and F|T is a sub-partition of T.

We say that D is k-edge-connected from S to T if there are k edge-disjoint paths from every node of S to every node of T. (When S = T we are back at k-edge-connectivity in T.) Theorem 4.2 gives rise to the following solution to problem A3:

Theorem 4.4 A digraph D = (V, E) can be made k-edge-connected from S to T by adding at most γ new edges with tails in S and heads in T if and only if ∑_{j}(k − ϱ(X_{j})) ≤ γ holds for every choice of an (S, T)-independent family of subsets X_{j} ⊆ V where T ∩ X_{j} ≠ ∅, S − X_{j} ≠ ∅ for each X_{j}.

There is a constructive proof of Theorem 4.1 which gives rise to a strongly polynomial algorithm to find an optimal augmentation in Theorem 4.3. The proof of Theorem 4.2 is not constructive and no combinatorial polynomial algorithm is known to construct the optimal augmentation of Theorem 4.4. It is a major open problem of the field to find one.

Another consequence of Theorem 4.2 concerns the node-connectivity version of problem A2. Given a digraph D = (V, E), we say that a pair of disjoint, nonempty subsets X, Y of V is a one-way pair if there is no edges from X to Y. The deficiency p_{def}(X, Y) of a one-way pair is defined by k − |V − (X ∪ Y)|. Two one-way pairs (X, Y) and (A, B) are called independent if X ∩A = ∅ or Y ∩B = ∅.

Theorem 4.5 A digraph D = (V, E) can be made k-node-connected by adding at most γ new edges if and only if ∑(p_{def}(X, Y) : (X, Y) ∈ F) ≤ γ holds for every family F of pairwise independent one-way pairs.

Are these results related to the ones mentioned in the previous section? One fundamental difference is that, while submodular flows are appropriate to handle min-cost problems, here the minimum-cost versions include NP-complete problems. For example, finding a minimum cost strongly connected augmentation of a digraph is NP-complete. However, for node-induced cost functions the nodeconnectivity augmentation problem turns out to be tractable. A node-induced cost of a directed edge uv is defined by c(uv) := c_{t}(u) + c_{h}(v) where c_{t} and c_{h} are two cost-functions on the node set V. The better behaviour of node-induced cost-functions is based on the fact that the in-degree vectors of k-connected augmentations with γ edges span a base-polyhedron.

We conclude this section by briefly remarking that Theorem 4.2 has a surprising consequence in combinatorial geometry; a theorem of E. Győri [Gy84] asserting that every vertically convex rectilinear polygon R (bounded by horizontal and vertical segments) in the plane can be covered by γ rectangles belonging to R if and only if R does not contain more than γ pairwise independent points (where two points are called independent if they cannot be covered by one rectangle (with horizontal and vertical sides).

5. Covering crossing and skew supermodular functions by graphs

Let p be a non-negative, symmetric, crossing supermodular function. An undirected graph is said to cover p if every cut [X, V −X] contains at least p(X) edges. What is the minimum number of edges covering p?

For a partition P of V, the sum ∑(p(X) : X ∈ P)/2 is clearly a lower bound. However, even the best such bound can be strictly smaller than the true minimum: when p(X) ≡ 1 for ∅ ⊂ X ⊂ V and p(∅) = p(V) = 0, the minimum is |V | − 1 while the best partition bound is |V |/2. Hence we need a new parameter, called the dimension of p. A partition F := {V_{1}, …, V_{h}} of V with h ≥ 4 is said to be p-full if p(∪F′) ≥ 1 for every sub-partition F′, ∅ ⊂ F′ ⊂ F, and F has a member V_{l} with p(V_{l}) = 1. We call the maximum size of a p-full partition the dimension of p and denote it by dim(p). It can easily be seen that any graph covering p must have at least dim(p)−1 edges. The content of the next result is that the minimum in question is equal to the larger of the two lower bounds.

Theorem 5.1 [BF96] Let p : 2^{V} → Z_{+} be a symmetric, crossing supermodular function and γ a positive integer. There exists an undirected graph G = (V, E) with at most γ edges covering p if and only if ∑(p(X) : X ∈ P) ≤ 2γ holds for every partition P of V and dim(p) − 1 ≤ γ.

It is an important open problem to extend this theorem to skew-supermodular functions. For even-valued functions p (that is, when p(X) is even for every subset X) this was done by Z. Szigeti. The advantage of even supermodular functions is that their dimension does not play any role. To capture the difference, observe that if p_{1} is identically 1 on non-empty proper sutsets of V, then a tree will be the smallest graph covering p_{1}, that is, the minimum number of edges is n − 1. If p_{2} := 2p_{1}, then we do not need twice as many edges to cover p_{2}. Just one more edge will do as a circuit of n edges cover every cut at least twice.

Theorem 5.2 [Sz95] Let p : 2^{V} → Z_{+} be a symmetric, even-valued, skewsupermodular function and γ a positive integer. There exists a graph G = (V, E) with at most γ edges covering p if and only if ∑(p(X) : X ∈ P) ≤ 2γ holds for every partition P of V.

As a consequence of Theorem 5.1 we exhibit a result concerning hypergraph connectivity augmentation. Given a hypergraph H′ = (V, A′), a subset ∅ ⊂ C ⊂ V is called a component of H′ if d_{H′}(C) = 0 and d_{H′}(X) > 0 for every ∅ ⊂ X ⊂ C. (d_{H′}(X) denotes the number of hyperedges of H′ intersecting both X and V −X.) For a subset T ⊂ V, we let c_{T} (H′) denote the number of components of H′ having a non-empty intersection with T. H′ is said to be k-edge-connected in T if d_{H′}(X) ≥ k for every subset ∅ ⊂ X ⊂ V separating T. When T = V we say that H′ is k-edge-connected.

Theorem 5.3 Let H = (V, A) a hypergraph, T a specified subset of V, and γ a positive integer. H = (V, A) can be made k-edge-connected in T by adding at most γ new graph-edges if and only if ∑(k − d_{H}(X) : X ∈ P) ≤ 2γ for every sub-partition P of V separating T and c_{T} (H′) − 1 ≤ γ for every hypergraph H′ = (V, A′) arising from H by leaving out k − 1 hyperedges. If these conditions hold, the new edges can be chosen so as to connect elements of T.

This result is a solution to problem A4. It extends an earlier theorem of J. Bang-Jensen and B. Jackson [BJ95] where T = V, which, in turn, generalizes an even earlier result of T. Watanabe and A. Nakamura [WN87] when the starting hypergraph H is itself a graph. The latter result was generalized in another direction in [F92] where, instead of global k-edge-connectivity, specified demands r(u, v) were required for the augmented local edge-connectivities between every pair of nodes u and v. Since such a problem gives rise to skew-supermodular functions, Theorem 5.1 cannot be applied. However, if half-capacity edges are also allowed in the augmentation, then Theorem 5.2 can be applied. That is, one can find a graph G of minimum number of edges so that adding the edges of G with half-capacity to the starting hypergraph, the local edge-connectivities of the increased hypergraph attain a prescribed value r(u, v) for every pair {u, v} of nodes.

References

[BJ95] J. Bang-Jensen and B. Jackson, Augmenting hypergraphs by edges of size two, Mathematical Programming, Ser B., to appear.

[BF96] A. Benczúr and A. Frank, Covering symmetric supermodular functions by graphs, Mathematical Programming, Ser B., to appear.

[E70] J. Edmonds, Submodular functions, matroids, and certain polyhedra, in: Combinatorial Structures and their applications (R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds.) Gordon and Breach, New York, 69-87.

[E79] J. Edmonds, Matroid intersection, in: ”Discrete Optimization”, Annals of Discrete Mathematics, Vol. 4 (1979) North-Holland.

[EG77] J. Edmonds and R. Giles, A min-max relation for submodular functions on graphs, Annals of Discrete Mathematics 1, (1977), 185-204.

[ET76] K.P. Eswaran and R.E. Tarjan, Augmentation problems, SIAM J. Computing, Vol. 5, No. 4, December 1976, 653-665.

[F79] A. Frank, Kernel systems of directed graphs, Acta Scientiarum Mathematicarum (Szeged) 41, 1-2 (1979) 63-76.

[F80] A. Frank, On the orientation of graphs, J. Combinatorial Theory, Ser B. , Vol. 28, No. 3 (1980) 251-261.

[F81] A. Frank, How to make a digraph strongly connected, Combinatorica 1, No. 2 (1981) 145-153.

[F82] A. Frank, An algorithm for submodular functions on graphs, Annals of Discrete Mathematics 16 (1982) 97-120.

[F92] A. Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM J. on Discrete Mathematics, (1992 February), Vol 5, No 1. pp. 22-53.

[F94] A. Frank, Connectivity augmentation problems in network design, in: Mathematical Programming: State of the Art 1994, eds., J.R. Birge and K.G. Murty), The University of Michigan, pp. 34-63.

[F96] A. Frank, Orientations of Graphs and Submodular Flows, Congressus Numerantium, 113 (1996) (A.J.W. Hilton, ed.) pp. 111-142.

[FJ95] A. Frank and T. Jordán, Minimal edge-coverings of pairs of sets, J. Combinatorial Theory, Ser. B. Vol. 65, No. 1 (1995, September) pp. 73-110.

[Fu84] S. Fujishige, Structures of polyhedra determined by submodular functions on crossing families, Math Programming, 29 (1984) 125-141.

[Gy84] E. Győri, A minimax theorem on intervals, J. Combinatorial Theory, Ser. B 37 (1984) 1-9.

[L83] L. Lovász, Submodular functions and convexity, in: Mathematical programming- The state of the art, (eds. A. Bachem, M. Grötschel and B. Korte) Springer 1983, 235-257.

[LY78] C.L. Lucchesi and D.H. Younger, A minimax relation for directed graphs, J. London Math. Soc. (2) 17 (1978) 369-374.

[M96] K. Murota, Convexity and Steinitz’s exchange property, Advances in Mathematics, Vol.124, No.2, (1996), 272-310.

[N60] C.St.J.A. Nash-Williams, On orientations, connectivity and odd vertex pairings in finite graphs, Canad. J. Math. 12 (1960) 555-567.

[N95] C.St.J.A. Nash-Williams, Strongly connected mixed graphs and connected detachments of graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 19 (1995) pp. 33-47.

[S84] A. Schrijver, Total dual integrality from directed graphs, crossing families and sub- and supermodular functions, in: Progress in Combinatorial Optimization,(ed. W. R. Pulleyblank) Academic Press (1984) 315-361.

[Sz96] Z. Szigeti, Hypergraph connectivity augmentation, Mathematical Programming, Ser B., to appear.

[WN87] T. Watanabe and A. Nakamura, Edge-connectivity augmentation problems, Computer and System Sciences, Vol 35, No.1, (1987) 96-144.

Dept. of Operations Research Eötvös University Múzeum krt. 6-8, Budapest Hungary, H-1088

frank@cs.elte.hu

Ericsson Traffic Laboratory Laborc u.1, Budapest Hungary, H-1037