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
