  Given a graph, finding the distance-2 maximal independent set (MIS-2) of the
vertices is a problem that is useful in several contexts such as algebraic
multigrid coarsening or multilevel graph partitioning. Such multilevel methods
rely on finding the independent vertices so they can be used as seeds for
aggregation in a multilevel scheme. We present a parallel MIS-2 algorithm to
improve performance on modern accelerator hardware. This algorithm is
implemented using the Kokkos programming model to enable performance
portability. We demonstrate the portability of the algorithm and the
performance on a variety of architectures (x86/ARM CPUs and NVIDIA/AMD GPUs).
The resulting algorithm is also deterministic, producing an identical result
for a given input across all of these platforms. The new MIS-2 implementation
outperforms implementations in state of the art libraries like CUSP and
ViennaCL by 3-8x while producing similar quality results. We further
demonstrate the benefits of this approach by developing parallel graph
coarsening scheme for two different use cases. First, we develop an algebraic
multigrid (AMG) aggregation scheme using parallel MIS-2 and demonstrate the
benefits as opposed to previous approaches used in the MueLu multigrid package
in Trilinos. We also describe an approach for implementing a parallel
multicolor "cluster" Gauss-Seidel preconditioner using this MIS-2 coarsening,
and demonstrate better performance with an efficient, parallel, multicolor
Gauss-Seidel algorithm.
