Distance-2 coloring does not respect distance-1 neighbors having same color

[brian-kelley]

Distance-2 coloring only checks for conflicts between pairs of vertices, separated by a path of length exactly 2. If there is no path of length 2 but a path of length 1 (u and v are immediate neighbors, and neither u nor v have themselves as neighbors) then the conflict will not be detected, and so the coloring will be incorrect.

If every row has the diagonal entry (every vertex has itself as a neighbor) then the algorithms are correct, but we don't enforce that or document it as a precondition. Consider it a bug.

[brian-kelley]

Our distance-2 algorithms are actually doing bipartite one-sided coloring, not distance-2 coloring!

[srajama1]

Our distance-2 algorithms are actually doing bipartite one-sided coloring, not distance-2 coloring!

By accident :)

[brian-kelley]

Yes of course :)

[brian-kelley]

@srajama1 After fixing the d2 coloring verification (to check d1 conflicts), all the d2 unit tests failed as expected. All the algorithms except SPGEMM+d1 were easy to fix. The problem with SPGEMM is that there's no way to tell the multiply to pretend there's a diagonal entry in every row.

Is it OK if I just get rid of SPGEMM-based d2? I don't think it'll be missed, since it's slow and uses lots of memory (as the squared matrix has an extra level of fill-in).

[srajama1]

@brian-kelley Yes, please remove it. It was supposed to be a temporary one until we had actual d2 working. We just didn't get to removing it.

[srajama1]

@crtrott This is should be closed, no ?