Covering a crossing supermodular function with pairwise non-parallel arcs

From Egres Open
Jump to: navigation, search

Given a crossing supermodular function [math]p:2^V\to \mathbb{Z}[/math] satisfying [math]p(\emptyset)=p(V)=0[/math], what is the minimum number of pairwise non-parallel arcs (i.e. only one copy of the arc uv is allowed for any pair [math]u,v\in V[/math], but opposite pairs are allowed) covering p, where a digraph D=(V,A) is said to cover p if [math]\varrho_D(X)\ge p(X)[/math] holds for every [math]X\subseteq V[/math]?


If we also allow parallel arcs then the above question is answered by the following theorem due to Frank [1]:

Theorem: A crossing supermodular function [math]p:2^V\to \mathbb{Z}[/math] satisfying [math]p(\emptyset)=p(V)=0[/math] can be covered by [math]\gamma[/math] arcs if and only if [math]\sum_{i=1}^t p(V_i)\le \gamma[/math] and [math]\sum_{i=1}^t p(V-V_i)\le \gamma[/math] holds for every partition [math]V_1,V_2,\dots,V_t[/math] of V.


  1. A. Frank, Connectivity augmentation problems in network design, author link