2012/01/31 by Alpert, Hannah, Iglesias, Jennifer
#68Q25 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1201.6578
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álvölgyi to be NP-hard.