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 , 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 .

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 $$K_{t,t}$$ -free t-matchings in bipartite graphs,
• Győri's Theorem on generating a system of intervals ,
• a generalization of Győri's theorem by Soto and Telha ,
• directed node-connectivity augmentation preserving simplicity .