A note on polynomial complexity optimal multiuser detection for certain non-orthogonal CDMA signals

It is well known that jointly-optimum multiuser detection (MUD) in code division multiple access (CDMA) systems has a computational complexity that increases exponentially with the number of users. If the signal cross-correlations between different users are non-positive, then optimum MUD can be done with polynomial complexity using graph theory. The MUD problem is transformed into one that solves for the minimum cut (min-cut) or maximum flow (max-flow) in an associated graph or network. An alternative method to transform the MUD problem into a network, that sees a reduction in the number of edges by 50 percent, is proposed. This results in minimizing the already polynomial-complexity of existing multiuser detection techniques based on edge-dependent max-flow algorithms.