Problem Based Benchmark Suite (2020)

Maximal Independent Set (MIS):

Given a undirected graph return a maximal independent set (MIS) for the graph. For timing purposes the input can either be an adjacency array format with all edges appearing in both directions, or an edge array with all edges appearing in just one direction. Any MIS is valid.

Input and Output File Formats

The input is a graph in the in the adjacency graph format. The output is a sequence of integers corresponding to the locations of all vertices in the MIS (0 based). The output needs to be in the sequence format. The vertex indices need not be sorted in the output.

For timing purposes any code is allowed to covert from the adjacency graph format to an edge based format outside of the timed code, but is not allowed to do any other processing of the graph (e.g. reordering to improve locality).

Default Input Distributions

Each distribution should be run for n=10,000,000. The weights used for average time are given in parentheses.

• (1) Random local graph with approximately 10 edges per vertex. This graph is generated so that the probability of each edge out of a vertex is biased to nearby vertices.

  randLocalGraph -j -d 3 -m <5*n> <n> <filename>
  

• (1) An RMAT graph with parameters (.3,.1,.1,.5) and about 5n edges.

  rMatGraph -j -a .5 -b .1 -m <5*n> <n> <filename>
  

• (1) A 3 dimensional grid.

  gridGraph -j -d 3 <n> <filename>