标题： 长度3的边不相交路径和部分定向 显示英文标题

标题： Length 3 Edge-Disjoint Paths and Partial Orientation

摘要： 2003年，有人声称以下问题可以在多项式时间内求解：在给定的图中，顶点s和t之间是否存在k条长度恰好为3的边不相交路径？ 该证明存在缺陷，我们证明即使不允许多重边，这个问题也是NP难的。 我们使用从部分定向问题的约化，这是一个最近由Pálvölgyi证明为NP难的问题。 显示英文摘要

摘要： In 2003, it was claimed that the following problem was solvable in polynomial time: do there exist k edge-disjoint paths of length exactly 3 between vertices s and t in a given graph? The proof was flawed, and we show that this problem is NP-hard even if we disallow multiple edges. We use a reduction from Partial Orientation, a problem recently shown by P\'alv\"olgyi to be NP-hard.