我一直在尝试以下问题，但没有成功。
问题如下：
给你一个图G（V，E），并要求你生成从起始节点S到节点T的两条路线。边E被分割成K个不相交的集合。让我们将两条路线称为R1和R2。在同一集合中可以不存在边E1和E2，使得E1在路径R1中并且E2在R2中（更简单地说，每个集合必须由不多于一个路由使用）。此外，在R1和R2之间不可能存在共享的节点。我们正在寻找R1和R2的最短组合路径长度（最小化（len（R1）+len（R2））。
我尝试过将子集和和独立集简化为这个，但没有成功。
首先，感谢您发布了一个非常有趣的问题。这真是太有趣了！
我提出的减少是从3SAT到你的问题。直观地说，归约的工作原理如下：我们构建了一个由两个平行的级联节点序列组成的图（让我们称它们为左分支和右分支）。左分支边对应于公式中的变量，右分支对应于公式的子句。我们将构建图，使这两条路径对应于为满足所有子句的公式选择变量赋值。
左分支强制变量取值，其构建如下。对于每个变量x，构建一个小工具，如下所示：
*
true --> / <-- false
* *
/
*
从顶部节点开始，"left"表示"x为true"，"right"表示"x为false"。我们将为每个变量构建一个小工具副本，并从上到下链接它们。因此，从链的顶部向下到底部的路径对应于为命题公式选择变量赋值。
右侧分支的构建方式类似。假设我们有一个子句x&lor；y&lor；z。然后我们构建这个小工具：
*
/|
* * *
|/
*
这里，左分支对应"x为真"，中分支对应"y为真"和右分支对应"z为真"。我们的想法是，每个子句至少需要一个真文字，我们将通过选择向下的路径来选择哪个文字。
现在，我们构建约束集。对于每个变量x，我们希望确保如果在左分支中我们说x是真的，那么我们不会遵循右分支中x应该是假的边。因此，我们将创建一个约束集，其中包含左分支的边"x为true"和右分支的所有"x为false"副本。我们将类似地创建第二个约束集，该约束集包含左分支的边"x为false"和右分支的所有标记为"x为true"的边。这些约束集共同确保，如果我们通过左分支和右分支选择一条路径，我们会为每个变量选择一个值（通过左分支的路径），并为每个子句选择至少一个真正的文本（通过右分支的路径）。
为了完成这一切，我们将创建一个新的起始节点S和一个新终端节点T，将S链接到左分支中的第一个节点和右分支中的第二个节点，并将左分支和右分支的最后一个节点链接到T。快速计算表明，如果该公式有n个变量和m个子句，则通过左分支的路径长度为2n+2，通过右分支的路径的长度为2m+2，因此该公式是可满足的，当且仅当存在一对从s到T的节点不相交路径，其组合长度为2n+2m+4。请注意，如果公式不可满足，则根本没有合法的路径。
希望这能有所帮助！