wiki_research

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

simple_path_parity_problem (515B)

      1 # Simple path parity problem
      2 
      3 [Computational_problem] of deciding if there is a [simple_path] in a [graph] from a vertex s to a vertex t that has even length (or odd length)
      4 
      5 This is [NP_complete] in general graphs by reduction from [two_disjoint_simple_path]
      6 
      7 But on [planar_graphs] it is in [PTIME] by [nedev1999finding]
      8 - shown by reduction to [undirected_k_disjoint_path_problem]
      9 - also and on [outerplanar_graphs] it is in [PTIME] even for [simple_path_RPQ] by [nedev2000polynomial]
     10 
     11 Up: [simple_path_problem]