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.
Hypergraph cuts have also been studied in the context of @math -way cuts. Here the goal is to partition the vertex set @math into @math non-empty sets so as to minimize the number of hyperedges crossing the partition. For @math a polynomial time algorithm is known @cite_5 while the complexity is unknown for fixed @math . The problem is NP-Complete when @math is part of the input even for graphs @cite_28 . Fukunaga @cite_36 obtained a polynomial-time algorithm for @math -way cut when @math and the rank @math are fixed; this generalizes the result the polynomial-time algorithm for graphs @cite_28 @cite_6 . Karger's contraction algorithm also yields a randomized algorithm when @math and the rank @math are fixed. When @math is part of the input, @math -way cut in graphs admits a @math -approximation @cite_1 . This immediately yields a @math -approximation for hypergraphs. If @math is not fixed and @math is part of the input, it was recently shown @cite_10 that the approximability of the @math -way cut problem is related to that of the @math -densest subgraph problem.
@cite_28 @cite_36 @cite_1 @cite_6 @cite_5 @cite_10
1961231572 1981202693 2067062892 1799262171
We study the approximability of multiway partitioning problems, examples of which include Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate these problems from the point of view of two possible generalizations: as Min-CSPs, and as Submodular Multiway Partition problems. These two generalizations lead to two natural relaxations that we call respectively the Local Distribution LP, and the Lovasz relaxation. The Local Distribution LP is generally stronger than the Lovasz relaxation, but applicable only to Min-CSP with predicates of constant size. The relaxations coincide in some cases such as Multiway Cut where they are both equivalent to the CKR relaxation. We show that the Lovasz relaxation gives a (2--2 k)-approximation for Submodular Multiway Partition with k terminals, improving a recent 2-approximation [2]. We prove that this factor is optimal in two senses: (1) A (2--2 k -- e)-approximation for Submodular Multiway Partition with k terminals would require exponentially many value queries (in the oracle model), or imply NP = RP (for certain explicit submodular functions). (2) For Hypergraph Multiway Cut and Node-weighted Multiway Cut with k terminals, both special cases of Submodular Multiway Partition, we prove that a (2--2 k -- e)-approximation is NP-hard, assuming the Unique Games Conjecture. Both our hardness results are more general: (1) We show that the notion of symmetry gap, previously used for submodular maximization problems [19, 6], also implies hardness results for submodular minimization problems. (2) Assuming the Unique Games Conjecture, we show that the Local Distribution LP gives an optimal approximation for every Min-CSP that includes the Not-Equal predicate. Finally, we connect the two hardness techniques by proving that the integrality gap of the Local Distribution LP coincides with the symmetry gap of the multilinear relaxation (for a related instance). This shows that the appearance of the same hardness threshold for a Min-CSP and the related submodular minimization problem is not a coincidence. The minimum 3-way cut problem in an edge-weighted hypergraph is to find a partition of the vertices into 3 nonempty sets minimizing the total weight of hyperedges that have at least two endpoints in two different sets. In this paper we show that a minimum 3-way cut in hypergraphs can be found by using O(n^3) hypergraph minimum (s,t) cut computations, where n is the number of vertices in the hypergraph. Our simple algorithm is the first polynomial-time algorithm for finding minimum 3-way cuts in hypergraphs. Abstract The hypergraph k -cut problem is the problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into at least k connected components. We present an algorithm for this problem, that runs in strongly polynomial time if both k and the maximum size of the hyperedges are constants. Our algorithm extends the algorithm proposed by Thorup (2008) for computing minimum k -cuts of graphs from greedy packings of spanning trees. Given two graphs @math and @math , the Subgraph Isomorphism problem asks if @math is isomorphic to a subgraph of @math . While NP-hard in general, algorithms exist for various parameterized versions of the problem: for example, the problem can be solved (1) in time @math using the color-coding technique of Alon, Yuster, and Zwick; (2) in time @math using Courcelle's Theorem; (3) in time @math using a result on first-order model checking by Frick and Grohe; or (4) in time @math for connected @math using the algorithm of Matou s ek and Thomas. Already this small sample of results shows that the way an algorithm can depend on the parameters is highly nontrivial and subtle. We develop a framework involving 10 relevant parameters for each of @math and @math (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time [ f_1(p_1,p_2,..., p_ ) n^ f_2(p_ +1 ,..., p_k) ] exist, where each of @math is one of the 10 parameters depending only on @math or @math . We show that all the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs); some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of @math gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when @math is a bounded-degree tree of constant pathwidth and @math is a planar graph of bounded pathwidth.