# In Search of the Densest Subgraph
## 4 Some Related Results and Open Problems
### Min-Max Theorems  
There are many results in combinatorial optimization, as well as related areas, that are referred to as _min-max theorems_, also called _min-max characterization_. The general form of such theorems is outlined below. Let \(f(x)\) be a polynomial-time computable function that maps a bit-string \(x\) into a rational number. The optimization problem is this: What is the maximum value of \(f(x)\) over \(n\)-bit strings \(x\)? We say that such a problem has a _min-max characterization_, if there is another polynomial-time computable function \(g\), such that  
\[\max_{x}f(x)=\min_{y}g(y)\]  
holds. Here, \(x\) runs over all \(n\)-bit strings, and \(y\) runs over all \(m\)-bit strings; \(n\) and \(m\) may be different, but they are polynomially related. Numerous natural and important optimization problems have such a min-max characterization (see, e.g., [PERSON] [39]). Let us list a few examples, showing the theorems on which the characterizations are based in parenthesis: Linear Programming (LP Duality Theorem), Maximum Flow (Max Flow Min Cut Theorem), Maximum Bipartite Matching (Konig-Hall Theorem), Maximum Non-Bipartite Matching (Tutte's Theorem and Tutte-Berge formula), Maximum Disjoint Arborescences in directed graph (Edmond's Disjoint Branching Theorem), Maximum Spanning Tree Packing in undirected graph (Tutte's Tree Packing Theorem), Minimum Covering by Forests (Nash-Williams Theorem), Maximum Directed Cut Packing (Lucchesi-Younger Theorem), Max 2-Matroid Intersection (Matroid Intersection Theorem), Maximum Disjoint Paths (Menger's Theorem), Max Antichain in Partially Ordered Set (Dilworth's Theorem), and a number of others. The significance of min-max theorems is two-fold:  
* They provide non-trivial insight into the problem structure, which is often helpful in developing algorithms. * They offer a way to _certify_ the optimality of a solution. For example, if someone provides us a network flow in a large network, and claims that it is a maximum flow, how can this be certified without re-running the entire algorithm? We can easily check that the flow is _feasible_, by simply checking that it satisfies all the constraints. How do we make sure it is indeed _optimal_, i.e., there is no flow with larger value? If we are also given a cut (a dual solution) with capacity equal to the flow value, then it indeed certifies the optimality, since no more flow can get through than what the bottleneck allows. The fact that such an optimality certificate always exists for this problem is not trivial, it follows from the Max Flow Min Cut Theorem. Now, we turn to the question: Are there such min-max characterizations for some of the densest subgraph problems we have considered? We show three examples below. [PERSON] and [PERSON] (2017) proved a characterization for the density of the densest subgraph, with respect to the edge density (see Section 3.1.1):  
**Theorem 13** (Pseudo-arboricity): _Let us call a graph a pseudo-forest if every connected component in it has at most one cycle. Let \(G\) be a graph, and let \(\kappa(G)\) denote the minimum number \(k\), such that there are \(k\) edge-disjoint pseudo-forests that together cover all edges of \(G\). This quantity is called the pseudo-arboricity of \(G\). Then, the following holds:_  
\[\kappa(G)=\left\lceil\max_{S}\frac{|E(S)|}{|V(S)|}\right\rceil,\]  
_where \(\lceil.\rceil\) denotes the upper integer part of any number._  
For example, if we want to convince somebody that a large graph has a subgraph with edge density 32.6, then we can simply exhibit such a subgraph (found by one of the known algorithms). However, how can we certify that such a subgraph does _not_ exist? This can be done by exhibiting a covering of the graph edges with at most 32 disjoint pseudo-forests. It proves that \(\kappa(G)\leq 32\), and by the above theorem it implies that \(G\) cannot contain a subgraph with edge density greater than 32.