Co-evolution happens when two or more species affect each other's evolution. One of the main ways of studying co-evolution is by means of a co-phylogenetic analysis, that is the reconstruction of the co-evolutionary history of groups based on their phylogenetic information. In the case of a host-parasite relationship, the objectives are to arrive at a better understanding of the dynamics of the infection of one group (the parasites) by the other (the hosts) and to estimate the longevity of the association. In the model we use, we are given a host tree H, a parasite tree P, and a function mapping the leaves of P to the leaves of H. A feasible reconciliation is a function that can be constructed using in general four main biological operations: co-speciation, duplication, host-switch, and loss. Costs are assigned to the events and a most parsimonious solution is sought. Despite an extensive research, many problems remain. First, it is frequent that for a given input, there are many optimal solutions which are quite different among them although having same cost. Hence, relying on a single optimal solution is problematic. To address this, we proposed a polynomial delay algorithm, Eucalypt, for generating all the optimal solutions. Second, from a biological point of view, reasonable cost values for an event-based reconciliation are not easily chosen. With Coala, we developed an algorithm that, for a given input, estimates the frequency of the events based on an approximate Bayesian computation approach. We studied the robustness of the methods proposed over small perturbations of the input. Some typical perturbations that were considered are the change of the root and/or of the associations of the leaves. Through a statistical analysis, we identified some issues with the current model and propose directions on how to address them.