TY - GEN

T1 - Trees for vertex cuts, hypergraph cuts and minimum hypergraph bisection

AU - Räcke, Harald

AU - Schwartz, Roy

AU - Stotz, Richard

N1 - Publisher Copyright:
© 2018 Copyright held by the owner/author(s).

PY - 2018/7/11

Y1 - 2018/7/11

N2 - In the Minimum Hypergraph Bisection problem, the vertex set of a hypergraph has to be partitioned into two parts of equal size so that the number of hyperedges intersecting both parts is minimized. This problem is a natural generalization of the well-studied Minimum Bisection problem in graphs. In this paper we present a sharp distinction between Minimum Bisection in hypergraphs and graphs. Whereas it is well-known that all bi-criteria approximation algorithms for Minimum Bisection in graphs can be extended to hypergraphs with the exact same guarantees, in this paper we prove that this is not the case when considering true (i.e., non bi-criteria) approximation algorithms. Specifically, we show that Minimum Bisection in Hypergraphs admits an Õ (n) approximation algorithm (and highlight several special cases where a better approximation ratio is possible). Additionally, we show that the problem is at least as hard as the Densest k-Subgraph problem. Assuming the Dense vs. Random Conjecture [4], no approximation ratio better than O (n1/4−ε ) is possible. In particular, Minimum Hypergraph Bisection is much harder to approximate than Minimum Bisection in graphs, for which a logarithmic approximation algorithms exist [17]. We also consider the problem of constructing trees that are cut sparsifiers for hypergraph and vertex cuts. While similar trees lie at the heart of powerful algorithms for Minimum Bisection in graphs, we prove that this is not the case for hypergraphs. We give upper and lower bounds to the quality of such trees. Our bounds show that this tree cut sparsifying approach cannot improve the general approximation ratio of Minimum Hypergraph Bisection and Minimum Vertex Bisection.

AB - In the Minimum Hypergraph Bisection problem, the vertex set of a hypergraph has to be partitioned into two parts of equal size so that the number of hyperedges intersecting both parts is minimized. This problem is a natural generalization of the well-studied Minimum Bisection problem in graphs. In this paper we present a sharp distinction between Minimum Bisection in hypergraphs and graphs. Whereas it is well-known that all bi-criteria approximation algorithms for Minimum Bisection in graphs can be extended to hypergraphs with the exact same guarantees, in this paper we prove that this is not the case when considering true (i.e., non bi-criteria) approximation algorithms. Specifically, we show that Minimum Bisection in Hypergraphs admits an Õ (n) approximation algorithm (and highlight several special cases where a better approximation ratio is possible). Additionally, we show that the problem is at least as hard as the Densest k-Subgraph problem. Assuming the Dense vs. Random Conjecture [4], no approximation ratio better than O (n1/4−ε ) is possible. In particular, Minimum Hypergraph Bisection is much harder to approximate than Minimum Bisection in graphs, for which a logarithmic approximation algorithms exist [17]. We also consider the problem of constructing trees that are cut sparsifiers for hypergraph and vertex cuts. While similar trees lie at the heart of powerful algorithms for Minimum Bisection in graphs, we prove that this is not the case for hypergraphs. We give upper and lower bounds to the quality of such trees. Our bounds show that this tree cut sparsifying approach cannot improve the general approximation ratio of Minimum Hypergraph Bisection and Minimum Vertex Bisection.

UR - http://www.scopus.com/inward/record.url?scp=85051136575&partnerID=8YFLogxK

U2 - 10.1145/3210377.3210398

DO - 10.1145/3210377.3210398

M3 - Conference contribution

AN - SCOPUS:85051136575

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 23

EP - 32

BT - SPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

T2 - 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018

Y2 - 16 July 2018 through 18 July 2018

ER -