Frank-Jordán theorem

Given two (not necessarly disjoint) sets S and T, let $\mathcal{P}$ denote the set of set pairs of the form $K=(K^-,K^+)$ for $\emptyset\neq K^-\subseteq S$, $\emptyset\neq K^+\subseteq T$. We say that the set pairs K and L are independent if $K^-\cap L^-=\emptyset$ or $K^+\cap L^+=\emptyset$. For two non-independent set pairs K and L let us define the two set pairs $K\wedge L=(K^-\cap L^-,K^+\cup L^+)$ and $K\vee L=(K^-\cup L^-,K^+\cap L^+)$.

A function $p:\mathcal{P}\rightarrow \mathbb{Z}_+$ is called positively crossing supermodular, if for any non-independent set pairs K and L with $p(K),p(L)\gt0$,

$p(K)+p(L)\le p(K\wedge L)+p(K\vee L)$

holds. An arc xy covers the set pair K, if $x\in K^-$, $y\in K^+$. An edge set F consiting of edges from S to T covers the function p if there are at least p(K) arcs in F covering K for each $K\in\mathcal{P}$.

Theorem (Frank and Jordán [1], 1995) Given a positively crossing supermodular function p, the minimum number of arcs covering p equals the maximum value of $\sum_{K\in \mathcal{F}} p(K)$, where $\mathcal{F}\subseteq \mathcal{P}$ is a set of pairwise independent set-pairs. A minimum arc set covering p can be found in polynomial time.

Note that the polynomial-time algorithm mentioned in the theorem relies on the ellipsoid method and does not find the optimal family of pairwise independent set-pairs. A combinatorial, pseudo-polynomial algorithm was given by Végh and Benczúr [2].

Applications

The most powerful application is directed node-connectivity augmentation: given a digraph D=(V,A) and a connectivity target k, it enables finding a minimum cardinality arc set F so that D+F is k-node-connected. The simpler problem of directed edge-connectivity augmentation can also be deduced from this theorem, along with its generalization, S-T edge-connectivity augmentation.

Further applications include

References

1. A. Frank, T. Jordán, Minimal edge-coverings of pairs of sets, DOI link, author link
2. L.A. Végh, A.A. Benczúr, Primal-dual approach for directed vertex connectivity augmentation and generalizations, DOI link, author link
3. E. Győri, A minimax theorem on intervals, DOI link
4. J.A. Soto, C. Telha, Independent sets and hitting sets of bicolored rectangular families, arXiv link
5. K Bérczi, A. Frank, Supermodularity in unweighted graph optimization III: Highly connected digraphs, EGRES Technical Report no. 2016-11