Adjacency on the constrained assignment problem

Let Qc,r be the integer hull of the intersection of the assignment polytope with a given hyper-plane H = {x = (xij) ϵ Rn × n: ∑ni = 1 ∑nj = 1 cijxij = r}. We show that the problem of checking whether two given extreme points of Qc,r are nonadjacent on Qc,r is solvable in O(n5) time if c = (cij) is a 0–1 matrix, and that it is NP-Complete if c is a general integer matrix.