We target M-ary data sequence estimation over time-variant frequency selective fading channels subject to co- channel interference (CCI). A novel joint reduced state sequence estimator is presented cancelling a dominant interferer by joint detection. It works similar to a Joint M-Algorithm (JMA), but with a metric minimizing the expectation of the Euclidian distance between received signal and convolution of channel and data hypotheses. In this way, we overcome the well known dependence of reduced search techniques on the partial channel energy. Co- Channel interference (CCI) as well as intersymbol-interference (ISI) is modelled as Gaussian noise and considered in the metric. This approach dramatically reduces the number of states to obtain a certain performance compared to JMA. The resulting joint breadth first tree detector combines good performance with low complexity. For low velocities, the technique can work with an initial channel estimate as data detector only, termed Joint Improved M-Algorithm (JIMA). For higher velocities, two Joint Iterative Channel Data Estimation (JICDE) techniques are discussed. The complexity of JIMA is linear in the alphabet size of each individual user and approximately linear in the channel memory. In comparison to known reduced state sequence estimators, no Front End Prefilter (FEP) to shorten the channel is needed. We propose a receiver with fixed parameterization. The GSM/EDGE signal model is used, 16 states are sufficient for detection of an 8-PSK signal, 3 states are needed for a GMSK-signal to yield performance similar to a 64 state Joint Delayed Decision Feedback Sequence Estimation (JDDFSE).