# Frank-Jordán theorem

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

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

[math]p(K)+p(L)\le p(K\wedge L)+p(K\vee L)[/math]

holds. An arc *xy* **covers** the set pair *K*, if [math]x\in K^-[/math],
[math]y\in K^+[/math]. 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
[math]K\in\mathcal{P}[/math].

**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 [math]\sum_{K\in \mathcal{F}} p(K)[/math], where [math]\mathcal{F}\subseteq \mathcal{P}[/math] 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

- finding maximum [math]K_{t,t}[/math]-free
*t*-matchings in bipartite graphs, - Győri's Theorem on generating a system of intervals
^{[3]}, - a generalization of Győri's theorem by Soto and Telha
^{[4]}, - directed node-connectivity augmentation preserving simplicity
^{[5]}.

## References

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