We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph @math with @math , @math and @math the best known algorithm to compute a global minimum cut in @math runs in time @math for the uncapacitated case and in @math time for the capacitated case. We show the following new results. 1. Given an uncapacitated hypergraph @math and an integer @math we describe an algorithm that runs in @math time to find a subhypergraph @math with sum of degrees @math that preserves all edge-connectivities up to @math (a @math -sparsifier). This generalizes the corresponding result of Nagamochi and Ibaraki from graphs to hypergraphs. Using this sparsification we obtain an @math time algorithm for computing a global minimum cut of @math where @math is the minimum cut value. 2. We generalize Matula's argument for graphs to hypergraphs and obtain a @math -approximation to the global minimum cut in a capacitated hypergraph in @math time. 3. We show that a hypercactus representation of all the global minimum cuts of a capacitated hypergraph can be computed in @math time and @math space. We utilize vertex ordering based ideas to obtain our results. Unlike graphs we observe that there are several different orderings for hypergraphs which yield different insights.
In a recent work Kogan and Krauthgamer @cite_30 examined the properties of random contraction algorithm of Karger when applied to hypergraphs. They showed that if the rank of the hypergraph is @math then the number of @math -mincuts for @math is at most @math which is a substantial improvement over a naive analysis that would give a bound of @math . The exponential dependence on @math is necessary. They also showed cut-sparsification results ala Benczur and Karger's result for graphs @cite_22 . In particular, given a @math -vertex capacitated hypergraph @math of rank @math they show that there is a capacitated hypergraph @math with @math edges such that every cut capacity in @math is preserved to within a @math factor in @math . @cite_33 considered parametric mincuts in graphs and hypergraphs of fixed rank and obtained polynomial bounds on the number of distinct mincuts.
@cite_30 @cite_22 @cite_33
1978676170 1543491698 2132147722
Sketching and streaming algorithms are in the forefront of current research directions for cut problems in graphs. In the streaming model, we show that (1--e)-approximation for Max-Cut must use n 1-O(e) space; moreover, beating 4 5-approximation requires polynomial space. For the sketching model, we show that every r-uniform hypergraph admits a (1+ e)-cut-sparsifier (i.e., a weighted subhypergraph that approximately preserves all the cuts) with O(e-2n(r+log n)) edges. We also make first steps towards sketching general CSPs (Constraint Satisfaction Problems). We describe random sampling techniques for approximately solving problems that involve cuts and flows in graphs. We give a near-linear-time randomized combinatorial construction that transforms any graph on @math vertices into an @math -edge graph on the same vertices whose cuts have approximately the same value as the original graph's. In this new graph, for example, we can run the @math -time maximum flow algorithm of Goldberg and Rao to find an @math - @math minimum cut in @math time. This corresponds to a @math -times minimum @math - @math cut in the original graph. A related approach leads to a randomized divide-and-conquer algorithm producing an approximately maximum flow in @math time. Our algorithm can also be used to improve the running time of sparsest cut approximation algorithms from @math to @math and to accelerate several other recent cut and flow algorithms. Our algorithms are based on a general theorem analyzing the concent... We consider multiobjective and parametric versions of the global minimum cut problem in undirected graphs and bounded-rank hypergraphs with multiple edge cost functions. For a fixed number of edge cost functions, we show that the total number of supported non-dominated (SND) cuts is bounded by a polynomial in the numbers of nodes and edges, i.e., is strongly polynomial. This bound also applies to the combinatorial facet complexity of the problem, i.e., the maximum number of facets (linear pieces) of the parametric curve for the parametrized (linear combination) objective, over the set of all parameter vectors such that the parametrized edge costs are nonnegative and the parametrized cut costs are positive. We sharpen this bound in the case of two objectives (the bicriteria problem), for which we also derive a strongly polynomial upper bound on the total number of non-dominated (Pareto optimal) cuts. In particular, the bicriteria global minimum cut problem in an n-node graph admits @math O(n3logn) SND cuts and @math O(n5logn) Pareto optimal cuts. These results significantly improve on earlier graph cut results by Mulmuley (SIAM J Comput 28(4):1460---1509, 1999) and Armon and Zwick (Algorithmica 46(1):15---26, 2006). They also imply that the parametric curve and all SND cuts, and, for the bicriteria problems, all Pareto optimal cuts, can be computed in strongly polynomial time when the number of objectives is fixed.