Chao Xu (Illinois Computer Science) Small $k$certificate in hypergraphs and representing all mincuts Abstract: For a hypergraph $H=(V,E)$, a hypergraph $H'=(V,E')$ is called a $k$certificate of $H$ if it preserves all the cut values up to $k$. That is, $\delta_{H'}(S) \geq \min(\delta_H(S),k)$ for all $S\subset V$. Nagamochi and Ibaraki showed there exists a $k$certificate with $O(kn)$ edges for graphs, where $n$ is the number of vertices. A similar argument shows this extends to hypergraphs. We show a stronger result of hypergraphs: there is a $k$certificate with size (sum of degrees) $O(kn)$, and it can be obtained by removing vertices from edges in $H$. We also devise an algorithm that finds a representation of all mincuts in a hypergraph in the same running time as finding a single mincut. The algorithm uses Cunningham's decomposition framework, and different generalizations of maximum adjacency ordering. This is joint work with Chandra Chekuri. 
