本文研究了一个属于图论领域的优化问题，即MaximumSimpleSharing(MSS)问题。MsS问题的目标，是在一个二分无向图上寻找由互不相交的路径所构成的集合，并要求这个集合满足一些特定的条件。MSS问题本身具有较大的理论价值，同时，MSS问题是MaximumSharing(MS)问题的变种，而后者在VLSI电路设计和分析领域有着重要的实际应用。特别的，对于和Quantum-dotcellularAutomata(QCA)电路有关的研究领域中，它们扮演了极为核心的角色。 本文介绍了MSS问题的起源，定义和讨论了2一LayerWeakNDCE问题和MSS问题，并严格地证明了上述两个问题的等价性。同时，本文从难计算性的角度讨论了MSS问题，证明了MSS问题的NP难性质。本文的最主要的结果集中在对MSS问题的近似算法的讨论上。本文首先给出了一个简单的、基于贪心策略的近似算法，然后给出了一个精巧的、近似度为5／3的近似算法，并以一个例子指出文中对近似度的分析是足够充分的。最后，本文引入了对MSS问题近似度下界的讨论，证明了对于任意的常数c>0，MSS问题的近似度不能小于740／739一E，除非P=NP。