Length 3 Edge-Disjoint Paths Is NP-Hard
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 in this note we show that this problem is NP-hard. We use a reduction from Partial Orienta...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
SP Birkhäuser Verlag Basel
2017
|
| Online Access: | http://hdl.handle.net/1721.1/106920 https://orcid.org/0000-0001-5813-5029 |