MultiProtocol Label Switching (MPLS) is used inside large ISP networks to provide services with stringent Service Level Agreements such as Virtual Private Networks (VPNs). Customers are now urging ISPs to provide such services across interdomain boundaries. This requires the ability to establish interdomain MPLS Label Switched Paths (LSPs) with constraints. Up to now, the literature has mostly focused on mechanisms to compute LSPs inside a single AS. In this paper, we explore the fundamental trade-offs for the computation of interdomain LSPs with QoS guarantees. We first show how cooperative Path Computation Elements (PCE) can be used to establish such LSPs. Our simulations indicate that with cooperative PCEs, it is possible to find good paths, but this is at the cost of a large number of messages exchanged between PCEs. In addition, we observe that the routes known to BGP constitute the main limitation to obtain interdomain LSPs that compete in their QoS with those that could be found using the full topological information of the network. We then propose and evaluate two heuristics to select appropriate interdomain paths without requiring too many inter-PCE messages.