A {−1,0,1}- and sparsest basis for the null space of a forest in optimal time

Given a matrix, the Null Space Problem asks for a basis of its null space having the fewest nonzeros. This problem is known to be NP-complete and even hard to approximate. The null space of a forest is the null space of its adjacency matrix. Sander and Sander (2005) and Akbari et al. (2006), independently, proved that the null space of each forest admits a {−1,0,1}-basis. We devise an algorithm for determining a sparsest basis of the null space of any given forest which, in addition, is a {−1,0,1}-basis. Our algorithm is time-optimal in the sense that it takes time at most proportional to the number of nonzeros in any sparsest basis of the null space of the input forest. Moreover, we show that, given a forest F on n vertices, the set of those vertices x for which there is a vector in the null space of F that is nonzero at x and the number of nonzeros in any sparsest basis of the null space of F can be found in O(n) time.