论文标题
计数和枚举最佳剪切套件的hypergraph $ k $ - 分区问题固定$ k $
Counting and enumerating optimum cut sets for hypergraph $k$-partitioning problems for fixed $k$
论文作者
论文摘要
我们考虑了两个HyperGraph $ K $ - 分区问题的最佳解决方案的问题 - 即HyperGraph- $ K $ -CUT和Minmax-Hypergraph- $ K $ - 分区。 HyperGraph $ K $ - 分区问题的输入是HyperGraph $ G =（V，E）$，具有正式成本，以及固定的正整数$ K $。目的是将$ v $的分区找到$ k $ nonepty parts $（v_1，v_2，\ ldots，v_k）$（称为$ k $ - 分区） - 以最大程度地减少感兴趣的目标。 1。如果感兴趣的目标是零件的最大切割值，则该问题称为Minmax-Hypergraph- $ k $ - 分区。如果是Minmax-Hypergraph-$ k $ - 分区的最佳$ K $ - 分区，那么Hyperedges的子集是Minmax-$ k $ -cut-cut-set。 2。如果感兴趣的目标是越过$ K $分区的Hyperedges的总成本，则该问题被称为HyperGraph- $ k $ -cut。 HypereDges的子集是最小$ K $ -CUT，如果它是越过最佳$ k $ - hypergraph- $ k $ cut的Hyperedges的子集。 我们对Minmax- $ K $ cut-sets和多项式时间算法的第一个多项式限制，以对每个固定的$ k $列举所有这些算法。 Our technique is strong enough to also enable an $n^{O(k)}p$-time deterministic algorithm to enumerate all min-$k$-cut-sets in hypergraphs, thus improving on the previously known $n^{O(k^2)}p$-time deterministic algorithm, where $n$ is the number of vertices and $p$ is the size of the hypergraph.对我们的枚举方法的正确性分析取决于结构性结果，该结果是对超图 - $ k $ cut和minmax-hypergraph- $ k $分区的已知结构结果的强烈而统一的概括。我们认为，我们的结构结果可能对超图理论（和图）具有独立的兴趣。
We consider the problem of enumerating optimal solutions for two hypergraph $k$-partitioning problems -- namely, Hypergraph-$k$-Cut and Minmax-Hypergraph-$k$-Partition. The input in hypergraph $k$-partitioning problems is a hypergraph $G=(V, E)$ with positive hyperedge costs along with a fixed positive integer $k$. The goal is to find a partition of $V$ into $k$ non-empty parts $(V_1, V_2, \ldots, V_k)$ -- known as a $k$-partition -- so as to minimize an objective of interest. 1. If the objective of interest is the maximum cut value of the parts, then the problem is known as Minmax-Hypergraph-$k$-Partition. A subset of hyperedges is a minmax-$k$-cut-set if it is the subset of hyperedges crossing an optimum $k$-partition for Minmax-Hypergraph-$k$-Partition. 2. If the objective of interest is the total cost of hyperedges crossing the $k$-partition, then the problem is known as Hypergraph-$k$-Cut. A subset of hyperedges is a min-$k$-cut-set if it is the subset of hyperedges crossing an optimum $k$-partition for Hypergraph-$k$-Cut. We give the first polynomial bound on the number of minmax-$k$-cut-sets and a polynomial-time algorithm to enumerate all of them in hypergraphs for every fixed $k$. Our technique is strong enough to also enable an $n^{O(k)}p$-time deterministic algorithm to enumerate all min-$k$-cut-sets in hypergraphs, thus improving on the previously known $n^{O(k^2)}p$-time deterministic algorithm, where $n$ is the number of vertices and $p$ is the size of the hypergraph. The correctness analysis of our enumeration approach relies on a structural result that is a strong and unifying generalization of known structural results for Hypergraph-$k$-Cut and Minmax-Hypergraph-$k$-Partition. We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs).
