wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

disjoint_paths_undirected (707B)

      1 # Disjoint paths on undirected graphs
      2 
      3 Given an [undirected_graph] G and vertices s_1, t_1, ..., s_k, t_k, decide whether there exist k [disjoint_paths] connecting s_i and t_i for each i
      4 
      5 It is is [NP_complete] if k is not fixed ([karp1975computational], cited in [liu2025disjoint])
      6 
      7 - For any constant k, by [Robertson_Seymour] it is [PTIME], in O(n^3), and even in [almost_linear_time] by [korhonen2024minor]
      8 - It is [FPT] parameterized by k
      9   - cf also [lokshtanov2021exponential], on [planar_graphs], for the dependency on k
     10 
     11 Cf [liu2025disjoint] for a review and for a generalization to [modularity_constraints]
     12 
     13 Special case: [2_disjoint_paths_undirected]
     14 
     15 Up: [disjoint_paths] on [undirected_graphs]