we showed that already a logarithmic numbers of levels suffices to compute solutions of high quality.

However, we still see a large potential in the $n$-level scheme as it provides a greater design space for future improvements.

Effectiveness tests comparing Mt-KaHyPar-D and
Mt-KaHyPar-Q (left), and both configurations that extend them with flow-based refinement (right) on .

Running Time of Algorithmic Components
We now analyze the running times of the different algorithmic components of Mt-KaHyPar on [Since initial
partitioning uses most of the other components within multilevel recursive bipartitioning,
we evaluate running times on the larger instances of  such that initial partitioning becomes
less time-consuming as explained earlier. We evaluated the solution quality of Mt-KaHyPar's different configurations on  due to the
effectiveness tests, which require a large number of repetitions per instance (10 repetitions on  vs 3 repetitions on .)].
Figure <ref> shows the fraction of instances (x-axis) for which the share of a component on the total execution
time is $\ge y\%$ for each configuration of Mt-KaHyPar. The intersection of $x = 0.5$ with the line of a component is the median share of the component on the
overall partitioning time.

Running time shares of the algorithmic components on the total execution time of
the different configurations of Mt-KaHyPar. For Mt-KaHyPar-Q, label propagation and
FM corresponds to their localized versions that run after each batch uncontraction, while Global FM refers to the
FM version that runs on the entire hypergraph after restoring identical nets.

The most time-consuming components of Mt-KaHyPar-D are preprocessing (consisting of the community detection algorithm
presented in Section <ref>), coarsening,
and the FM algorithm. These components have similar shares on the total partitioning time, which is between
$21\%$ and $23\%$ in the median. However, there are some long-running outliers for the FM algorithm
on instances with many large hyperedges. Here, the FM searches tend to move more nodes due to many zero-gain moves.
The median share of initial partitioning on the total execution time is $8.3\%$. Longer running times can be observed for
instances where we do not reach the contraction limit as, e.g., social networks with highly-skewed node degree distributions.
The running time of label propagation is negligible on most of the instances.

In the deterministic version of Mt-KaHyPar, preprocessing (median share on the total execution time is $42.7\%$) and
coarsening ($28.1\%$) takes the most time, while flow-based refinement ($77.8\%$) dominates the running time of Mt-KaHyPar-D-F
(the same is holds for Mt-KaHyPar-Q-F, which is why it is omitted in the plot).
In our $n$-level partitioning algorithm, the most time-consuming components are coarsening ($16\%$), batch uncontractions ($17.3\%$), and the localized version
of the FM algorithm ($22.1\%$).

[noheader, keys=key,value]speedupdata/scalability.dat

Geometric mean speedups of the total execution time, preprocessing (P), coarsening (C), initial partitioning (IP), and uncoarsening (UC)
of the different configurations of Mt-KaHyPar over all instances and instances with a single-threaded time $\ge 100$s.

2cMt-KaHyPar-SDet     2cMt-KaHyPar-D     2cMt-KaHyPar-Q     2cMt-KaHyPar-D-F

2rNum. Threads     All     $\ge 100$s      All     $\ge 100$s     All     $\ge 100$s     All     $\ge 100$s

4      $\placeholder{speedup}{deterministic_total_speed_up_t_4_0}$     $\placeholder{speedup}{deterministic_total_speed_up_t_4_100}$
$\placeholder{speedup}{default_total_speed_up_t_4_0}$     $\placeholder{speedup}{default_total_speed_up_t_4_100}$
$\placeholder{speedup}{quality_total_speed_up_t_4_0}$     $\placeholder{speedup}{quality_total_speed_up_t_4_100}$
$\placeholder{speedup}{default_flows_total_speed_up_t_4_0}$     $\placeholder{speedup}{default_flows_total_speed_up_t_4_100}$

16     $\placeholder{speedup}{deterministic_total_speed_up_t_16_0}$     $\placeholder{speedup}{deterministic_total_speed_up_t_16_100}$
$\placeholder{speedup}{default_total_speed_up_t_16_0}$     $\placeholder{speedup}{default_total_speed_up_t_16_100}$
$\placeholder{speedup}{quality_total_speed_up_t_16_0}$     $\placeholder{speedup}{quality_total_speed_up_t_16_100}$
$\placeholder{speedup}{default_flows_total_speed_up_t_16_0}$     $\placeholder{speedup}{default_flows_total_speed_up_t_16_100}$

64     $\placeholder{speedup}{deterministic_total_speed_up_t_64_0}$     $\placeholder{speedup}{deterministic_total_speed_up_t_64_100}$
$\placeholder{speedup}{default_total_speed_up_t_64_0}$     $\placeholder{speedup}{default_total_speed_up_t_64_100}$
$\placeholder{speedup}{quality_total_speed_up_t_64_0}$     $\placeholder{speedup}{quality_total_speed_up_t_64_100}$
$\placeholder{speedup}{default_flows_total_speed_up_t_64_0}$     $\placeholder{speedup}{default_flows_total_speed_up_t_64_100}$

4      $\placeholder{speedup}{deterministic_preprocessing_speed_up_t_4_0}$     $\placeholder{speedup}{deterministic_preprocessing_speed_up_t_4_100}$
$\placeholder{speedup}{default_preprocessing_speed_up_t_4_0}$     $\placeholder{speedup}{default_preprocessing_speed_up_t_4_100}$
$\placeholder{speedup}{quality_preprocessing_speed_up_t_4_0}$     $\placeholder{speedup}{quality_preprocessing_speed_up_t_4_100}$
$\placeholder{speedup}{default_flows_preprocessing_speed_up_t_4_0}$     $\placeholder{speedup}{default_flows_preprocessing_speed_up_t_4_100}$

16     $\placeholder{speedup}{deterministic_preprocessing_speed_up_t_16_0}$     $\placeholder{speedup}{deterministic_preprocessing_speed_up_t_16_100}$
$\placeholder{speedup}{default_preprocessing_speed_up_t_16_0}$     $\placeholder{speedup}{default_preprocessing_speed_up_t_16_100}$
$\placeholder{speedup}{quality_preprocessing_speed_up_t_16_0}$     $\placeholder{speedup}{quality_preprocessing_speed_up_t_16_100}$
$\placeholder{speedup}{default_flows_preprocessing_speed_up_t_16_0}$     $\placeholder{speedup}{default_flows_preprocessing_speed_up_t_16_100}$

64     $\placeholder{speedup}{deterministic_preprocessing_speed_up_t_64_0}$     $\placeholder{speedup}{deterministic_preprocessing_speed_up_t_64_100}$
$\placeholder{speedup}{default_preprocessing_speed_up_t_64_0}$     $\placeholder{speedup}{default_preprocessing_speed_up_t_64_100}$
$\placeholder{speedup}{quality_preprocessing_speed_up_t_64_0}$     $\placeholder{speedup}{quality_preprocessing_speed_up_t_64_100}$
$\placeholder{speedup}{default_flows_preprocessing_speed_up_t_64_0}$     $\placeholder{speedup}{default_flows_preprocessing_speed_up_t_64_100}$

4      $\placeholder{speedup}{deterministic_coarsening_speed_up_t_4_0}$     $\placeholder{speedup}{deterministic_coarsening_speed_up_t_4_100}$
$\placeholder{speedup}{default_coarsening_speed_up_t_4_0}$     $\placeholder{speedup}{default_coarsening_speed_up_t_4_100}$
$\placeholder{speedup}{quality_coarsening_speed_up_t_4_0}$     $\placeholder{speedup}{quality_coarsening_speed_up_t_4_100}$
$\placeholder{speedup}{default_flows_coarsening_speed_up_t_4_0}$     $\placeholder{speedup}{default_flows_coarsening_speed_up_t_4_100}$

16     $\placeholder{speedup}{deterministic_coarsening_speed_up_t_16_0}$     $\placeholder{speedup}{deterministic_coarsening_speed_up_t_16_100}$
$\placeholder{speedup}{default_coarsening_speed_up_t_16_0}$     $\placeholder{speedup}{default_coarsening_speed_up_t_16_100}$
$\placeholder{speedup}{quality_coarsening_speed_up_t_16_0}$     $\placeholder{speedup}{quality_coarsening_speed_up_t_16_100}$
$\placeholder{speedup}{default_flows_coarsening_speed_up_t_16_0}$     $\placeholder{speedup}{default_flows_coarsening_speed_up_t_16_100}$

64     $\placeholder{speedup}{deterministic_coarsening_speed_up_t_64_0}$     $\placeholder{speedup}{deterministic_coarsening_speed_up_t_64_100}$
$\placeholder{speedup}{default_coarsening_speed_up_t_64_0}$     $\placeholder{speedup}{default_coarsening_speed_up_t_64_100}$
$\placeholder{speedup}{quality_coarsening_speed_up_t_64_0}$     $\placeholder{speedup}{quality_coarsening_speed_up_t_64_100}$
$\placeholder{speedup}{default_flows_coarsening_speed_up_t_64_0}$     $\placeholder{speedup}{default_flows_coarsening_speed_up_t_64_100}$

4      $\placeholder{speedup}{deterministic_initial_partitioning_speed_up_t_4_0}$     $\placeholder{speedup}{deterministic_initial_partitioning_speed_up_t_4_100}$
$\placeholder{speedup}{default_initial_partitioning_speed_up_t_4_0}$     $\placeholder{speedup}{default_initial_partitioning_speed_up_t_4_100}$
$\placeholder{speedup}{quality_initial_partitioning_speed_up_t_4_0}$     $\placeholder{speedup}{quality_initial_partitioning_speed_up_t_4_100}$
$\placeholder{speedup}{default_flows_initial_partitioning_speed_up_t_4_0}$     $\placeholder{speedup}{default_flows_initial_partitioning_speed_up_t_4_100}$

16     $\placeholder{speedup}{deterministic_initial_partitioning_speed_up_t_16_0}$     $\placeholder{speedup}{deterministic_initial_partitioning_speed_up_t_16_100}$
$\placeholder{speedup}{default_initial_partitioning_speed_up_t_16_0}$     $\placeholder{speedup}{default_initial_partitioning_speed_up_t_16_100}$
$\placeholder{speedup}{quality_initial_partitioning_speed_up_t_16_0}$     $\placeholder{speedup}{quality_initial_partitioning_speed_up_t_16_100}$
$\placeholder{speedup}{default_flows_initial_partitioning_speed_up_t_16_0}$     $\placeholder{speedup}{default_flows_initial_partitioning_speed_up_t_16_100}$

64     $\placeholder{speedup}{deterministic_initial_partitioning_speed_up_t_64_0}$     $\placeholder{speedup}{deterministic_initial_partitioning_speed_up_t_64_100}$
$\placeholder{speedup}{default_initial_partitioning_speed_up_t_64_0}$     $\placeholder{speedup}{default_initial_partitioning_speed_up_t_64_100}$
$\placeholder{speedup}{quality_initial_partitioning_speed_up_t_64_0}$     $\placeholder{speedup}{quality_initial_partitioning_speed_up_t_64_100}$
$\placeholder{speedup}{default_flows_initial_partitioning_speed_up_t_64_0}$     $\placeholder{speedup}{default_flows_initial_partitioning_speed_up_t_64_100}$

4      $\placeholder{speedup}{deterministic_uncoarsening_speed_up_t_4_0}$     $\placeholder{speedup}{deterministic_uncoarsening_speed_up_t_4_100}$
$\placeholder{speedup}{default_uncoarsening_speed_up_t_4_0}$     $\placeholder{speedup}{default_uncoarsening_speed_up_t_4_100}$
$\placeholder{speedup}{quality_uncoarsening_speed_up_t_4_0}$     $\placeholder{speedup}{quality_uncoarsening_speed_up_t_4_100}$
$\placeholder{speedup}{default_flows_uncoarsening_speed_up_t_4_0}$     $\placeholder{speedup}{default_flows_uncoarsening_speed_up_t_4_100}$

16     $\placeholder{speedup}{deterministic_uncoarsening_speed_up_t_16_0}$     $\placeholder{speedup}{deterministic_uncoarsening_speed_up_t_16_100}$
$\placeholder{speedup}{default_uncoarsening_speed_up_t_16_0}$     $\placeholder{speedup}{default_uncoarsening_speed_up_t_16_100}$
$\placeholder{speedup}{quality_uncoarsening_speed_up_t_16_0}$     $\placeholder{speedup}{quality_uncoarsening_speed_up_t_16_100}$
$\placeholder{speedup}{default_flows_uncoarsening_speed_up_t_16_0}$     $\placeholder{speedup}{default_flows_uncoarsening_speed_up_t_16_100}$

64     $\placeholder{speedup}{deterministic_uncoarsening_speed_up_t_64_0}$     $\placeholder{speedup}{deterministic_uncoarsening_speed_up_t_64_100}$
$\placeholder{speedup}{default_uncoarsening_speed_up_t_64_0}$     $\placeholder{speedup}{default_uncoarsening_speed_up_t_64_100}$
$\placeholder{speedup}{quality_uncoarsening_speed_up_t_64_0}$     $\placeholder{speedup}{quality_uncoarsening_speed_up_t_64_100}$
$\placeholder{speedup}{default_flows_uncoarsening_speed_up_t_64_0}$     $\placeholder{speedup}{default_flows_uncoarsening_speed_up_t_64_100}$

In Figure <ref> and <ref>, and Table <ref>, we summarize self-relative speedups
of Mt-KaHyPar for each configuration and the different phases of the multilevel scheme with an increasing number of threads $t \in \{1,4,16,64\}$.
The scalability experiments run on . However, we used a subset for Mt-KaHyPar-Q (77 out of 94 hypergraphs) and Mt-KaHyPar-D-F (76 out of 94 hypergraphs) to ensure
reasonable running times. This set consists of instances where Mt-KaHyPar-Q/-D-F was able to finish in under 600 seconds with $64$ threads
for all tested values of $k$. The experiment still took $6$ weeks to complete for each configuration.
Note that we only rerun the experiments for Mt-KaHyPar-SDet/-D for this work, while the speedups of Mt-KaHyPar-Q/-D-F
are based on the data from the corresponding conference publications <cit.> due to the high time requirements.
In the plot, we represent the speedup (y-axis)
of each instance as a point and the centered rolling geometric mean over the points with a window size of $25$ as a line. The x-axis shows the single-threaded
running time of the corresponding configuration resp. component[In contrast
to many other publications in the parallel partitioning community, we do not correlate
speedups to any of the common hypergraph metrics (such as the number of pins).
We found that the running time often depends on a variety of different factors. Fitting
suitable parameters for a combination of the metrics seem much more complicated
than plotting against sequential running time, which is often nicely correlated with

Speedups of Mt-KaHyPar-SDet (left), Mt-KaHyPar-D (middle), and Mt-KaHyPar-Q (right).

Speedups of Mt-KaHyPar-D-F and flow-based refinement for different values of $k$.

Performance profiles comparing the solution quality of Mt-KaHyPar
with an increasing number of threads on .

The overall geometric mean speedup of Mt-KaHyPar-D is $\placeholder{speedup}{default_total_speed_up_t_4_0}$ for $t = 4$,
$\placeholder{speedup}{default_total_speed_up_t_16_0}$ for $t = 16$, and $\placeholder{speedup}{default_total_speed_up_t_64_0}$ for $t = 64$.
If we only consider instances with a single-threaded running time $\ge 100$s, the geometric mean speedup increases to $\placeholder{speedup}{default_total_speed_up_t_64_100}$
for $t = 64$. For $t = 4$, the speedup is at least $3$ on $\placeholder{speedup}{default_total_speed_up_larger_than_3_t_4}\%$ of the instances.
The community detection algorithm (refered to as preprocessing) and coarsening share many similarities in their implementation and both
show reliable speedups for an increasing number of threads. For initial partitioning and the uncoarsening phase, we observe that longer single-threaded
execution times leads to substantially better speedups. The most time-consuming component of the uncoarsening phase is the FM algorithm.
The geometric mean speedup of the FM algorithm is $\placeholder{speedup}{default_fm_speed_up_t_64_0}$ for $t = 64$, which increases to
$\placeholder{speedup}{default_fm_speed_up_t_64_100}$ for instances with sequential time $\ge 100$s.

If we compare the speedups of Mt-KaHyPar-SDet to its non-deterministic counterpart Mt-KaHyPar-D, we see that it achieves much more reliable speedups.
Especially, the speedups of initial partitioning increases substantially with a geometric mean speedup of
$\placeholder{speedup}{deterministic_initial_partitioning_speed_up_t_64_0}$ for $t = 64$.
Since Mt-KaHyPar-SDet does not adaptively adjust the number of repetitions in the bipartitioning
portfolio, it performs more work in the initial partitioning phase and is not affected by non-deterministic decisions, which increases its scalability
(geometric mean running time of initial partitioning is $9.36$s in Mt-KaHyPar-SDet vs $4.23$s in Mt-KaHyPar-D for $t = 1$).
The overall geometric mean speedup of Mt-KaHyPar-SDet is $\placeholder{speedup}{deterministic_total_speed_up_t_4_0}$ for $t = 4$,
$\placeholder{speedup}{deterministic_total_speed_up_t_16_0}$ for $t = 16$, and $\placeholder{speedup}{deterministic_total_speed_up_t_64_0}$ for $t = 64$.

The coarsening and batch uncontraction algorithm are the components that differentiate our $n$-level partitioning algorithm Mt-KaHyPar-Q
from the other multilevel algorithms.
Both components exhibit good speedups, while coarsening (geometric mean speedup is
$\placeholder{speedup}{quality_coarsening_speed_up_t_64_0}$ for $t = 64$) scales slightly better than the batch uncontractions
($\placeholder{speedup}{quality_batch_uncontractions_speed_up_t_64_0}$ for $t = 64$). Moreover, the speedups of the localized version of
FM algorithm that runs after each batch uncontraction operation are less pronounced than the speedups of the FM algorithm in Mt-KaHyPar-D
(geometric mean speedup $\placeholder{speedup}{quality_fm_speed_up_t_64_0}$ vs $\placeholder{speedup}{default_fm_speed_up_t_64_0}$ for $t = 64$).
Note that we also observe super-linear speedups, which are caused by non-deterministic coarsening decisions.
The geometric mean speedup of Mt-KaHyPar-Q is $\placeholder{speedup}{quality_total_speed_up_t_4_0}$ for $t = 4$,
$\placeholder{speedup}{quality_total_speed_up_t_16_0}$ for $t = 16$, and $\placeholder{speedup}{quality_total_speed_up_t_64_0}$ for $t = 64$.

Mt-KaHyPar-D-F extends Mt-KaHyPar-D with flow-based refinement.
We therefore only show speedups for this component in Figure <ref>.
Unfortunely, the speedups are less promising as for the other configurations.
The geometric mean speedup of Mt-KaHyPar-D-F is $\placeholder{speedup}{default_flows_total_speed_up_t_4_0}$ for $t = 4$,
$\placeholder{speedup}{default_flows_total_speed_up_t_16_0}$ for $t = 16$, and $\placeholder{speedup}{default_flows_total_speed_up_t_64_0}$ for $t = 64$.
However, we achieve better speedups for larger values of $k$ where all parallelism is leveraged in the scheduling algorithm, and none in
the FlowCutter algorithm. For $k = 2$, the scalability depends on our parallel maximum flow algorithm for which we observe similar
speedups as reported in Ref. <cit.> – the work on which our parallel implementation is based on.
Thus, increasing the scalability of maximum flow algorithms is an important avenue for future research.

In Figure <ref>, we compare the solution quality of the different configurations when increasing the number
of threads. We can see that using more threads adversely affects the solution quality of the partitions produced by
Mt-KaHyPar-Q, but only by a small margin (solution are $0.4\%$ better with one compared to 64 threads).
Mt-KaHyPar-D and Mt-KaHyPar-D-F produce comparable solutions when increasing the number of threads.

Effects of Graph Optimizations

In Section <ref>, we presented optimized data structures for graph partitioning used as a drop-in replacement
in our partitioning algorithm. Figure <ref> shows their impact on the solution quality and speedups for
different algorithmic components of Mt-KaHyPar-D on . As it can be seen, replacing our hypergraph with
the graph data structures does not adversely affect the solution quality of Mt-KaHyPar-D as both performance lines
are almost identical and converges quickly towards $y = 1$.

Performance profile (left) and speedups (right) of coarsening (C), initial partitioning (IP),
label propagation (LP), and FM refinement comparing Mt-KaHyPar-D with and without our optimized
graph data structure on .

The coarsening algorithm benefits most from our optimized graph data structure (geometric mean speedup $2.48$).
The hypergraph version computes a clustering of the nodes by iterating over the pin-lists of nets
to aggregate ratings, and subsequently contract that clustering by collapsing two adjacency arrays (one for the
pin-lists and one for the incident nets). The cache-friendly memory layout for graphs (only one adjacency array for neighbors)
leads to faster access times to enumerate neighbors and to a simpler contraction algorithm. The FM algorithm has the least promising
speedups ($1.29$). One of the most time-consuming parts of the algorithm is retrieving and updating entries from the gain
table, which has the same asymptotic worst-case complexity in both implementations. The initial partitioning phase ($1.8$)
has better speedups than both refinement algorithms but slightly worse speedups than coarsening. This can be explained by
the fact that initial partitioning uses all algorithms within multilevel recursive bipartitioning.

The overall speedup of the graph version of Mt-KaHyPar-D over its hypergraph counterpart is $1.75$ on average
( $10.8$s vs $18.94$s). In the dissertation of Heuer <cit.>, we also present an optimized
graph data structure for $n$-level partitioning, which accelerates Mt-KaHyPar-Q by a factor of $1.91$ on average
($97.45$s vs $186.32$s). We note that flow-based refinement requires further engineering efforts to handle large graphs efficiently
(currently works only on medium-sized graphs in reasonable running times).
The FlowCutter algorithm operates implicitly on the Lawler expansion <cit.>
($n + 2m$ nodes and $5m$ edges) of the input (hyper)graph. An optimized version would omit this transformation and
compute a maximum flow directly on the graph representation. However, this issue will be addressed in a future release
of Mt-KaHyPar.

§.§ Comparison to Other Systems

We now compare Mt-KaHyPar to existing partitioning algorithms to see if it can improve the state-of-the-art.
We did an extensive research on publicly available partitioning tools and were able to include $25$ different sequential and parallel
graph and hypergraph partitioners that we compare on over 800 graphs and hypergraphs. Thus, to the best of our knowledge, this study represents
the most comprehensive comparison of partitioning algorithms to date.
We primarly focus on multilevel algorithms as it has been shown that they provide an excellent trade-off
between solution quality and running time <cit.>. While there are even faster
partitioning method that omit the multilevel scheme, it has been shown that they are inferior to multilevel
algorithms in terms of solution quality <cit.>. Moreover, algorithms that achieve even higher solution quality than
multilevel algorithms such as evolutionary algorithms <cit.>, diffusion-based partitioning <cit.>,
and approaches based on integer linear programming <cit.> would not run in a reasonable time frame on our benchmark sets.

We first provide a description of the partitioning algorithms included in our study and explain how we configured them.
We then identify a subset of Pareto-optimal algorithms to which we then compare Mt-KaHyPar[We made
all experimental results publicly available from <https://algo2.iti.kit.edu/heuer/talg/>.].

Listing of graph and hypergraph partitioning algorithms (GP and HGP) included in the experimental evaluation.
For algorithms publicly available on GitHub, we report the first seven characters of the
corresponding commit hash indicating the used version.

2cSequential     3cParallel

Algorithm     Version     Algorithm     Version     Machine Model

Metis <cit.>      5.1.0      KaMinPar <cit.>     29101f61f22b917b5c6c824275040f747f2c4b3b     Shared-Memory

Metis-R and Metis-K         Mt-Metis <cit.>     0.6.0     Shared-Memory

KaFFPa <cit.>     f239f7afd21e73d9db349aeb62d578b4b256b93b     ParMetis <cit.>     4.0.3     Distributed-Memory

2lKaFFPa-Fast(S)/-Eco(S)/-Strong(S)     Mt-KaHIP <cit.>     30de7371a2348945cbbc1ba0c2b8ae26e0ab6793     Shared-Memory

Scotch <cit.>     6.1.3     ParHIP <cit.>       f239f7afd21e73d9db349aeb62d578b4b256b93b     Distributed-Memory

2lParHIP-Fast and ParHIP-Eco

PaToH <cit.>     3.3      Zoltan <cit.>     3.83     Distributed-Memory

2lPaToH-D and PaToH-Q     BiPart <cit.>     49a59a652bf9492fd1f44d4ecebb1a7af47bbac2     Shared-Memory

hMetis <cit.>     2.0pre1

2lhMetis-R and hMetis-K

KaHyPar <cit.>     876b7768a92614747e6427e596b89506349c7561

2lKaHyPar-CA, $r$KaHyPar, and $k$KaHyPar

Mondriaan <cit.>     4.2.1

Included Algorithms

Table <ref> lists all partitioning algorithms included in the following experimental evaluation.
Many of these algorithms provide multiple partitioning configurations
offering different trade-offs in running time and solution quality (e.g., KaFFPa-Fast/-Eco/-Strong,
or the default (-D) and quality preset (-Q) of PaToH), or are
based on either recursive bipartitioning (e.g., hMetis-R) or direct $k$-way partitioning (e.g., hMetis-K).
The graph partitioner KaFFPa also provides different settings for partitioning social networks (KaFFPa-FastS/-EcoS/-StrongS).
Thus, we include all three social configurations as well as their non-social counterparts (KaFFPa-Fast/-Eco/-Strong).
For the $n$-level algorithm KaHyPar, we include the recursive bipartitioning ($r$KaHyPar) and direct $k$-way version
($k$KaHyPar, which uses similar algorithmic components as Mt-KaHyPar-Q-F), as well as a configuration without flow-based refinement (KaHyPar-CA,
which uses similar algorithmic components as Mt-KaHyPar-Q).

Unfortunely, we were not able to include the publicly available versions of Parkway <cit.> (distributed-memory),
PT-Scotch <cit.> (distributed-memory), and Chaco <cit.> (sequential). These algorithms
failed with segmentation faults on most instances of our benchmark sets.

Algorithm Configuration

We configure all graph partitioning algorithms to optimize the edge cut metric, while we optimize the connectivity
metric for hypergraph partitioning. We run Mt-KaHyPar using ten threads for comparisons to sequential
algorithms as this is a typical number of available cores in a modern commodity workstation.
We add a suffix to the name of parallel algorithms indicating the number of threads
used, e.g., Mt-KaHyPar 64 for 64 threads. We omit the suffix for sequential algorithms.
For graph partitioning, Mt-KaHyPar uses the partition and graph data structure presented in Section <ref>.

We use the default settings provided by the authors to configure the different partitioning algorithms. However, for algorithms based on recursive bipartitioning,
we adjust the input imbalance parameter $\varepsilon$ to $\varepsilon' := (1 + \varepsilon)^{\frac{1}{\lceil \log_2{k} \rceil}}$ (based
on Equation <ref> by applying it to the first bipartitioning step) when we observed that most of the computed partitions are imbalanced.
This applies to Metis-R, hMetis-R, and BiPart.
We further set hMetis to optimize the sum-of-external-degree metric $\osoed(\Partition) := \sum_{e \in \cutnets} \lambda(e) \cdot \omega(e)
= \ocon(\Partition) + \ocut(\Partition)$ (connectivity plus cut-net metric) and calculate the connectivity metric accordingly.
We additionally configure Mt-Metis to use its hill-scanning refinement algorithm <cit.>.
Moreover, we do not perform multiple repetitions when running Scotch or BiPart as both do not provide
a command line parameter for setting a seed value.

Summary of algorithms (first column) outperforming others (second column). It shows the median improvement in the connectivity
resp. edge cut metric in percent for each baseline over the outperformed algorithm and the average slowdown of the outperformed
relative to the baseline algorithm.

4c|Sequential     4cParallel (64 threads)

Base Algo.     Outperformed     Med. [$\%$]     Rel. Slow.     Base Algo.     Outperformed     Med. [$\%$]     Rel. Slow.

Metis-K      Metis-R     2.9     1.4     KaMinPar     Mt-Metis     0     9.11

Metis-K     KaFFPa-Fast     5.8     4.3     KaMinPar     ParMetis     4.4     211.2

Metis-K     KaFFPa-FastS     2.2     4,79     KaMinPar     ParHIP-Fast     2.8     8.18

Metis-K     Scotch     2.5     4.66     Mt-KaHIP     ParHIP-Eco     2.2     11.62

KaFFPa-EcoS     KaFFPa-Eco     3.2     1.04

PaToH-D     Mondriaan     0.6     5.63     Zoltan     BiPart     69     2.31

KaHyPar-CA     hMetis-R     0.5     3.31

KaHyPar-CA     hMetis-K     2.6     2.62

$k$KaHyPar     $r$KaHyPar     2.1     $\sim 1$

Identifying Competitors

Since some of the included algorithms already outperform others with regards to solution quality and running time,
we compare Mt-KaHyPar only to a subset of Pareto-optimal partitioning algorithms.
Table <ref> presents a summary of the results that we used to identify our main competitors.
The data is based on a detailed evaluation that can be found in the dissertation of Heuer <cit.>.
We added the performance profiles and running time plots used for this evaluation in Appendix <ref>.
In the table, the algorithms in the second column are outperformed by the algorithms in the first column and are therefore excluded
from the following experimental evaluation.
The included systems can be classified into fast partitioning methods (PaToH-D, Zoltan, Metis-K, and
KaMinPar), configurations providing a good trade-off between solution quality and running time (PaToH-Q, KaFFPa-EcoS,
and Mt-KaHIP), and high-quality partitioning algorithms (KaHyPar-CA, $k$KaHyPar, and KaFFPa-Strong/-StrongS).
To simplify the following evaluation, we compare the high quality algorithms to Mt-KaHyPar-Q-F (highest quality configuration)
and all others to Mt-KaHyPar-D (fastest configuration).

Comparison to Sequential Systems

Figure <ref> compares Mt-KaHyPar to the sequential hypergraph partitioners
PaToH and KaHyPar on .
In an individual comparison,
Mt-KaHyPar-D ( $0.88$s) computes better partitions than
PaToH-D ($1.17$s) and PaToH-Q ($5.85$s) on $82.9\%$ and $58.34\%$ of the instances
(median improvement is $6.6\%$ and $1.2\%$)[It appears that Mt-KaHyPar-D performs slightly
worse than PaToH-Q in the performance profiles. However, if we would compare them in a performance profile
individually, we would see that the performance line of Mt-KaHyPar-D lies strictly above the line of
PaToH-Q. We therefore point out that performance profiles do not permit a full ranking between three or more algorithms.],
while it achieves a speedup of $1.32$  PaToH-D
and $6.6$  PaToH-Q with ten threads on average.
Thus, Mt-KaHyPar-D outperforms PaToH-D and PaToH-Q.

We can also see that the performance lines of Mt-KaHyPar-Q-F and $k$KaHyPar
– the currently best sequential hypergraph partitioning algorithm – are almost identical, which means that both compute
partitions of comparable solution quality. Mt-KaHyPar-Q-F ($5.08$s)
is faster than KaHyPar-CA ($28.14$s) and $k$KaHyPar ($48.97$s)
on almost all instances with ten threads ($\ge 99\%$). This shows that we achieved
the same solution quality as the currently highest-quality sequential partitioning algorithm, while being almost an
order of magnitude faster with only ten threads.
Moreover, Mt-KaHyPar-Q-F is also slightly faster than PaToH-Q, while
it computes  better partitions than PaToH-Q on $87.7\%$ of the instances
(median improvement is $6.4\%$).

Performance profiles and running times comparing Mt-KaHyPar to
PaToH and KaHyPar on .

Figure <ref> compares Mt-KaHyPar to the sequential graph partitioners Metis-K
and KaFFPa on .
Mt-KaHyPar-D ( $0.55$s) is slightly slower than Metis-K ($0.39$s) with ten threads but produces significantly better edge cuts
(median improvement is $5.9\%$). If we disable the FM algorithm in Mt-KaHyPar-D, we obtain a configuration that is slightly
faster than Metis-K, while the edge cuts are comparable (see Figure <ref> in Appendix <ref>).

Mt-KaHyPar-Q-F ($5.22$s) is faster than KaFFPa-EcoS ($10.51$s) and produces better edge cuts
by $2.9\%$ in the median. The differences between the edge cuts computed by
Mt-KaHyPar-Q-F and KaFFPa-Strong ($162.83$s) are not statiscally
significant ($Z = -2.3101$ and $p = 0.02088$).
Out of all tested algorithms, KaFFPa-StrongS ($201.99$s) is the only algorithm producing slightly better edge cuts than
Mt-KaHyPar-Q-F (median improvement is $1\%$). However, this comes at the cost of a $38.66$ times
longer running time on average, making the quality improvement questionable in practice.

Performance profiles and running times comparing Mt-KaHyPar to
Metis and KaFFPa on .

Geometric mean running times of different sequential (hyper)graph partitioning algorithm and Mt-KaHyPar-D/-Q-F
with an increasing number of threads on  (left) and  (right).

2c|Mt-KaHyPar                                            2cMt-KaHyPar

Seq. Algo.      $t[s]$     Threads     -D     -Q-F
Seq. Algo.      $t[s]$     Threads     -D     -Q-F

Metis-K            $0.39$        16          $0.45$     $4.23$      PaToH-D          $1.17$            16          $0.74$        $3.98$

Metis-R            $0.55$        10          $0.55$     $5.22$      PaToH-Q          $5.86$            10          $0.88$        $5.08$

KaFFPa-Fast        $1.69$        8           $0.61$     $5.74$      Mondriaan        $6.62$            8           $1.08$        $5.58$

Scotch             $1.84$        4           $0.98$     $8.98$      KaHyPar-CA       $28.14$           4           $1.83$        $9.07$

KaFFPa-FastS       $1.88$        2           $1.69$     $15.64$     $r$KaHyPar       $46.10$           2           $3.33$        $16.04$

KaFFPa-EcoS        $10.51$       1           $3.00$     $28.56$     $k$KaHyPar       $48.98$           1           $6.24$        $29.52$

KaFFPa-Eco         $10.94$                                          hMetis-K         $73.75$

KaFFPa-Strong      $162.83$                                         hMetis-R         $93.21$

KaFFPa-StrongS     $201.99$

As we have seen, Mt-KaHyPar-D is faster than most of the sequential algorithms using ten threads.
This raises the question whether or not the result still holds when we use less threads. We therefore
compare the running times of Mt-KaHyPar-D/-Q-F with an increasing number of threads to the different sequential
algorithms on  and  in Table <ref>[Note that increasing the number of threads
does not affect the solution quality of Mt-KaHyPar-D/-Q-F, as shown in Figure <ref>.].
On , Mt-KaHyPar-D is faster than most of the sequential algorithms using two threads.
Metis-K is still faster than Mt-KaHyPar-D, but their running times become comparable when we use $16$ threads.
The sequential time of Mt-KaHyPar-Q-F is almost an order of magnitude faster than the running time of the best sequetial
partitioner KaFFPa-StrongS, and it becomes faster than KaFFPa-EcoS when we use four threads.
On , we have to run Mt-KaHyPar-D with eight threads to achieve comparable speed to PaToH-D.
However, this number decreases to two threads when we compare their running times on the larger instances of  <cit.>.
The sequential time of Mt-KaHyPar-D is comparable to PaToH-Q, and Mt-KaHyPar-Q-F is
significantly faster than its sequential counterpart $k$KaHyPar when we use only one thread.

Comparison to Parallel Systems

Figure <ref> compares Mt-KaHyPar to the hypergraph partitioners
Zoltan (distributed-memory), BiPart (deterministic shared-memory), and
PaToH (sequential) on . Note that PaToH-D is fast enough to conduct the experiments on  in a reasonable time frame,
while this is not the case for any of the other sequential partitioners.
Despite the fact that Zoltan has been shown to outperform BiPart (see Table <ref>),
we have included it for a direct comparison to our deterministic configuration Mt-KaHyPar-SDet.

The median improvement of Mt-KaHyPar-SDet ( $3.14$s) over
BiPart ($29.19$s) – the only existing competitor for deterministic partitioning –
is $200\%$, while it is almost an order of magnitude faster. Our deterministic algorithm
also outperforms Zoltan ($12.63$s, median improvement is $12\%$) and
the Wilcoxon signed-ranked test reveals that there is no statistically significant difference between the
solutions produced by Mt-KaHyPar-SDet and PaToH-D ($51.2$s,
$Z = 1.7314$ and $p = 0.08337$).

Mt-KaHyPar-D ($4.64$s) is slightly slower than Mt-KaHyPar-SDet, but it computes solutions
that are $23\%$ resp. $6.6\%$ better than those of Zoltan resp. PaToH-D in the median and
is still significantly faster than both algorithms. When flow-based refinement is used (Mt-KaHyPar-D-F, not shown in the plots),
we achieve a median improvement over Zoltan of $34\%$.
This shows that Mt-KaHyPar can partition extremely large hypergraph with high solution quality,
which was previously only possible with sequential codes on medium-sized instances.

Performance profiles and running times comparing Mt-KaHyPar to
PaToH and Zoltan on .

Figure <ref> compares Mt-KaHyPar to the parallel graph partitioner
KaMinPar (shared-memory) and Mt-KaHIP (shared-memory, also implements
a parallel version of the FM algorithm) on . We can see that Mt-KaHyPar-D ($10.8$s)
computes on most of the instances the best solutions. The median improvement of Mt-KaHyPar-D
over Mt-KaHIP ($13.69$s) is $2.1\%$, while it is also slightly faster. Out of
all tested algorithms, KaMinPar ($2.69$s) is the only algorithm that is faster than Mt-KaHyPar-D,
but the edge cuts produced by KaMinPar are worse than those of Mt-KaHyPar-D by
$9.9\%$ in the median. On larger graph instances, KaMinPar is the method of choice when speed is more important
than quality, and Mt-KaHyPar should be used if one aims for high solution quality.

Performance profiles and running times comparing Mt-KaHyPar to
KaMinPar and Mt-KaHIP on .

In this study, we partitioned (hyper)graphs in up to $128$ blocks with an allowed imbalance of $\varepsilon = 3\%$.
We want to point out that there are still settings where the results of this evaluation do not apply.
For example, KaMinPar is specifically designed for partitioning graphs into a
large number of blocks (e.g., $k \in \Oh{\sqrt{n}}$). In this setting, existing algorithms struggle to find
balanced solutions or do not complete in a reasonable time frame <cit.>.
We are integrating KaMinPar's deep multilevel partitioning scheme in Mt-KaHyPar and hope to offer support for very large $k$ in the near future.
Another limitation is the restriction of our algorithms to running in-memory on a single machine, and thus instances are restricted to the size of currently available RAM.
Finally, partitioning (hyper)graphs with a tight balance constraint (e.g., $\varepsilon \approx 0$) poses additional
challenges for traditional refinement algorithms as this drastically reduces the set of possible moves.

§ CONCLUSION

We have presented the first set of shared-memory algorithms for partitioning hypergraphs. Our solver Mt-KaHyPar
produces solutions on par with the best sequential codes, while it is faster than most of the existing parallel algorithms.
We demonstrated this achievement in our extensive experimental evaluation with 25 sequential and parallel
graph and hypergraph partitioners tested on over $800$ (hyper)graphs.
We contributed parallel formulations for all phases of the multilevel scheme: a parallel clustering-based coarsening
algorithm guided by the community structure of the input hypergraph obtained via a parallel community detection algorithm,
initial partitioning via parallel recursive bipartitioning using work-stealing, the first fully-parallel FM implementation,
and a parallelization of flow-based refinement.
Perhaps the most suprising result is the efficient parallelization of the $n$-level partitioning scheme, even though
we showed that traditional multilevel algorithms can compute comparable solutions when flow-based refinement is used.
Furthermore, we presented multiple techniques to accurately (re)compute gain values
for concurrent node moves, which had not been addressed in
parallel partitioning algorithms before. We also proposed data structure optimizations
for plain graphs, making Mt-KaHyPar the state-of-the-art solver for graph partitioning.
Additionally, we devised a deterministic version of our multilevel algorithm based on the synchronous local moving scheme.

Given that quality improvements often come at the cost of significantly longer running times, it may be interesting to
evaluate the quality-time trade-off of existing tools for applications before advancing the
field of high-quality partitioning. For instances that do not fit into the main memory of a single machine,
translating the techniques presented in this work into the distributed-memory setting is also
an important area for future research. We see further algorithmic improvements in a localized version
of flow-based refinement that runs after each batch uncontraction in the $n$-level scheme as well as
improving clustering decisions in the coarsening phase.

The authors thank Michael Hamann, Daniel Seemaier, Christian Schulz and Dorothea Wagner for helpful discussions over the course of this research.
This work was supported in part by DFG grants WA654/19-2 and SA933/11-1. The
authors acknowledge support by the state of Baden-Württemberg through bwHPC.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Abou-Rjeili and KarypisAbou-Rjeili and
authorpersonAmine Abou-Rjeili and
personGeorge Karypis. year2006.
Multilevel Algorithms for Partitioning Power-Law
Graphs. In booktitle20th International Parallel and
Distributed Processing Symposium (IPDPS). publisherIEEE.

authorpersonYaroslav Akhremtsev.
titleParallel and External High Quality Graph
Dissertation. schoolKarlsruhe Institute of Technology.

[Akhremtsev, Heuer, Sanders, and
SchlagAkhremtsev et al2017a]
authorpersonYaroslav Akhremtsev,
personTobias Heuer, personPeter Sanders, and
personSebastian Schlag. year2017a.
Engineering a Direct k-way Hypergraph
Partitioning Algorithm. In booktitle19th Workshop on
Algorithm Engineering & Experiments (ALENEX). publisherSIAM,

[Akhremtsev, Sanders, and SchulzAkhremtsev
et al2017b]
authorpersonYaroslav Akhremtsev, personPeter
Sanders, and personChristian Schulz.
High-Quality Shared-Memory Graph Partitioning.
In booktitleEuropean Conference on Parallel Processing
(Euro-Par). publisherSpringer, pages659–671.

[Aloul, Markov, and SakallahAloul
et al2004]
authorpersonFadi A. Aloul, personIgor L.
Markov, and personKarem A. Sakallah.
MINCE: A Static Global Variable-Ordering
Heuristic for SAT Search and BDD Manipulation.
journalThe International Journal of Universal
Computer Science volume10, number12
(year2004), pages1562–1596.

authorpersonCharles J. Alpert.
The ISPD98 Circuit Benchmark Suite. In
booktitleInternational Symposium on Physical Design
(ISPD). pages80–85.

[Alpert, Huang, and KahngAlpert
et al1997]
authorpersonCharles J. Alpert,
personJsen-Hsin Huang, and personAndrew B. Kahng.
Multilevel Circuit Partitioning. In
booktitle34th Conference on Design Automation (DAC).

[Alpert and KahngAlpert and Kahng1995]
authorpersonCharles J. Alpert and
personAndrew B. Kahng. year1995.
Recent Directions in Netlist Partitioning: A
journalIntegration: The VLSI Journal
volume19, number1-2 (year1995),

[Anderson and SetubalAnderson and
authorpersonRichard J. Anderson and
personJoão C. Setubal. year1995.
A Parallel Implementation of the Push-Relabel
Algorithm for the Maximum Flow Problem.
journalJ. Parallel and Distrib. Comput.
volume29, number1 (year1995),

[Andre, Schlag, and SchulzAndre
et al2018]
authorpersonRobin Andre, personSebastian
Schlag, and personChristian Schulz.
Memetic Multilevel Hypergraph Partitioning. In
booktitleGenetic and Evolutionary Computation Conference
(GECCO). publisherACM, pages347–354.

[Andres-Martinez and HeunenAndres-Martinez
and Heunen2019]
authorpersonPablo Andres-Martinez and
personChris Heunen. year2019.
Automated Distribution of Quantum Circuits via
Hypergraph Partitioning.
journalPhysical Review A volume100,
number3 (year2019), pages1–11.

[Aykanat, Cambazoglu, and UçarAykanat
et al2008a]
authorpersonCevdet Aykanat,
personBerkant Barla Cambazoglu, and personBora
Uçar. year2008a.
Multi-level Direct $k$-Way Hypergraph Partitioning
With Multiple Constraints and Fixed Vertices.
journalJournal of Parallel Distributed Computing
volume68, number5 (year2008),

[Aykanat, Cambazoglu, and UçarAykanat
et al2008b]
authorpersonCevdet Aykanat,
personBerkant Barla Cambazoglu, and personBora
Uçar. year2008b.
Multi-level Direct $k$-way Hypergraph Partitioning
With Multiple Constraints and Fixed Vertices.
journalJ. Parallel and Distrib. Comput.
volume68, number5 (year2008),

[Bader, Meyerhenke, Sanders, and WagnerBader
et al2013a]
editorpersonDavid Bader, personHenning
Meyerhenke, personPeter Sanders, and personDorothea
Wagner (Eds.). year2013a.
booktitleGraph Partitioning and Graph Clustering,
10th DIMACS Implementation Challenge Workshop.
seriesContemporary Mathematics, Vol. volume588.
publisherAmerican Mathematical Society.

[Bader, Meyerhenke, Sanders, and WagnerBader
et al2013b]
authorpersonDavid A. Bader, personHenning
Meyerhenke, personPeter Sanders, and personDorothea
Wagner. year2013b.
booktitleGraph Partitioning and Graph
Clustering. Vol. volume588.
publisherAmerican Mathematical Society Providence, RI.

[Barnard and SimonBarnard and Simon1993]
authorpersonStephen T. Barnard and
personHorst D. Simon. year1993.
A Fast Multilevel Implementation of Recursive
Spectral Bisection for Partitioning Unstructured Problems. In
booktitle6th SIAM Conference on Parallel Processing for
Scientific Computing (PPSC). pages711–718.

[Baumstark, Blelloch, and ShunBaumstark
et al2015]
authorpersonNiklas Baumstark, personGuy E.
Blelloch, and personJulian Shun.
Efficient Implementation of a Synchronous Parallel
Push-Relabel Algorithm. In booktitle23rd European Symposium
on Algorithms (ESA), Vol. volume9294.
publisherSpringer, pages106–117.

[Belov, Diepold, Heule, and
JärvisaloBelov et al2014]
authorpersonAnton Belov, personDaniel
Diepold, personMarijn Heule, and personMatti
Järvisalo. year2014.
titleThe SAT Competition 2014.

[Blelloch, Fineman, Gibbons, and ShunBlelloch
et al[n.d.]]
authorpersonGuy E. Blelloch, personJeremy T.
Fineman, personPhillip B. Gibbons, and personJulian
Shun. year[n.d.].
Internally Deterministic Parallel Algorithms Can
Be Fast. In booktitlePPoPP 2012.

[Blondel, Guillaume, Lambiotte, and
LefebvreBlondel et al2008]
authorpersonVincent D. Blondel, personJean
Guillaume, personRenaud Lambiotte, and
personEtienne Lefebvre. year2008.
Fast Unfolding of Communities in Large Networks.
journalJournal of Statistical Mechanics: Theory and
Experiment number10 (year2008).

[Bocchino, Adve, Adve, and SnirBocchino
et al2009]
authorpersonRobert L Bocchino, personVikram
Adve, personSarita Adve, and personMarc Snir.
Parallel Programming Must Be Deterministic By
journalUsenix HotPar  volume6

[Brandes, Delling, Gaertler, Görke, Hoefer,
Nikoloski, and WagnerBrandes et al2008]
authorpersonUlrik Brandes, personDaniel
Delling, personMarco Gaertler, personRobert Görke,
personMartin Hoefer, personZoran Nikoloski, and
personDorothea Wagner. year2008.
On Modularity Clustering.
journalIEEE Transactions on Knowledge and Data
Engineering volume20, number2
(year2008), pages172–188.

[Buluç, Meyerhenke, Safro, Sanders, and
SchulzBuluç et al2016]
authorpersonAydin Buluç, personHenning
Meyerhenke, personIlya Safro, personPeter Sanders,
and personChristian Schulz. year2016.
Recent Advances in Graph Partitioning.
In booktitleAlgorithm Engineering - Selected Results
and Surveys. Vol. volume9220. pages117–158.

[Campbell and SwinscowCampbell and
authorpersonMichael J. Campbell and
personThomas D.V. Swinscow. year2009.
booktitleStatistics at Square One.
publisherBMJ Publishing Group.

[Çatalyürek and
AykanatÇatalyürek and Aykanat2001a]
authorpersonÜmit V. Çatalyürek and
personCevdet Aykanat. year2001a.
A Fine-Grain Hypergraph Model for 2D Decomposition
of Sparse Matrices. In booktitle15th International Parallel
and Distributed Processing Symposium (IPDPS). pages118.

[Çatalyürek and
AykanatÇatalyürek and Aykanat2001b]
authorpersonÜmit V. Çatalyürek and
personCevdet Aykanat. year2001b.
A Hypergraph-Partitioning Approach for Coarse-Grain
Decomposition. In booktitleACM/IEEE Conference on
Supercomputing. publisherACM, pages28.

[Çatalyürek and
AykanatÇatalyürek and Aykanat2011]
authorpersonÜmit V. Çatalyürek and
personCevdet Aykanat. year2011.
booktitlePaToH: Partitioning Tool for

[Çatalyürek, Deveci, Kaya, and
UçarÇatalyürek et al2012]
authorpersonÜmit V. Çatalyürek,
personMehmet Deveci, personKamer Kaya, and
personBora Uçar. year2012.
Multithreaded Clustering for Multi-level
Hypergraph Partitioning. In booktitle26th International
Parallel and Distributed Processing Symposium (IPDPS).

[Çatalyürek, Devine, Faraj,
Gottesbüren, Heuer, Meyerhenke, Sanders, Schlag, Schulz, Seemaier, and
WagnerÇatalyürek et al2022]
authorpersonÜmit V. Çatalyürek,
personKaren D. Devine, personMarcelo Fonseca Faraj,
personLars Gottesbüren, personTobias Heuer,
personHenning Meyerhenke, personPeter Sanders,
personSebastian Schlag, personChristian Schulz,
personDaniel Seemaier, and personDorothea Wagner.
More Recent Advances in (Hyper)Graph Partitioning.
journalComputing Research Repository (CoRR)
volumeabs/2205.13202 (year2022).

[Catalyurek and AykanatCatalyurek and
authorpersonÜmit V. Catalyurek and
personCevdet Aykanat. year1999.
Hypergraph-Partitioning-Based Decomposition for
Parallel Sparse-Matrix Vector Multiplication.
journalIEEE Transactions on Parallel and Distributed
Systems volume10, number7 (year1999),

[Cherkassky and GoldbergCherkassky and
authorpersonBoris V. Cherkassky and
personAndrew V. Goldberg. year1997.
On Implementing the Push-Relabel Method for the
Maximum Flow Problem.
journalAlgorithmica volume19,
number4 (year1997), pages390–410.

[Chevalier and PellegriniChevalier and
authorpersonCédric Chevalier and
personFrançois Pellegrini.
PT-Scotch: A Tool for Efficient Parallel Graph
journalParallel Comput. volume34,
number6-8 (year2008), pages318–331.

[Curino, Zhang, Jones, and MaddenCurino
et al2010]
authorpersonCarlo Curino, personYang Zhang,
personEvan P. C. Jones, and personSamuel Madden.
Schism: A Workload-Driven Approach to Database
Replication and Partitioning.
journalProceedings of the VLDB Endowment
volume3, number1 (year2010),

[Davis and HuDavis and Hu2011]
authorpersonTimothy A. Davis and
personYifan Hu. year2011.
The University of Florida Sparse Matrix
journalACM Trans. Math. Software
volume38, number1 (date11
year2011), pages1:1–1:25.

[Deveci, Kaya, and
ÇatalyürekDeveci et al2013]
authorpersonMehmet Deveci, personKamer
Kaya, and personÜmit V. Çatalyürek.
Hypergraph Sparsification and Its Application to
Partitioning. In booktitle42nd International Conference on
Parallel Processing (ICPP). pages200–209.

[Devine, Boman, Heaphy, Bisseling, and
ÇatalyürekDevine et al2006]
authorpersonKaren D. Devine, personErik G.
Boman, personRobert T. Heaphy, personRob H.
Bisseling, and personÜmit V. Çatalyürek.
Parallel Hypergraph Partitioning for Scientific
Computing. In booktitle20th International Parallel and
Distributed Processing Symposium (IPDPS). publisherIEEE.

[Dolan and MoréDolan and
authorpersonElizabeth D. Dolan and
personJorge J. Moré. year2002.
Benchmarking Optimization Software with
Performance Profiles.
journalMathematical Programming
volume91, number2 (year2002),

authorpersonAndreas E. Feldmann.
Fast Balanced Partitioning is Hard Even On Grids
and Trees.
journalTheoretical Computer Science
volume485 (year2013), pages61–68.

[Fiduccia and MattheysesFiduccia and
authorpersonCharles M. Fiduccia and
personRobert M. Mattheyses. year1982.
A Linear-Time Heuristic for Improving Network
Partitions. In booktitle19th Conference on Design
Automation (DAC). pages175–181.

[Ford and FulkersonFord and
authorpersonLester Randolph Ford and
personDelbert R Fulkerson. year1956.
Maximal Flow Through a Network.
journalCanadian Journal of Mathematics
volume8 (year1956), pages399–404.

[Funke, Lamm, Sanders, Schulz, Strash, and von
LoozFunke et al2018]
authorpersonD. Funke, personS. Lamm,
personP. Sanders, personC. Schulz,
personD. Strash, and personM. von Looz.
Communication-free Massively Distributed Graph
Generation. In booktitle32nd International Parallel and
Distributed Processing Symposium (IPDPS). pages336–347.

[Garey and JohnsonGarey and Johnson1979]
authorpersonMichael R. Garey and
personDavid S. Johnson. year1979.
booktitleComputers and Intractability: A Guide to
the Theory of NP-Completeness. Vol. volume174.
publisherW. H. Freeman.

[Garey, Johnson, and StockmeyerGarey
et al1976]
authorpersonMichael R. Garey, personDavid S.
Johnson, and personLarry J. Stockmeyer.
Some Simplified NP-Complete Graph Problems.
journalTheoretical Computer Science
volume1, number3 (year1976),

[Goldberg and TarjanGoldberg and
authorpersonAndrew V. Goldberg and
personRobert Endre Tarjan. year1988.
A New Approach to the Maximum-Flow Problem.
journalJournal of the ACM (JACM)
volume35, number4 (year1988),

[Gottesbüren and
HamannGottesbüren and Hamann2022]
authorpersonLars Gottesbüren and
personMichael Hamann. year2022.
Deterministic Parallel Hypergraph Partitioning.
In booktitleEuropean Conference on Parallel Processing
(Euro-Par), Vol. volume13440. publisherSpringer,

[Gottesbüren, Hamann, Schlag, and
WagnerGottesbüren et al2020]
authorpersonLars Gottesbüren,
personMichael Hamann, personSebastian Schlag, and
personDorothea Wagner. year2020.
Advanced Flow-Based Multilevel Hypergraph
journal18th International Symposium on Experimental
Algorithms (SEA) (year2020).

[Gottesbüren, Hamann, and
WagnerGottesbüren et al2019]
authorpersonLars Gottesbüren,
personMichael Hamann, and personDorothea Wagner.
Evaluation of a Flow-Based Hypergraph
Bipartitioning Algorithm. In booktitle27th European
Symposium on Algorithms (ESA). pages52:1–52:17.

[Gottesbüren, Heuer, and
SandersGottesbüren et al2022]
authorpersonLars Gottesbüren,
personTobias Heuer, and personPeter Sanders.
Parallel Flow-Based Hypergraph Partitioning. In
booktitle20th International Symposium on Experimental
Algorithms (SEA) (seriesLIPIcs),
Vol. volume233. publisherSchloss Dagstuhl –
Leibniz-Zentrum für Informatik, addressDagstuhl, Germany,

[Gottesbüren, Heuer, Sanders, and
SchlagGottesbüren et al2022]
authorpersonLars Gottesbüren,
personTobias Heuer, personPeter Sanders, and
personSebastian Schlag. year2022.
Shared-Memory $n$-level Hypergraph Partitioning.
In booktitle24th Workshop on Algorithm Engineering &
Experiments (ALENEX). publisherSIAM, pages131–144.

[Gottesbüren, Heuer, Sanders, Schulz, and
SeemaierGottesbüren et al2021]
authorpersonLars Gottesbüren,
personTobias Heuer, personPeter Sanders,
personChristian Schulz, and personDaniel Seemaier.
Deep Multilevel Graph Partitioning. In
booktitle29th European Symposium on Algorithms (ESA)
(seriesLIPIcs), Vol. volume204.
publisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik,

authorpersonLars Gottesbüren.
titleParallel and Flow-Based High-Quality
Hypergraph Partitioning.
thesistypePh.D. Dissertation. schoolKarlsruhe
Institute of Technology.

[Gottesbüren, Heuer, Sanders, and
SchlagGottesbüren et al2021]
authorpersonLars Gottesbüren, personTobias
Heuer, personPeter Sanders, and personSebastian
Schlag. year2021.
Scalable Shared-Memory Hypergraph Partitioning. In
booktitle23rd Workshop on Algorithm Engineering &
Experiments (ALENEX). publisherSIAM, pages16–30.

[Gray and KourtisGray and Kourtis2021]
authorpersonJohnnie Gray and
personStefanos Kourtis. year2021.
Hyper-Optimized Tensor Network Contraction.
journalQuantum  volume5
(year2021), pages410.

[Hagen, Huang, and KahngHagen
et al1997]
authorpersonLars W. Hagen,
personDennis J.-H. Huang, and personAndrew B.
Kahng. year1997.
On Implementation Choices for Iterative
Improvement Partitioning Algorithms.
journalIEEE Transactions on Computer-Aided Design of
Integrated Circuits & Systems volume16, number10
(year1997), pages1199–1205.

[Hamann and StrasserHamann and
authorpersonMichael Hamann and personBen
Strasser. year2018.
Graph Bisection with Pareto Optimization.
journalACM Journal of Experimental Algorithmics
(JEA)  volume23 (year2018).

[Hamann, Strasser, Wagner, and ZeitzHamann
et al2018]
authorpersonMichael Hamann, personBen
Strasser, personDorothea Wagner, and personTim
Zeitz. year2018.
Distributed Graph Clustering Using Modularity and
Map Equation. In booktitleEuropean Conference on Parallel
Processing (Euro-Par). pages688–702.

[Hauck and BorrielloHauck and
authorpersonScott Hauck and personGaetano
Borriello. year1995.
An Evaluation of Bipartitioning Techniques. In
booktitle16th Conference on Advanced Research in VLSI
(ARVLSI). pages383–403.

[Hendrickson and LelandHendrickson and
authorpersonBruce Hendrickson and
personRobert W. Leland. year1995.
A Multi-Level Algorithm For Partitioning Graphs.
In booktitleSupercomputing. publisherACM,

[Henzinger, Noe, and SchulzHenzinger
et al2020]
authorpersonAlexandra Henzinger,
personAlexander Noe, and personChristian Schulz.
ILP-Based Local Search for Graph Partitioning.
journalACM Journal of Experimental Algorithmics
(JEA)  volume25 (year2020), pages1–26.

authorpersonTobias Heuer.
titleEngineering Initial Partitioning Algorithms
for direct $k$-way Hypergraph Partitioning.
Bachelor Thesis. schoolKarlsruhe Institute of Technology.

authorpersonTobias Heuer.
titleHigh Quality Hypergraph Partitioning via
Max-Flow-Min-Cut Computations.
Master Thesis. schoolKarlsruhe Institute of Technology.

authorpersonTobias Heuer.
titleScalable High-Quality Graph and Hypergraph
thesistypePh.D. Dissertation. schoolKarlsruhe
Institute of Technology.

[Heuer, Maas, and SchlagHeuer
et al2021]
authorpersonTobias Heuer, personNikolai
Maas, and personSebastian Schlag.
Multilevel Hypergraph Partitioning with Vertex
Weights Revisited. In booktitle19th International
Symposium on Experimental Algorithms (SEA)
(seriesLIPIcs), Vol. volume190.
publisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik,

[Heuer, Sanders, and SchlagHeuer
et al2019]
authorpersonTobias Heuer, personPeter
Sanders, and personSebastian Schlag.
Network Flow-Based Refinement for Multilevel
Hypergraph Partitioning.
journalACM Journal of Experimental Algorithmics
(JEA) volume24, number1 (date09
year2019), pages2.3:1–2.3:36.

[Heuer and SchlagHeuer and Schlag2017]
authorpersonTobias Heuer and
personSebastian Schlag. year2017.
Improving Coarsening Schemes for Hypergraph
Partitioning by Exploiting Community Structure. In
booktitle16th International Symposium on Experimental
Algorithms (SEA). publisherSchloss Dagstuhl – Leibniz-Zentrum
für Informatik, pages21:1–21:19.

[Holtgrewe, Sanders, and SchulzHoltgrewe
et al2010]
authorpersonManuel Holtgrewe, personPeter
Sanders, and personChristian Schulz.
Engineering a Scalable High Quality Graph
Partitioner. In booktitle24th International Parallel and
Distributed Processing Symposium (IPDPS). publisherIEEE,

[Hu and MoerderHu and Moerder1985]
authorpersonT. C. Hu and personK.
Moerder. year1985.
Multiterminal Flows in a Hypergraph.
In booktitleVLSI Circuit Layout: Theory and
Design. publisherIEEE, Chapter 3, pages87–93.

[Kabiljo, Karrer, Pundir, Pupyrev, Shalita,
Akhremtsev, and PrestaKabiljo et al2017]
authorpersonIgor Kabiljo, personBrian
Karrer, personMayank Pundir, personSergey Pupyrev,
personAlon Shalita, personYaroslav Akhremtsev, and
personAlessandro Presta. year2017.
Social Hash Partitioner: A Scalable Distributed
Hypergraph Partitioner.
journalProceedings of the VLDB Endowment
volume10, number11 (year2017),

[Kara and ÖzturanKara and
authorpersonGökçehan Kara and
personCan C. Özturan. year2019.
Graph Coloring Based Parallel Push-relabel
Algorithm for the Maximum Flow Problem.
journalACM Trans. Math. Software
volume45, number4 (year2019),

authorpersonGeorge Karypis.
Multilevel Hypergraph Partitioning.
In booktitleMultilevel Optimization in VLSICAD.
publisherSpringer, pages125–154.

[Karypis, Aggarwal, Kumar, and ShekharKarypis
et al1999]
authorpersonGeorge Karypis, personRajat
Aggarwal, personVipin Kumar, and personShashi
Shekhar. year1999.
Multilevel Hypergraph Partitioning: Applications
in VLSI Domain.
journalIEEE Transactions on Very Large Scale
Integration (VLSI) Systems volume7, number1
(year1999), pages69–79.

[Karypis and KumarKarypis and Kumar1996]
authorpersonGeorge Karypis and personVipin
Kumar. year1996.
Parallel Multilevel $k$-way Partitioning Scheme
for Irregular Graphs. In booktitleACM/IEEE Conference on
Supercomputing. pages35.

[Karypis and KumarKarypis and Kumar1998a]
authorpersonGeorge Karypis and personVipin
Kumar. year1998a.
A Fast and High Quality Multilevel Scheme for
Partitioning Irregular Graphs.
journalSIAM Journal on Scientific Computing
volume20, number1 (year1998),

[Karypis and KumarKarypis and Kumar1998b]
authorpersonGeorge Karypis and personVipin
Kumar. year1998b.
Multilevel $k$-way Partitioning Scheme for
Irregular Graphs.
journalJ. Parallel and Distrib. Comput.
volume48, number1 (year1998),

[Karypis and KumarKarypis and Kumar2000]
authorpersonGeorge Karypis and personVipin
Kumar. year2000.
Multilevel k-way Hypergraph Partitioning.
journalVLSI Design volume2000,
number3 (year2000), pages285–300.

authorpersonAlexander V. Karzanov.
Determining the Maximal Flow in a Network by the
Method of Preflows. In booktitleSoviet Mathematics
Doklady, Vol. volume15. pages434–437.

[Kayaaslan, Pinar, Çatalyürek, and
AykanatKayaaslan et al2012]
authorpersonEnver Kayaaslan, personAli
Pinar, personÜmit V. Çatalyürek, and
personCevdet Aykanat. year2012.
Partitioning Hypergraphs in Scientific Computing
Applications through Vertex Separators on Graphs.
journalSIAM Journal on Scientific Computing
volume34, number2 (year2012).

[Kernighan and LinKernighan and Lin1970]
authorpersonBrian W. Kernighan and
personShen Lin. year1970.
An Efficient Heuristic Procedure for Partitioning
journalThe Bell System Technical Journal
volume49, number2 (date2
year1970), pages291–307.

[Khorasani, Gupta, and BhuyanKhorasani
et al2015]
authorpersonFarzad Khorasani, personRajiv
Gupta, and personLaxmi N. Bhuyan.
Scalable SIMD-Efficient Graph Processing on
GPUs. In booktitleInternational Conference on Parallel
Architectures and Compilation (PACT). pages39–50.

[Kumar, Quamar, Deshpande, and KhullerKumar
et al2014]
authorpersonK. Ashwin Kumar, personAbdul
Quamar, personAmol Deshpande, and personSamir
Khuller. year2014.
SWORD: Workload-Aware Data Placement and Replica
Selection for Cloud Data Management Systems.
journalThe VLDB Journal volume23,
number6 (year2014), pages845–870.

[Laboratory of Web AlgorithmsLaboratory of
Web Algorithms[n.d.]]
authorpersonUniversity of Milano Laboratory of
Web Algorithms. year[n.d.].

[Larsson TräffLarsson Träff2006]
authorpersonJesper Larsson Träff.
Direct graph $k$-partitioning with a
Kernighan–Lin like heuristic.
journalOperations Research Letters
volume34, number6 (dateNov.
year2006), pages621–629.

[Lasalle and KarypisLasalle and
authorpersonDominique Lasalle and
personGeorge Karypis. year2013.
Multi-Threaded Graph Partitioning. In
booktitle27th International Parallel and Distributed
Processing Symposium (IPDPS). pages225–236.

[LaSalle and KarypisLaSalle and
authorpersonDominique LaSalle and
personGeorge Karypis. year2016.
A Parallel Hill-Climbing Refinement Algorithm for
Graph Partitioning. In booktitle45th International
Conference on Parallel Processing (ICPP). pages236–241.

[LaSalle, Patwary, Satish, Sundaram, Dubey, and
KarypisLaSalle et al2015]
authorpersonDominique LaSalle, personMd.
Mostofa Ali Patwary, personNadathur Satish,
personNarayanan Sundaram, personPradeep Dubey, and
personGeorge Karypis. year2015.
Improving Graph Partitioning For Modern Graphs and
Architectures. In booktitle5th Workshop on Irregular
Applications - Architectures and Algorithms IA3.

authorpersonEugene L. Lawler.
Cutsets and Partitions of Hypergraphs.
journalNetworks volume3,
number3 (year1973), pages275–285.

authorpersonEdward A. Lee.
The Problem with Threads.
journalComputer volume39,
number5 (year2006), pages33–42.

authorpersonThomas Lengauer.
booktitleCombinatorial Algorithms for Integrated
Circuit Layout.
publisherJohn Wiley & Sons.

[Leskovec and KrevlLeskovec and
authorpersonJ. Leskovec and personA.
Krevl. year2014.
titleSNAP Datasets: Stanford Large Network Dataset

[Maleki, Agarwal, Burtscher, and
PingaliMaleki et al2021]
authorpersonSepideh Maleki, personUdit
Agarwal, personMartin Burtscher, and personKeshav
Pingali. year2021.
BiPart: A Parallel and Deterministic Hypergraph
Partitioner. In booktitle26th ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming (PPoPP).

[Mann and PappMann and Papp2014]
authorpersonZoltán Á. Mann and
personPál A. Papp. year2014.
Formula Partitioning Revisited. In
booktitle5th Pragmatics of SAT Workshop.

authorpersonHenning Meyerhenke.
Shape Optimizing Load Balancing for MPI-Parallel
Adaptive Numerical Simulations. In booktitleGraph
Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge
Workshop. pages67–82.

[Meyerhenke, Monien, and SauerwaldMeyerhenke
et al2008]
authorpersonHenning Meyerhenke,
personBurkhard Monien, and personThomas Sauerwald.
A New Diffusion-Based Multilevel Algorithm for
Computing Graph Partitions of Very High Quality. In
booktitle22nd International Parallel and Distributed
Processing Symposium (IPDPS). publisherIEEE,

[Meyerhenke, Monien, and SauerwaldMeyerhenke
et al2009]
authorpersonHenning Meyerhenke,
personBurkhard Monien, and personThomas Sauerwald.
A New Diffusion-Based Multilevel Algorithm for
Computing Graph Partitions.
journalJournal of Parallel Distributed Computing
volume69, number9 (year2009),

[Meyerhenke, Sanders, and SchulzMeyerhenke
et al2017]
authorpersonHenning Meyerhenke, personPeter
Sanders, and personChristian Schulz.
Parallel Graph Partitioning for Complex
journalIEEE Transactions on Parallel and
Distributed Systems volume28, number9
(year2017), pages2625–2638.

[Newman and GirvanNewman and Girvan2004]
authorpersonMark E. J. Newman and
personMichelle Girvan. year2004.
Finding and Evaluating Community Structure in
journalPhysical Review  volume69
(date2 year2004).
Issue 2.

[Osipov and SandersOsipov and
authorpersonVitaly Osipov and personPeter
Sanders. year2010.
$n$-Level Graph Partitioning. In
booktitle18th European Symposium on Algorithms (ESA).
Springer, pages278–289.

[Papa and MarkovPapa and Markov2007]
authorpersonDavid A. Papa and
personIgor L. Markov. year2007.
Hypergraph Partitioning and Clustering.
In booktitleHandbook of Approximation Algorithms and

[Pellegrini and RomanPellegrini and
authorpersonFrançois Pellegrini and
personJean Roman. year1996.
SCOTCH: A Software Package for Static Mapping
by Dual Recursive Bipartitioning of Process and Architecture Graphs. In
booktitleHigh-Performance Computing and Networking (HPCN),
Vol. volume1067. publisherSpringer,

authorpersonChuck Pheatt.
Intel Threading Building Blocks.
journalJournal of Computing Sciences in Colleges
volume23, number4 (year2008),

[Picard and QueyrannePicard and
authorpersonJean-Claude Picard and
personMaurice Queyranne. year1980.
On the Structure of All Minimum Cuts in a Network
and Applications.
journalCombinatorial Optimization II
(year1980), pages8–16.

authorpersonR. A. Rutman.
An Algorithm for Placement of Interconnected
Elements Based on Minimum Wire Length. In booktitleSpring
Joint Computer Conference of the American Federation of Information
Processing Societies (AFIPS). publisherACM,

authorpersonYoussef Saab.
A Fast and Robust Network Bisection Algorithm.
journalIEEE Trans. Comput. volume44,
number7 (year1995), pages903–913.

authorpersonLaura A. Sanchis.
Multiple-Way Network Partitioning.
journalIEEE Trans. Comput. volume38,
number1 (year1989), pages62–81.

[Sanders and SchulzSanders and
authorpersonPeter Sanders and
personChristian Schulz. year2011.
Engineering Multilevel Graph Partitioning
Algorithms. In booktitle19th European Symposium on
Algorithms (ESA). publisherSpringer, pages469–480.

[Sanders and SchulzSanders and
authorpersonPeter Sanders and
personChristian Schulz. year2012.
Distributed Evolutionary Graph Partitioning. In
booktitle12th Workshop on Algorithm Engineering &
Experiments (ALENEX). pages16–29.

[Savage and WlokaSavage and Wloka1991]
authorpersonJohn E. Savage and
personMarkus G. Wloka. year1991.
Parallelism in Graph-Partitioning.
journalJ. Parallel and Distrib. Comput.
volume13, number3 (year1991),

authorpersonSebastian Schlag.
titleHigh-Quality Hypergraph Partitioning.
thesistypePh.D. Dissertation. schoolKarlsruhe
Institute of Technology.

[Schlag, Henne, Heuer, Meyerhenke, Sanders, and
SchulzSchlag et al2016]
authorpersonSebastian Schlag, personVitali
Henne, personTobias Heuer, personHenning Meyerhenke,
personPeter Sanders, and personChristian Schulz.
$k$-way Hypergraph Partitioning via $n$-Level
Recursive Bisection. In booktitle18th Workshop on
Algorithm Engineering & Experiments (ALENEX). SIAM,

[Schlag, Heuer, Gottesbüren, Akhremtsev,
Schulz, and SandersSchlag et al2022]
authorpersonSebastian Schlag, personTobias
Heuer, personLars Gottesbüren, personYaroslav
Akhremtsev, personChristian Schulz, and personPeter
Sanders. year2022.
High-Quality Hypergraph Partitioning.
journalACM Journal of Experimental Algorithmics
(JEA) (datemar year2022).

Just Accepted.

authorpersonC. Schulz.
titleHigh Quality Graph Partitioning.
thesistypePh.D. Dissertation. schoolKarlsruhe
Institute of Technology.

[Schweikert and KernighanSchweikert and
authorpersonDaniel G. Schweikert and
personBrian W. Kernighan. year1972.
A Proper Model for the Partitioning of Electrical
Circuits. In booktitle9th Conference on Design Automation
(DAC). publisherACM, pages57–62.

[Serafini, Taft, Elmore, Pavlo, Aboulnaga, and
StonebrakerSerafini et al2016]
authorpersonMarco Serafini, personRebecca
Taft, personAaron J Elmore, personAndrew Pavlo,
personAshraf Aboulnaga, and personMichael
Stonebraker. year2016.
Clay: Fine-Grained Adaptive Partitioning for
General Database Schemas.
journalProceedings of the VLDB Endowment
volume10, number4 (year2016),

[Shiloach and VishkinShiloach and
authorpersonYossi Shiloach and personUzi
Vishkin. year1982.
An $\mathcal{O}(n^2 \log{n})$ Parallel Max-Flow
journalJournal of Algorithms volume3,
number2 (year1982), pages128–146.

[Staudt and MeyerhenkeStaudt and
authorpersonChristian L. Staudt and
personHenning Meyerhenke. year2016.
Engineering Parallel Algorithms for Community
Detection in Massive Networks.
journalIEEE Transactions on Parallel and Distributed
Systems volume27, number1 (date01
year2016), pages171–184.

authorpersonGuy L. Steele.
Making Asynchronous Parallelism Safe for the
World. In booktitlePOPL 90,
editorpersonFrances E. Allen (Ed.).
publisherACM Press, pages218–231.

[Trifunovic and KnottenbeltTrifunovic and
authorpersonAleksandar Trifunovic and
personWilliam J. Knottenbelt. year2004a.
Parkway 2.0: A Parallel Multilevel Hypergraph
Partitioning Tool. In booktitle19th International
Symposium on Computer and Information Sciences (ISCIS),
Vol. volume3280. publisherSpringer,

[Trifunovic and KnottenbeltTrifunovic and
authorpersonAleksandar Trifunovic and
personWilliam J. Knottenbelt. year2004b.
Towards a Parallel Disk-Based Algorithm for
Multilevel $k$-way Hypergraph Partitioning. In
booktitle18th International Parallel and Distributed
Processing Symposium (IPDPS).

[Vastenhouw and BisselingVastenhouw and
authorpersonBrendan Vastenhouw and
personRob H. Bisseling. year2005.
A Two-Dimensional Data Distribution Method for
Parallel Sparse Matrix-Vector Multiplication.
journalSIAM Rev. volume47,
number1 (year2005), pages67–95.

[Viswanathan, Alpert, Sze, Li, and
WeiViswanathan et al2012]
authorpersonNatarajan Viswanathan,
personCharles J. Alpert, personCliff C. N. Sze,
personZhuo Li, and personYaoguang Wei.
The DAC 2012 Routability-Driven Placement Contest
and Benchmark Suite. In booktitle49th Conference on Design
Automation (DAC). publisherACM, pages774–782.

authorpersonC. Walshaw.
booktitleAn Exploration of Multilevel Combinatorial
publisherSpringer, pages71–124.

authorpersonC. Walshaw.
Multilevel Refinement for Combinatorial
Optimisation Problems.
journalAnnals of Operations Research
volume131, number1–4 (year2004),

[Walshaw and CrossWalshaw and Cross2000a]
authorpersonChris Walshaw and personMark
Cross. year2000a.
Mesh Partitioning: A Multilevel Balancing and
Refinement Algorithm.
journalSIAM Journal on Scientific Computing
volume22, number1 (year2000),

[Walshaw and CrossWalshaw and Cross2000b]
authorpersonChris Walshaw and personMark
Cross. year2000b.
Parallel Optimisation Algorithms for Multilevel
Mesh Partitioning.
journalParallel Comput. volume26,
number12 (year2000), pages1635–1660.

[Walshaw, Cross, and EverettWalshaw
et al1997]
authorpersonChris Walshaw, personMark
Cross, and personMartin G. Everett.
Parallel Dynamic Graph Partitioning for Adaptive
Unstructured Meshes.
journalJ. Parallel and Distrib. Comput.
volume47, number2 (year1997),

authorpersonFrank Wilcoxon.
Individual Comparisons by Ranking Methods.
In booktitleBreakthroughs in Statistics.
publisherSpringer, pages196–202.

[Williams, Oliker, Vuduc, Shalf, Yelick, and
DemmelWilliams et al2007]
authorpersonSamuel Williams, personLeonid
Oliker, personRichard W. Vuduc, personJohn Shalf,
personKatherine A. Yelick, and personJames Demmel.
Optimization of Sparse Matrix-Vector Multiplication
on Emerging Multicore Platforms. In booktitleInternational
Conference for High Performance Computing, Networking, Storage and Analysis
(SC). publisherACM Press, pages38.

[Yang and WongYang and Wong1996]
authorpersonHannah H. Yang and personD. F.
Wong. year1996.
Efficient Network Flow Based Min-Cut Balanced
journalIEEE Transactions on Computer-Aided Design of
Integrated Circuits & Systems volume15, number12
(year1996), pages1533–1540.

[Yang, Wang, Choo, and ChenYang
et al2018]
authorpersonWenyin Yang, personGuojun Wang,
personKim-Kwang Raymond Choo, and personShuhong
Chen. year2018.
HEPart: A Balanced Hypergraph Partitioning
Algorithm for Big Data Applications.
journalFuture Generation Computer Systems
volume83 (year2018), pages250–268.

[Yu and PanYu and Pan2015]
authorpersonBoyang Yu and personJianping
Pan. year2015.
Location-Aware Associated Data Placement for
Geo-Distributed Data-Intensive Applications. In
booktitleIEEE Conference on Computer Communications
(INFOCOM). IEEE, pages603–611.

§ COMPARISON TO OTHER SYSTEMS

Performance profiles and running times comparing PaToH-D and
Mondriaan on .

Performance profiles and running times comparing KaHyPar-CA and
hMetis on .

Performance profiles and running times comparing $r$KaHyPar and
$k$KaHyPar on .

Performance profiles and running times comparing Metis-R and
Metis-K on .

Performance profiles and running times comparing Metis-K and
KaFFPa-Fast/-FastS on .

Performance profiles and running times comparing Metis-K and
Scotch on .

Performance profiles and running times comparing KaFFPa-Eco and
KaFFPa-EcoS on .

Performance profiles and running times comparing Zoltan and
BiPart on .

Performance profiles and running times comparing KaMinPar to
Mt-Metis and ParMetis on .

Performance profiles and running times comparing KaMinPar to
ParHIP-Fast on .

Performance profiles and running times comparing Mt-KaHIP to
ParHIP-Eco on .

Performance profiles and running times comparing Mt-KaHyPar-S (Speed, Mt-KaHyPar-D without FM refinement) to
Metis-K on .


# Gaussian inequality

Tewodros Amdeberhan and David Callan  Department of Mathematics, Tulane
University, New Orleans, LA 70118, USA<EMAIL_ADDRESS>Department of
Statistics, University of Wisconsin-Madison, Madison, WI 53715, USA
<EMAIL_ADDRESS>
###### Abstract.

We prove some special cases of Bergeron’s inequality involving two Gaussian
polynomials (or $q$-binomials).

###### 2010 Mathematics Subject Classification:

11B65, 11A07.

##  1\. Introduction

We begin by recalling the $q$-analogues
$[n]!_{q}=\prod_{j=1}^{n}\frac{1-q^{j}}{1-q}$ of factorials and the
$q$-analogue $\binom{n}{k}_{q}=\frac{[n]!_{q}}{[k]!_{q}[n-k]!_{q}}$ of
binomial coefficients. Adopt the convention $[0]!_{q}=1$. It is well-known
that these rational functions $\binom{n}{k}_{q}$ are polynomials, in $q$, also
called _Gaussian polynomials_ , having non-negative coefficients which are
also _unimodal_ and symmetric. Furthermore, there are several combinatorial
interpretations of which we state two of them.

A _word_ of length $n$ over the _alphabet_ set $\\{0,1\\}$ is a finite
sequence $w=a_{1}\cdots a_{n}$. Construct

$\mathcal{W}_{n,k}=\\{w=a_{1}\cdots a_{n}:\text{$w$ has $k$ zeros and $n-k$
ones}\\}$

and the _inversion set_ of $w$ as $\text{Inv}(w)=\\{(i,j):\text{$i<j$ and
$a_{i}>a_{j}$}\\}$. The corresponding _inversion number_ of $w$ will be
denoted $\text{inv}(w)=\\#\text{Inv}(w)$. Then, we have

$\binom{n}{k}_{q}=\sum_{w\in\mathcal{W}_{n,k}}q^{\text{inv}(w)}.$

Yet, another formulation which would come to appeal to many combinatorialists
is

$\binom{a+d}{a}_{q}=\sum_{T}q^{area(T)}$

where $T$ is a lattice path inside an $a\times d$ box and $area(T)$ is area
above the curve $T$.

Given two polynomials $f(q)$ and $g(q)$, we write $f(q)\geq g(q)$ provided
that $f(q)-g(q)$ has non-negative coefficients in the powers of $q$.

The well-known _Foulkes conjecture_ (see, for instance [4]) was generalized by
Vessenes [8]. She conjectured that

$\displaystyle(h_{b}\circ h_{c})-(h_{a}\circ h_{d})$ (1)

is _Schur positive_ (expands with positive integer coefficients in the Schur
basis $\\{s_{\mu}\\}_{\mu\vdash n}$ of symmetric polynomials) whenever $a\leq
b<c\leq d$, with $n=ad=bc$, and one writes $(h_{n}\circ h_{k})$ for the
_plethysm_ of complete homogeneous symmetric functions. A well-known fact is
that $(h_{n}\circ h_{k})(1,q)=\binom{n+k}{k}_{q}$. Moreover, any non-zero
evaluation of a Schur function at $1$ and $q$ is of the form
$q^{i}+q^{i+1}+\dots+q^{j}$ for some $i<j$. Exploiting these facts on the
occasion of [3], and assuming that (1) holds, F. Bergeron (see also [4])
underlined that the evaluation of the difference in (1), at $1$ and $q$, would
imply the following:

######  Conjecture 1.

Assume $0<a\leq b<c\leq d$ are positive integers with $ad=bc$. Then, the
following difference of two Gaussian polynomials is symmetric and satisfies

$\displaystyle\binom{b+c}{b}_{q}-\binom{a+d}{a}_{q}\geq 0.$ (2)

One can associate a direct combinatorial meaning to Vessenes’ conjecture in
the context of representation theory of $GL(V)$. Indeed, if it holds true, it
would signify that there is an embedding of the composite of symmetric powers
$S^{a}(S^{d}(V))$ inside $S^{b}(S^{c}(V))$, as $GL(V)$-modules. It may however
be more natural to state that there is a surjective $GL(V)$-module morphism
the other way around (which is also equivalent). Therefore each
$GL(V)$-irreducible occurs with smaller multiplicity in $S^{a}(S^{d}(V))$ than
it does in $S^{b}(S^{c}(V))$, and the conjecture reflects this at the level of
the corresponding characters (with Schur polynomials appearing as characters
of irreducible representations).

The sole attempt [9] toward resolving Conjecture 1 was made by F. Zanello, who
attends to the special case $a\leq 3$, including the property of symmetry and
unimodality. A sequence of numbers is _unimodal_ if it does not increase
strictly after a strict decrease. The author in [9] offers a strengthening of
Conjecture 1 to the effect that

######  Conjecture 2.

Preserve the hypothesis in Conjecture 1. Then, the coefficients of the
symmetric polynomial

$\displaystyle\binom{b+c}{b}_{q}-\binom{a+d}{a}_{q}$

are non-negative and unimodal.

Notice that symmetry is clear, since both $\binom{b+c}{b}_{q}$ and
$\binom{a+d}{a}_{q}$ are symmetric polynomials of the same degree, $ad=bc$. We
started out this project with the goal of proving the below $3$-parameter
special case of Conjecture 1 which we dubbed the _$\beta$ -Conjecture_.
Namely,

######  Conjecture 3.

For integers $0<a<b$ and $\beta\geq 1$, we have

$\displaystyle\binom{b+\beta a}{b}_{q}\geq\binom{a+\beta b}{a}_{q}.$ (3)

The case $\beta=1$ is trivial. However, our journey in this effort failed
short of capturing the $\beta$-Conjecture in its fullest. In the sequel, we
supply the details of our success in settling the particular instance
$\beta=2$. Let’s commence by stating one useful identity.

######  Theorem 1.

($q$-analogue Vandermonde-Chu). The following holds true

$\displaystyle\sum_{j\geq
0}\binom{X}{Z-j}_{q}\binom{Y}{j}_{q}q^{j(X-Z+j)}=\binom{X+Y}{Z}_{q}.$ (4)

######  Remark 2.

In view of (4), Conjecture 1 tantamount

$\displaystyle\binom{b+c}{b}_{q}=\sum_{k=0}^{\boldsymbol{b}}\binom{b}{k}_{q}\binom{c}{k}_{q}q^{k^{2}}\geq\sum_{k=0}^{\boldsymbol{a}}\binom{a}{k}_{q}\binom{d}{k}_{q}q^{k^{2}}=\binom{a+d}{a}_{q}.$

##  2\. THE CASE $\beta=2$ and $q=1$

In this section, we wish to explain the resolution of the $\beta$-Conjecture
for the ordinary binomial coefficients ($q=1$) while $\beta=2$, which
elaborates a natural development.

For $a<b<c<d$ with $ad=bc$ and special case $c=2a,d=2b$, say $b=a+i,\,i\geq
1$, it would be desirable to find a bijective proof for

$\binom{3a+i}{a+i}\geq\binom{3a+2i}{a}\,.$

An injection from a set counted by the smaller number to one counted by the
larger number would be nice but a better proof would be an expression for the
difference as a sum of obviously positive terms. For $i=1$, we have

$\binom{3a+1}{a+1}-\binom{3a+2}{a}=\binom{3a+1}{a-1}\,,$

and the right-hand side is clearly positive. It seems for general
$i=1,2,\dots,$

$\binom{3a+i}{a+i}-\binom{3a+2i}{a}=\sum_{k=1}^{i}c_{k}(i)\binom{3a+i}{a-k}$

for integers $c_{k}(i)$ and, furthermore, the $c_{k}(i)$ _are all positive_.
Here is a table for $c_{k}(i)$ when $1\leq k\leq i\leq 8$:

$\begin{array}[]{cccccccc}1&\text{}&\text{}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
3&1&\text{}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
6&6&1&\text{}&\text{}&\text{}&\text{}&\text{}\\\
10&19&9&1&\text{}&\text{}&\text{}&\text{}\\\
15&45&39&12&1&\text{}&\text{}&\text{}\\\ 21&90&120&66&15&1&\text{}&\text{}\\\
28&161&301&250&100&18&1&\text{}\\\ 36&266&658&755&450&141&21&1\\\ \end{array}$

but appeared hard to get a handle on them. The evolution of our next progress
begins with the discovery of

$c_{k}(i)=\binom{i+k-1}{2k}+2\binom{i+k-1}{2k-1}-\binom{i}{k}.$

Let’s contract these coefficients as
$c_{k}(i)=\frac{i+3k}{i+k}\binom{i+k}{2k}-\binom{i}{k}$, for $i,k\geq 1$.
Notice $c_{0}(i)=0$. We need some preliminary results.

######  Lemma 1.

We have

$\binom{3a+2i}{a}=\sum_{k\geq 0}\binom{i}{k}\binom{3a+i}{a-k}.$

###### Proof.

This follows from the Vandermonde-Chu identity (Theorem 1 for $q=1$)

$\binom{X+Y}{Z}=\sum_{k\geq 0}\binom{X}{k}\binom{Y}{Z-k}$

applied to $\binom{3a+2i}{a}=\binom{i+3a+i}{a}$ with $X=i,Y=3a+i$ and $Z=a$. ∎

######  Lemma 2.

We have

$\binom{3a+i}{a+i}=\sum_{k\geq
0}\frac{i+3k}{i+k}\binom{i+k}{2k}\binom{3a+i}{a-k}=\sum_{k\geq
0}\left[\binom{i+k}{2k}+\binom{i+k-1}{2k-1}\right]\binom{3a+i}{a-k}.$

###### Proof.

We implement Zeilberger’s algorithm (from the Wilf-Zeilberger theory). Define

$F(i,k)=\frac{i+3k}{i+k}\cdot\frac{\binom{i+k}{2k}\binom{3a+i}{a-k}}{\binom{3a+i}{a+i}}\qquad\text{and}\qquad
G(i,k)=-\frac{\binom{i+k-1}{2k-2}\binom{3a+i}{a-k}}{\binom{3a+i}{a+i}}.$

Check that $F(i+1,k)-F(i,k)=G(i,k+1)-G(i,k)$ and sum both sides over all
integer values $k$. Then, notice the right-hand side vanishes and hence we
obtain a sum $\sum_{k}F(i,k)$ that is constant in the variable $i$. Determine
this constant by substituting, say $i=1$,

$\sum_{k=0}^{1}F(1,k)=\frac{\binom{3a+1}{a}}{\binom{3a+1}{a+1}}+\frac{2\binom{3a+1}{a-1}}{\binom{3a+1}{a+1}}=\frac{a+1}{2a+1}+\frac{a}{2a+1}=1.$

Therefore, $\sum_{k}F(i,k)=1$, identically, for all $i\geq 1$. The proof
follows. ∎

We now state the main result of this section.

######  Theorem 3.

We have

$\binom{3a+i}{a+i}-\binom{3a+2i}{a}=\sum_{k\geq
1}\left\\{\frac{i+3k}{i+k}\binom{i+k}{2k}-\binom{i}{k}\right\\}\binom{3a+i}{a-k}.$

###### Proof.

Immediate from Lemma 1 and Lemma 2. ∎

######  Lemma 3.

For $k\geq 1$, the coefficients $c_{k}(i)$ are non-negative.

###### Proof.

We may look at it in two different ways:

(1)
$c_{k}(i)=\frac{2k}{i+k}\binom{i+k}{2k}+\binom{i+k}{2k}-\binom{i}{k}=\frac{2k}{i+k}\binom{i+k}{2k}+\binom{i+k}{i-k}-\binom{i}{i-k}$.
Obviously $\binom{i+k}{i-k}\geq\binom{i}{i-k}$, therefore $c_{k}(i)\geq 0$.

(2)
$c_{k}(i)=\binom{i+k}{2k}+\binom{i+k-1}{2k-1}-\binom{i}{k}=\binom{i+k}{2k}+\sum_{r=0}^{k-2}\binom{i+r}{k+1+r}$
shows clearly that $c_{k}(i)\geq 0$. The identity
$\binom{i+k-1}{2k-1}=\binom{i}{k}+\sum_{r=1}^{k-1}\binom{i+r-1}{k+r}$ results
from a cascading effect of the familiar binomial recurrence
$\binom{u}{v}+\binom{u}{v-1}=\binom{u+1}{v}$. ∎

##  3\.  $q$-ANALOGUES when $\beta=2$

In the present section, we aim to generalize our proofs given in the preceding
section by lifting the argument from the ordinary binomials to Gaussian
polynomials.

######  Lemma 4.

We have

$\binom{3a+2i}{a}_{q}=\sum_{k\geq
0}q^{(a-k)(i-k)}\binom{i}{k}_{q}\binom{3a+i}{a-k}_{q}.$

###### Proof.

This follows from the Vandermonde-Chu identity (Theorem 1)

$\binom{X+Y}{Z}_{q}=\sum_{k\geq
0}q^{(Z-k)(X-k)}\binom{X}{k}_{q}\binom{Y}{Z-k}_{q}$

on $\binom{3a+2i}{a}_{q}=\binom{i+3a+i}{a}_{q}$ with $X=i,Y=3a+i$ and $Z=a$. ∎

######  Lemma 5.

We have

$\displaystyle\binom{3a+i}{a+i}_{q}$ $\displaystyle=\sum_{k\geq
0}q^{(a-k)(i-k)}\left[\binom{i+k}{2k}_{q}+q^{a+i}\binom{i+k-1}{2k-1}_{q}\right]\binom{3a+i}{a-k}_{q}.$

###### Proof.

Let’s rewrite
$\binom{i+k}{2k}_{q}+q^{a+i}\binom{i+k-1}{2k-1}_{q}=\left[1+\frac{q^{a+i}(1-q^{2k})}{1-q^{i+k}}\right]\binom{i+k}{2k}_{q}$
and define the functions

$\displaystyle F(i,k)$
$\displaystyle=q^{(a-k)(i-k)}\left[1+q^{a+i}\cdot\frac{1-q^{2k}}{1-q^{i+k}}\right]\frac{\binom{i+k}{2k}_{q}\binom{3a+i}{a-k}_{q}}{\binom{3a+i}{a+i}_{q}},\qquad\text{and}$
$\displaystyle G(i,k)$
$\displaystyle=-q^{(a-k+1)(i-k+1)}\cdot\frac{\binom{i+k-1}{2k-2}_{q}\binom{3a+i}{a-k}_{q}}{\binom{3a+i}{a+i}_{q}}.$

Divide both sides of the intended identity by $\binom{3a+i}{a+i}_{q}$. Our
goal is to prove $\sum_{k}F(i,k)=1$ by adopting the Wilf-Zeilberger technique.
To this end, calculate the following two ratios

$A(i,k):=\frac{F(i+1,k)}{F(i,k)}-1\qquad\text{and}\qquad
B(i,k):=\frac{G(i,k+1)}{F(i,k)}-\frac{G(i,k)}{F(i,k)}$

resulting in

$\displaystyle A(i,k)$
$\displaystyle=\frac{q^{a-k}(1-q^{i+k})(1-q^{a+i+1})(1-q^{i+k+1}+q^{a+i+1}-q^{a+i+2k+1})}{(1-q^{i-k+1})(1-q^{2a+i+k+1})(1-q^{i+k}+q^{a+i}-q^{a+i+2k})}-1\qquad\text{and}$
$\displaystyle B(i,k)$
$\displaystyle=\left[-\frac{1-q^{a-k}}{1-q^{2a+i+k+1}}+\frac{q^{a+i-2k+1}(1-q^{2k})(1-q^{2k-1})}{(1-q^{i+k})(1-q^{i-k+1})}\right]\cdot\frac{1-q^{i+k}}{1-q^{i+k}+q^{a+i}-q^{a+i+2k}}.$

Verify routinely $A(i,k)=B(i,k)$. Thus $F(i+1,k)-F(i,k)=G(i,k+1)-G(i,k)$. Now,
sum both sides over all integer values $k$. Then, notice that the right-hand
side vanishes and hence we obtain a sum $\sum_{k}F(i,k)$ that is constant in
the variable $i$. Determine this constant by substituting, say $i=1$ and
proceed with some simplifications leading to

$\sum_{k=0}^{1}F(1,k)=q^{a}\cdot\frac{1-q^{a+1}}{1-q^{2a+1}}+\frac{1-q^{a}}{1-q^{2a+1}}=1.$

Therefore, $\sum_{k}F(i,k)=1$, identically, for all $i\geq 1$. The assertion
follows. ∎

######  Lemma 6.

We have the identity

$\displaystyle\binom{i+k}{2k}_{q}=\binom{i}{k}_{q}+\sum_{r=1}^{k}q^{k+r}\binom{i+r-1}{k+r}_{q}.$

###### Proof.

Use the recursive relations
$\binom{a}{b}_{q}=\binom{a-1}{b}_{q}+q^{a-b}\binom{a-1}{b-1}_{q}=q^{b}\binom{a-1}{b}_{q}+\binom{a-1}{b-1}_{q}$.
∎

######  Lemma 7.

We have the inequality $\binom{i+k}{i-k}_{q}\geq\binom{i}{i-k}_{q}$.

###### Proof.

We use the interpretation of the Gaussian polynomials as the _inversion
number_ generating function for all bit strings of length $n$ with $k$ zeroes
and $n-k$ ones, that is

$\binom{n}{k}_{q}=\sum_{w\in\,0^{k}1^{n-k}}q^{\text{inv}(w)}.$

Let $w^{\prime}\in\,0^{i-k}1^{k}\sqcup 1^{k}$ denote a bit where the last $k$
digits are all ones. In this sense, we get

$\displaystyle\binom{i+k}{i-k}_{q}=\sum_{w\in\,0^{i-k}1^{2k}}q^{\text{inv}(w)}$
$\displaystyle=\sum_{w^{\prime}\in\,0^{i-k}1^{k}\sqcup
1^{k}}q^{\text{inv}(w^{\prime})}+\sum_{w^{\prime}\not\in\,0^{i-k}1^{k}\sqcup
1^{k}}q^{\text{inv}(w^{\prime})}$
$\displaystyle=\sum_{w\in\,0^{i-k}1^{k}}q^{\text{inv}(w)}+\sum_{w^{\prime}\not\in\,0^{i-k}1^{k}\sqcup
1^{k}}q^{\text{inv}(w^{\prime})}$
$\displaystyle=\binom{i}{i-k}_{q}+\sum_{w^{\prime}\not\in\,0^{i-k}1^{k}\sqcup
1^{k}}q^{\text{inv}(w^{\prime})}$

where we note that $\text{inv}(w^{\prime})=\text{inv}(w)$ if the word
$w^{\prime}\in\,0^{i-k}1^{k}\sqcup 1^{k}$ is associated with
$w\in\,0^{i-k}1^{k}$ found by dropping the last $k$ ones. The assertion is now
immediate. ∎

We prove the main result of this section and our paper, the $\beta$-Conjecture
for $\beta=2$.

######  Theorem 4.

The polynomial $P(q):=\binom{3a+i}{a+i}_{q}-\binom{3a+2i}{a}_{q}$ has non-
negative coefficients.

###### Proof.

From Lemma 4 and Lemma 5, we infer

$\displaystyle P(q)=\sum_{k\geq
1}q^{(a-k)(i-k)}\left[\binom{i+k}{2k}_{q}+q^{a+i}\binom{i+k-1}{2k-1}-\binom{i}{k}_{q}\right]\binom{3a+i}{a-k}_{q}.$

It suffices to verify positivity of the terms inside the inner parenthesis on
the right-hand side. We may pair up these terms and compliment the lower index
to the effect that

$\displaystyle\binom{i+k}{2k}_{q}-\binom{i}{k}_{q}+q^{a+i}\binom{i+k-1}{2k-1}_{q}=\binom{i+k}{i-k}_{q}-\binom{i}{i-k}_{q}+q^{a+i}\binom{i+k-1}{2k-1}_{q}.$

To reach the conclusion, simply apply Lemma 6 or Lemma 7. ∎

##  4\. Final remarks

In the present section, we close our discussion with one conjecture as a
codicil of certain calculations we encountered while digging up ways to prove
the $\beta$-Conjecture.

######  Conjecture 4.

For each $0\leq k\leq a<b$, we have

$\binom{a}{k}_{q}\binom{a+b}{b-k}_{q}\geq\binom{b}{k}_{q}\binom{a+b}{a-k}_{q}\qquad\text{or}\qquad\binom{a}{k}_{q}\binom{b}{k}_{q}\binom{b+a}{b}_{q}\left[\frac{1}{\binom{a+k}{k}_{q}}-\frac{1}{\binom{b+k}{k}_{q}}\right]\geq
0.$

The next elementary result might be helpful if one decides to engage this
conjecture.

######  Lemma 8.

For $0\leq k\leq a<b$, we have

$\displaystyle\frac{1}{\binom{a+k}{k}_{q}}-\frac{1}{\binom{b+k}{k}_{q}}$
$\displaystyle=\sum_{i=1}^{k}q^{a+i}\frac{1-q^{b-a}}{1-q^{b+i}}\prod_{j=i}^{k}\frac{1-q^{j}}{1-q^{a+j}}\prod_{j=1}^{i-1}\frac{1-q^{j}}{1-q^{b+j}}.$

###### Proof.

This results from partial fractions. ∎

######  Example 1.

$\displaystyle\frac{1}{\binom{a+1}{1}_{q}}-\frac{1}{\binom{b+1}{1}_{q}}$
$\displaystyle=\frac{q^{a+1}(1-q)(1-q^{b-a})}{(1-q^{a+1})(1-q^{b+1})}$
$\displaystyle\frac{1}{\binom{a+2}{2}_{q}}-\frac{1}{\binom{b+2}{2}_{q}}$
$\displaystyle=\frac{q^{a+1}(1-q)(1-q^{2})(1-q^{b-a})}{(1-q^{a+1})(1-q^{a+2})(1-q^{b+1})}+\frac{q^{a+2}(1-q)(1-q^{2})(1-q^{b-a})}{(1-q^{a+2})(1-q^{b+1})(1-q^{b+2})}.$

######  Example 2.

$\displaystyle\frac{1}{\binom{a+3}{3}_{q}}-\frac{1}{\binom{b+3}{3}_{q}}$
$\displaystyle=\frac{q^{a+1}(1-q)(1-q^{2})(1-q^{3})(1-q^{b-a})}{(1-q^{a+1})(1-q^{a+2})(1-q^{a+3})(1-q^{b+1})}$
$\displaystyle+\frac{q^{a+2}(1-q)(1-q^{2})(1-q^{3})(1-q^{b-a})}{(1-q^{a+2})(1-q^{a+3})(1-q^{b+1})(1-q^{b+2})}$
$\displaystyle+\frac{q^{a+3}(1-q)(1-q^{2})(1-q^{3})(1-q^{b-a})}{(1-q^{a+3})(1-q^{b+1})(1-q^{b+2})(1-q^{b+3})}.$

######  Remark 5.

As a side note, we recall that G. E. Andrews [2] expresses
$\binom{n}{k}_{q}-\binom{n}{k-1}_{q}$ as the generating function for
partitions with particular _Frobenius symbols_ , while L. M. Butler [5] does
this with the help of the _Kostka-Foulkes polynomials_ to show non-negativity
of the coefficients. We shall provide an alternative algebraic approach.

######  Lemma 9.

For $0\leq 2k\leq n$, we have $\binom{n}{k}_{q}-\binom{n}{k-1}_{q}\geq 0$.

###### Proof.

Let $n=\alpha k+d$ where $0\leq d<k$. Rewrite

$\displaystyle\binom{n}{k}_{q}-\binom{n}{k-1}_{q}$
$\displaystyle=q^{k}\binom{n}{k-1}_{q}\frac{1-q^{(\alpha-2)k}}{1-q^{k}}+q^{(\alpha-1)k}\binom{n}{k-1}_{q}\frac{1-q^{d+1}}{1-q^{k}}.$

Observe $\frac{1-q^{(\alpha-2)k}}{1-q^{k}}$ is already a polynomial with non-
negative coefficients. Furthermore, since $U(q):=\binom{n}{k-1}_{q}$ is
unimodal [1], [6], [7], the coefficient of $q^{j}$ in $U(q)\cdot(1-q^{d+1})$
is non-negative as long as $2j\leq\deg(U)$. The same is true for
$U(q)\frac{1-q^{d+1}}{1-q^{k}}$ as a formal power series. Since the polynomial
$U(q)\frac{1-q^{d+1}}{1-q^{k}}$ is symmetric, having degree no greater than
$U(q)$, all remaining coefficients of $U(q)\frac{1-q^{d+1}}{1-q^{k}}$ are non-
negative. ∎

## Acknowledgement

The first author thanks R. P. Stanley for bringing Bergeron’s conjecture to
his attention, also F. Bergeron for his generous explanation of the problem
studied in the present work.

## References

  * [1] G. E. Andrews, _A theorem on reciprocal polynomials with applications to permutations and compositions_ , Amer. Math. Monthly 82, no. 8 (1975).
  * [2] G. E. Andrews, _On the difference of successive Gaussian polynomials_ , J. Statist. Plann. Inference 34, no. 1 (1993).
  * [3] F. Bergeron, _The $q$-Foulkes’ Conjecture_, Talk delivered at Bowdoin College, ME, on September 24, (2016).
  * [4] F.Bergeron, _A $q$-analog of Foulkes’ Conjecture_, Electron. J. Combin., 24, no. 1, (2017).
  * [5] L. M. Butler, _A unimodality result in the enumeration of subgroups of a finite abelian group_ , Proc. Amer. Math. Soc. 101, no. 4, (1987).
  * [6] J.W.B. Hughes, J. Van der Jeugt, _Unimodal polynomials associated with Lie algebras and superalgebras_ , J. Computational and Applied Math. 37, (1991).
  * [7] K. B. Stolarsky, _Higher partition functions and their relation to finitely generated nilpotent groups_ , Ph.D. thesis, University of Wisconsin, (1968).
  * [8] R. Vessenes, _Generalized Foulkes’ conjecture and tableaux_ , J. Algebra, 277, (2004).
  * [9] F. Zanello, _On Bergeron’s positivity problem for q-binomial coefficients_ , Electron. J. Combin. 25, no. 2, (2018).