wiki_research

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

even_path_problem (409B)

      1 # Even path problem
      2 
      3 The [decision_problem] of whether a [directed_graph] has an [even_path] from s to t
      4 
      5 It is easy for [walks] but [NP_hard] for [simple_paths] by reduction from [2_disjoint_paths_problem], cf [lapaugh1984even]
      6 
      7 Tractable for [directed_single_crossing_graphs], cf [chauhuan2025evenpath]
      8 
      9 Discussed in [amarilli2024survey]
     10 
     11 Up: [decision_problem], [even_path]
     12 
     13 See also: [even_cycle_problem]