Sub- and supermodular functions

Problems in this category

• Characterizing integral g-polymatroids
• Covering a crossing supermodular function with graph edges
• Covering a crossing supermodular function with pairwise non-parallel arcs
• Covering a symmetric crossing supermodular function with hyperedges of prescribed size
• Edge-covering number of 2-polymatroids
• Maximizing a skew-supermodular function
• Minimum k-way cut in a hypergraph
• Opposite vertices of base polyhedra
• Skew-supermodular colouring with prescribed class-sizes
• Skew-supermodular colouring with two class sizes
• Skew-supermodular list colouring

Introduction

Submodular and supermodular functions play an important role in combinatorial optimization. Using the terminology of Frank , we will say that a function is semimodular if it is either submodular or supermodular. We usually consider the function f to be available through a function evaluation oracle, which can tell us the function value f(X) for a subset X of the ground set V. Very often we encounter functions that only satisfy some weaker form of sub- or supermodularity. Examples include intersecting-, crossing- and skew- sub/supermodular functions.

Generalized polymatroids

Generalized polymatroids (or g-polymatroids, for short) were introduced by Frank to unify the treatment of certain polyhedra related to semimodular functions. A very recent result of J. Pap gives a new characterization of g-polymatroids (conjectured by Pritchard: more results in ).

The following question of András Frank is motivated by the submodular function minimizing algorithms. The bottleneck in these algorithms is the Charateodory subroutine: given a convex combination of some elements of [math]\mathbb{R}^n[/math], find at most n+1 of these elements and coefficients for these that define the same convex combination. The current submodular function minimisation algorithms use this subroutine many times. If we could find positive answers to the following questions then we could speed up these algorithms (more details and related questions).

Is it true that if all vertices of a base polyhedron B are in [math]\{0,1,-1\}^n[/math] and [math]0 \in B[/math], then B has a vertex v such that -v is also a vertex?

Submodular function minimization

Submodular function minimization was first shown to be solvable in polynomial time by the celebrated paper of Grötschel, Lovász and Schrijver , but they used the ellipsoid method. For a symmetric function f, a simple (polynomial time) combinatorial algorithm was given by Queyranne . The first combinatorial algorithm for the general (i.e. non-symmetric) problem was given independently by Iwata, Fleischer and Fujishige and Schrijver . Currently the best known algorithm (in terms of running time) is due to Orlin . The story probably does not end here, as suggested by the survey paper .

It is open if polynomial time minimization is possible for functions that are not submodular, but either satisfy the relaxed skew-submodular property, or the posimodular property (which is related to submodularity). The problems are formulated here (in maximization form).

Given a skew-supermodular function [math]p:2^V\to \mathbb{Z}[/math] with a function evaluation oracle, is it possible to find a set [math]X\subseteq V[/math] in polynomial time such that [math]p(X)=\max\{p(Y): Y\subseteq V\}[/math]? The problem is open even if [math]p[/math] is a crossing negamodular function.

Submodular partitioning problems

There are two versions of this problem. In both versions we are given a submodular function f over the ground set V, and a positive integer k, and we want to find a partition of V into k nonempty parts [math]A_1,A_2,\dots,A_k[/math] minimizing the sum [math] \sum_{i=1}^k f(A_i)[/math]. In one version we are also given terminals [math]s_1,s_2,\dots,s_k\in V[/math] and we require [math]s_i\in A_i[/math] to hold for every i: let us call this the submodular multiway partition problem. In the other version there are no terminals, we only require [math] A_i[/math] to be nonempty for every i. This is the k-way partition problem. An example is when f is the cut function of a graph or hypergraph: in that case f is also symmetric.

Submodular multiway partition

The submodular multiway partition problem is already NP-hard if f is the cut function of a graph and k=3. In a recent paper Chekuri and Ene gave a (2-1/k)-approximation algorithm for the general submodular multiway partition problem, and an (1,5-1/k)-approximation algorithm for the submodular multiway partition problem with a symmetric function f. However, their algorithm uses the ellipsoid method, so an open question is to find a polynomial-time algorithm that does not rely on it.

Submodular k-way partition

The problem is NP-complete if k is part of the input. If k is fixed and f is the cut function of a graph, then the problem was shown to be polynomially solvable by Goldschmidt and Hochbaum . In contrast, the general submodular problem is known to be in P only for [math]k \leq 3[/math] , and the symmetric submodular case is solved for [math]k \leq 4[/math] (note that for symmetric f, the k=2 case it equivalent to the minimization problem for f). The following special case is also open (more details).

Can we find a minimum k-way cut in a capacitated hypergraph in polynomial time, if k is fixed?

(Note that this problem cannot be formulated with a symmetric function: if we take f to be the cut function of the hypergraph, then we would count a hyperedge several times. On the other hand, it can be formulated with a non-symmetric function f: orient the hypergraph by designating one arbitrary head for each hyperedge, and let f be the in-degree function.)

Covering problems

The covering problems mentioned here are all edge-connectivity augmentation problems, so see more details about them in the page on edge-connectivity augmentation.

Skew-supermodular colouring problems

The problems skew-supermodular colouring with prescribed class-sizes and skew-supermodular list colouring are both generalizations of the skew-supermodular variant of Schrijver's Supermodular colouring theorem. This theorem states that if [math]p_1[/math] and [math]p_2[/math] are two integer skew-supermodular set functions on ground set S, both with maximal value k, that are also subcardinal (i.e. [math]p_i(X)\le |X|[/math] for any [math]X\subseteq S[/math] and i=1,2), then we can colour the set S with k colours such that every subset X contains at least [math]\max\{p_1(X), p_2(X)\}[/math] different colours. In the first problem we want to prescribe the sizes of the colour classes. On the other hand in the skew-supermodular list colouring problem we want to extend this theorem in a list colouring sense: every node [math] v\in S[/math] has a list containing at least k colours, and we are only allowed to choose a colour for v from this list.