Length 3 edge-disjoint paths is NP-hard

DOI10.1007/S00037-012-0038-4zbMATH Open1247.05118OpenAlexW2075741721MaRDI QIDQ445249FDOQ445249

Authors Hannah Alpert, Jennifer Iglesias 

Publication date 24 August 2012

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.6578

zbMATH Keywords

network flowNP-completenessdegree sequencedirected graphNP-hardnessoriented graphEdge-disjoint paths

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Vertex degrees (05C07) Paths and cycles (05C38) Connectivity (05C40)

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.

Recommendations

• NP-completeness of some edge-disjoint paths problems
• scientific article; zbMATH DE number 1303036
• Edge-partitioning 3-edge-connected graphs into paths
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Logarithmic hardness of the undirected edge-disjoint paths problem
• The \(k\) edge-disjoint 3-hop-constrained paths polytope
• Finding two edge-disjoint paths with length constraints
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• A linear time algorithm for finding three edge-disjoint paths in Eulerian networks

Cites Work

• Length 3 edge-disjoint paths is NP-hard
• On the complexity of vertex-disjoint length-restricted path problems

Cited In (2)

• Length 3 edge-disjoint paths is NP-hard
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs

This page was built for publication: Length 3 edge-disjoint paths is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q445249)