Background: Cattle international genetic evaluations allow the comparison of estimated breeding values (EBV) across different environments, i.e. countries. For international evaluations, across-country genetic correlations (r g ) need to be estimated. However, lack of convergence of the estimated parameters and high standard errors of the r g are often experienced for beef cattle populations due to limited across-country genetic connections. Furthermore, using all available genetic connections to estimate r g is prohibitive due to computational constraints, thus sub-setting the data is necessary. Our objective was to investigate and compare the impact of strategies of data sub-setting on estimated across-country r g and their computational requirements. Methods: Phenotype and pedigree information for age-adjusted weaning weight was available for ten European countries and 3,128,338 Limousin beef cattle males and females. Using a Monte Carlo based expectation-maximization restricted maximum likelihood (MC EM REML) methodology, we estimated across-country r g by using a multi-trait animal model where countries are modelled as different correlated traits. Values of r g were estimated using the full data and four different sub-setting strategies that aimed at selecting the most connected herds from the largest population. Results: Using all available data, direct and maternal r g (standard errors in parentheses) were on average equal to 0.79 (0.14) and 0.71 (0.19), respectively. Direct-maternal within-country and between-country r g were on average equal to - 0.12 (0.09) and 0.00 (0.14), respectively. Data sub-setting scenarios gave similar results: on average, estimated r g were smaller compared to using all data for direct (0.02) and maternal (0.05) genetic effects. The largest differences were obtained for the direct-maternal within-country and between-country r g, which were, on average 0.13 and 0.12 smaller compared to values obtained by using all data. Standard errors always increased when reducing the data, by 0.02 to 0.06, on average. The proposed sub-setting strategies reduced the required computing time up to 22% compared to using all data. Conclusions: Estimating all 120 across-country r g that are required for beef cattle international evaluations, using a multi-trait MC EM REML approach, is feasible but involves long computing time. We propose four strategies to reduce computational requirements while keeping a multi-trait estimation approach. In all scenarios with data sub-setting, the estimated r g were consistently smaller (mainly for direct-maternal r g ) and had larger standard errors.