disjoint_path_2 (856B)
1 # Two-disjoint path problem 2 3 The [decision_problem], given a [directed_graph] and sources s1 and s2 and sinks t1 and t2, of determining whether there are vertex-disjoint [simple_paths] from s1 to t1 and s2 to t2 4 5 It is [NP_hard], cf [fortune1980directed] 6 7 The "[simple_path] via node" problem is already [NP_hard] 8 9 Not to be confused with the problem of finding two vertex-disjoint paths from {s1, s2} to {t1, t2}, which can be solved in [PTIME] using [network_flows]; in that case you cannot enforce which pairs of vertices are being connected by the two paths 10 11 Up: [disjoint_paths] 12 13 See also: [edge_connectedness], [simple_path_RPQ] 14 15 Aliases: two disjoint path problem, two disjoint paths, Disjoint path 2, twodisjoint path problem, two disjoint simple path, two disjoint simple paths, two disjoint simple path problem, two disjoint simple paths problem