pith. sign in

arxiv: 1201.6578 · v1 · pith:YGLBOVOTnew · submitted 2012-01-31 · 💻 cs.CC · math.CO

Length 3 Edge-Disjoint Paths and Partial Orientation

classification 💻 cs.CC math.CO
keywords problemedge-disjointlengthnp-hardorientationpartialpathsclaimed
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.