Abstract: Secure multi-party computation is a research focus in international cryptographic community. This paper focuses on the secure multi-party computation of set-inclusion and graph-inclusion problems and a secure multi-party computation solution to set-inclusion problem is proposed. Based on this solution and combined with Monte Carlo approach and Cantor encoding, an approximate secure multi-party computation solution to graph-inclusion problem is further proposed. It is proved by simulation paradigm that these solutions are secure. Comparing with known solutions, these solutions can solve more complicated problems and have, with lower communication complexity, more applicability. For some problems that can be solved with known solutions, the new solutions have less computational complexity.