  Cognitive Radio Networks (CRNs) are considered as a promising solution to the
spectrum shortage problem in wireless communication. In this paper, we initiate
the first systematic study on the algorithmic complexity of the connectivity
problem in CRNs through spectrum assignments. We model the network of secondary
users (SUs) as a potential graph, where two nodes having an edge between them
are connected as long as they choose a common available channel. In the general
case, where the potential graph is arbitrary and the SUs may have different
number of antennae, we prove that it is NP-complete to determine whether the
network is connectable even if there are only two channels. For the special
case where the number of channels is constant and all the SUs have the same
number of antennae, which is more than one but less than the number of
channels, the problem is also NP-complete. For the special cases in which the
potential graph is complete, a tree, or a graph with bounded treewidth, we
prove the problem is NP-complete and fixed-parameter tractable (FPT) when
parameterized by the number of channels. Exact algorithms are also derived to
determine the connectability of a given cognitive radio network.
